Contar formas de distribuir m elementos entre n personas

Dadas m y n que representan el número de mangos y el número de personas respectivamente. La tarea es calcular el número de formas de distribuir m mangos entre n personas. Considerando ambas variables m y n, llegamos a 4 casos de uso típicos donde se considera que los mangos y las personas son:
1) Ambos idénticos
2) Únicos e idénticos respectivamente
3) Idénticos y únicos respectivamente
4) Ambos únicos
Requisitos previos: Coeficiente binomial | Permutación y Combinación

Caso 1: Distribuir m mangos idénticos entre n personas idénticas
Si tratamos de distribuir m mangos en una fila, nuestro objetivo es dividir estos m mangos entre n personas sentadas en algún lugar entre arreglos de estos mangos. Todo lo que tenemos que hacer es agrupar estos m mangos en n conjuntos para que cada uno de estos n conjuntos se pueda asignar a n personas respectivamente.
Para realizar la tarea anterior, necesitamos particionar el arreglo inicial de los mangos usando n-1 divisores para crear n conjuntos de mangos. En este caso, necesitamos colocar m mangos y n-1 divisores todos juntos. Así que necesitamos $(m+ n-1)!$ maneras de calcular nuestra respuesta.
La ilustración que se muestra a continuación representa un ejemplo (una forma) de una disposición de particiones creada después de colocar 3 particiones, a saber, P1, P2, P3, que dividieron los 7 mangos en 4 particiones diferentes para que 4 personas puedan tener su propia porción de la partición respectiva:

Example of an arrangement after partitioning

Como todos los mangos se consideran idénticos, dividimos $(m+n-1)!$ entre $(m)!$ para deducir las entradas duplicadas. Del mismo modo, dividimos la expresión anterior nuevamente entre $(n-1)!$ porque todas las personas también se consideran idénticas.
La expresión final que obtenemos es: $(m+n-1)!/((n-1)!*(m)!)$
La expresión anterior es incluso igual al coeficiente binomial: $^m^+^n^-^1C_n_-_1$
Ejemplo:

Input :  m = 3, n = 2
Output : 4
There are four ways
3 + 0, 1 + 2, 2 + 1 and 0 + 3 

Input :  m = 13, n = 6
Output : 8568

Input :  m = 11, n = 3
Output : 78

C++

// C++ code for calculating number of ways
// to distribute m mangoes amongst n people
// where all mangoes and people are identical
#include <bits/stdc++.h>
using namespace std;
 
// function used to generate binomial coefficient
// time complexity O(m)
int binomial_coefficient(int n, int m)
{
    int res = 1;
 
    if (m > n - m)
        m = n - m;
 
    for (int i = 0; i < m; ++i) {
        res *= (n - i);
        res /= (i + 1);
    }
 
    return res;
}
 
// helper function for generating no of ways
// to distribute m mangoes amongst n people
int calculate_ways(int m, int n)
{
    // not enough mangoes to be distributed
    if (m < n)
        return 0;
     
    // ways  -> (n+m-1)C(n-1)
    int ways = binomial_coefficient(n + m - 1, n - 1);
    return ways;
}
 
// Driver function
int main()
{
    // m represents number of mangoes
    // n represents number of people
    int m = 7, n = 5;
 
    int result = calculate_ways(m, n);
    printf("%d\n", result);
 
    return 0;
}

Java

// Java code for calculating number of ways
// to distribute m mangoes amongst n people
// where all mangoes and people are identical
 
import java.util.*;
 
class GFG {
 
    // function used to generate binomial coefficient
    // time complexity O(m)
    public static int binomial_coefficient(int n, int m)
    {
        int res = 1;
 
        if (m > n - m)
            m = n - m;
 
        for (int i = 0; i < m; ++i) {
            res *= (n - i);
            res /= (i + 1);
        }
 
        return res;
    }
 
    // helper function for generating no of ways
    // to distribute m mangoes amongst n people
    public static int calculate_ways(int m, int n)
    {
 
        // not enough mangoes to be distributed
        if (m < n) {
            return 0;
        }
 
        // ways  -> (n+m-1)C(n-1)
        int ways = binomial_coefficient(n + m - 1, n - 1);
        return ways;
    }
 
    // Driver function
    public static void main(String[] args)
    {
 
        // m represents number of mangoes
        // n represents number of people
        int m = 7, n = 5;
 
        int result = calculate_ways(m, n);
        System.out.println(Integer.toString(result));
 
        System.exit(0);
    }
}

Python3

# Python code for calculating number of ways
# to distribute m mangoes amongst n people
# where all mangoes and people are identical
 
 
# function used to generate binomial coefficient
# time complexity O(m)
def binomial_coefficient(n, m):
    res = 1
 
    if m > n - m:
        m = n - m
 
    for i in range(0, m):
        res *= (n - i)
        res /= (i + 1)
 
    return res
 
# helper function for generating no of ways
# to distribute m mangoes amongst n people
def calculate_ways(m, n):
 
    # not enough mangoes to be distributed   
    if m<n:
        return 0
 
    # ways  -> (n + m-1)C(n-1)
    ways = binomial_coefficient(n + m-1, n-1)
    return int(ways)
 
# Driver function
if __name__ == '__main__':
 
    # m represents number of mangoes
    # n represents number of people
    m = 7 ;n = 5
 
    result = calculate_ways(m, n)
    print(result)

C#

// C# code for calculating number
// of ways to distribute m mangoes
// amongst n people where all mangoes
// and people are identical
using System;
 
class GFG
{
 
// function used to generate
// binomial coefficient
// time complexity O(m)
public static int binomial_coefficient(int n,
                                       int m)
{
    int res = 1;
 
    if (m > n - m)
        m = n - m;
 
    for (int i = 0; i < m; ++i)
    {
        res *= (n - i);
        res /= (i + 1);
    }
 
    return res;
}
 
// helper function for generating
// no of ways to distribute m
// mangoes amongst n people
public static int calculate_ways(int m, int n)
{
 
    // not enough mangoes
    // to be distributed
    if (m < n)
    {
        return 0;
    }
 
    // ways -> (n+m-1)C(n-1)
    int ways = binomial_coefficient(n + m - 1,
                                    n - 1);
    return ways;
}
 
// Driver Code
public static void Main()
{
 
    // m represents number of mangoes
    // n represents number of people
    int m = 7, n = 5;
 
    int result = calculate_ways(m, n);
    Console.WriteLine(result.ToString());
}
}
 
// This code is contributed
// by Subhadeep

PHP

<?php
// PHP code for calculating number
// of ways to distribute m mangoes
// amongst n people where all
// mangoes and people are identical
 
// function used to generate
// binomial coefficient
// time complexity O(m)
function binomial_coefficient($n, $m)
{
    $res = 1;
 
    if ($m > $n - $m)
        $m = $n - $m;
 
    for ($i = 0; $i < $m; ++$i)
    {
        $res *= ($n - $i);
        $res /= ($i + 1);
    }
 
    return $res;
}
 
// Helper function for generating
// no of ways to distribute m.
// mangoes amongst n people
function calculate_ways($m, $n)
{
    // not enough mangoes to
    // be distributed
    if ($m < $n)
        return 0;
     
    // ways -> (n+m-1)C(n-1)
    $ways = binomial_coefficient($n + $m - 1,
                                      $n - 1);
    return $ways;
}
 
// Driver Code
 
// m represents number of mangoes
// n represents number of people
$m = 7;
$n = 5;
 
$result = calculate_ways($m, $n);
echo $result;
 
// This code is contributed
// by Shivi_Aggarwal
?>

Javascript

<script>
 
// Javascript code for calculating number of ways
// to distribute m mangoes amongst n people
// where all mangoes and people are identical
 
// function used to generate binomial coefficient
// time complexity O(m)
function binomial_coefficient(n, m)
{
    let res = 1;
 
    if (m > n - m)
        m = n - m;
 
    for (let i = 0; i < m; ++i) {
        res *= (n - i);
        res /= (i + 1);
    }
 
    return res;
}
 
// helper function for generating no of ways
// to distribute m mangoes amongst n people
function calculate_ways(m, n)
{
    // not enough mangoes to be distributed
    if (m < n)
        return 0;
     
    // ways -> (n+m-1)C(n-1)
    let ways = binomial_coefficient(n + m - 1, n - 1);
    return ways;
}
 
// Driver function
 
    // m represents number of mangoes
    // n represents number of people
    let m = 7, n = 5;
 
    let result = calculate_ways(m, n);
    document.write(result);
 
// This code is contributed by Mayank Tyagi
</script>

Producción:

Complejidad temporal: O(n)
Espacio auxiliar: O(1)
Caso 2: Distribuir m mangos únicos entre n personas idénticas
En este caso, para calcular el número de formas de distribuir m mangos únicos entre n personas idénticas, solo necesitamos multiplicar la última expresión $^m^+^n^-^1C_n_-_1$ que calculamos en el Caso 1 por $m!$ .
Entonces, nuestra expresión final para este caso es $^m^+^n^-^1C_n_-_1*m!$
Prueba:
en el caso 1, inicialmente obtuvimos la expresión $(m+ n-1)!$ sin eliminar las entradas duplicadas.
En este caso, solo necesitamos dividir $(n-1)!$ ya que todos los mangos se consideran únicos en este caso.
Entonces obtenemos la expresión como: $(m+ n-1)!/(n-1)!$
Multiplicando tanto el numerador como el denominador por $(n-1)!$ ,
obtenemos $(m+ n-1)!*m!/(n-1)!*m!$
Donde $((m+ n-1)!/(n-1)!*m!)*m!$ === $^m^+^n^-^1C_n_-_1*m!$
Complejidad temporal: O(max(n, m))
Espacio auxiliar: O(1)
Caso 3: Distribuir m mangos idénticos entre n personas únicas
En este caso, para calcular el número de formas de distribuir m mangos idénticos entre n personas únicas, solo necesitamos multiplicar la última expresión $^m^+^n^-^1C_n_-_1$ que calculamos en el Caso 1 por $(n-1)!$ .
Así que nuestra expresión final para este caso es $^m^+^n^-^1C_n_-_1*(n-1)!$
Prueba:
Esta prueba es bastante similar a la expresión de prueba del último caso.
En el caso 1, inicialmente obtuvimos la expresión $(m+ n-1)!$ sin eliminar las entradas duplicadas.
En este caso, solo necesitamos dividir $m!$ ya que todas las personas se consideran únicas en este caso.
Entonces obtenemos la expresión como: $(m+ n-1)!/m!$
Multiplicando tanto el numerador como el denominador por $(n-1)!$ ,
obtenemos $(m+ n-1)!*(n-1)!/(n-1)!*m!$
Donde $((m+ n-1)!/(n-1)!*m!)*(n-1)!$ === $^m^+^n^-^1C_n_-_1*(n-1)!$
Tiempo Complejidad: O(n)
Espacio auxiliar: O(1)
Para obtener referencias sobre cómo calcular $m!$ , consulte aquí el factorial de un número
Caso 4: Distribuir m mangos únicos entre n personas únicas
En este caso necesitamos multiplicar la expresión obtenida en el caso 1 por ambos $m!$ y $(n-1)!$ .
Las pruebas para ambas multiplicaciones se definen en el caso 2 y el caso 3.
Por lo tanto, en este caso, nuestra expresión final resulta ser $^m^+^n^-^1C_n_-_1*(n-1)!*m!$
Complejidad del tiempo: O(n+m)
Espacio auxiliar: O(1)