Cuente maneras 30 libros distintos van a 6 estudiantes, por lo que cada uno recibe como máximo 7 libros

Question

¿Qué es un buen método para el número de maneras de distribuir la $n=30$ libros distintos a $m=6$ a los estudiantes para que cada alumno recibe en la mayoría de las $r=7$ libros?

Mi observación es: Si el estudiante $S_i$ recibe $n_i$ libros, el número de maneras es: $\binom{n}{n_1,n_2,\cdots,n_m}$.

Así que la respuesta es el coeficiente de $x^n$$n!(1+x+\frac{x^2}{2!}+\cdots+\frac{x^r}{r!})^m$.

Para este caso significa calcular el coeficiente de $x^{30}$$30!(1+x+\frac{x^2}{2!}+\cdots+\frac{x^7}{7!})^6$.

Sin embargo, es bastante molesto para calcular este coeficiente, sin función exponencial. También si cambiamos $(...)$ a $e^x-(\frac{x^8}{8!}+\frac{x^9}{9!}+\cdots)$, ¿cómo podemos manejar $(\frac{x^8}{8!}+\frac{x^9}{9!}+\cdots)$ plazo?

Hay alguna buena idea para manejar este término para facilitar el cálculo?

Answer 1

Ya que la Pregunta no estatales que cada estudiante debe recibir al menos un libro, he incluido a continuación en el 46 caminos (seis números enteros no negativos suma a 30), aquellos con partes iguales a cero, sin embargo la limitación de sumandos que no exceda de 7:

$$ 30 = s_1 + s_2 + s_3 + s_4 + s_5 + s_6 $$

such that $ 7 \ge s_1 \ge s_2 \ge s_3 \ge s_4 \ge s_5 \ge s_6 \ge 0 $. These solutions were generated by a short Prolog "program" (backtracking predicate):

/* genPartitionW(SumTotal,NumberOfParts,MaxPartSize,ListOfParts) */
genPartitionW(N,1,M,[N]) :- !, N >= 0, N =< M.
genPartitionW(N,K,M,[P|Ps]) :-
    Max is min(N,M),
    for(P,Max,1,-1),
    (   N > P*K
     -> fail
     ;  ( Km is K-1, Nm is N-P )
    ),
    genPartitionW(Nm,Km,P,Ps).

For each of these I created a row in a spreadsheet, computing in one cell the multinomial coefficient:

$$ \frac{30!}{s_1!\cdot s_2!\cdot s_3!\cdot s_4!\cdot s_5!\cdot s_6!} $$

and in another cell the multiplier that accounts for how many weak compositions correspond to that summation, which is $6!$ divided by the product of factorials of frequencies of parts (number of books allocated to one student).

For example, the first summation in our list is $30=7+7+7+7+2+0$. The multinomial computation gives:

$$ \frac{30!}{7!\cdot 7!\cdot 7!\cdot 7!\cdot 2!\cdot 0!} = 205545481187904000 $$

and the orbit of weak compositions for that summation (arrangements of parts) has size:

$$ \frac{6}{4!\cdot 1!\cdot 1!} = 30 $$

The product of these is $205545481187904000\cdot 30 = 6166364435637120000$.

Debido a la limitada precisión numérica de LibreOffice Calc (en torno a 15 dígitos), me fui de regreso a la programación (Amsi! Prólogo soporta aritmética de precisión arbitraria) y tiene un total de 88,115,255,674,831,753,917,120 maneras, o aproximadamente 8.8115 E+22.

Formas de expresar 30 como sumas (hasta reordenamiento) de 6 enteros entre 0 y 7

7, 7, 7, 7, 2, 0
7, 7, 7, 7, 1, 1
7, 7, 7, 6, 3, 0
7, 7, 7, 6, 2, 1
7, 7, 7, 5, 4, 0
7, 7, 7, 5, 3, 1
7, 7, 7, 5, 2, 2
7, 7, 7, 4, 4, 1
7, 7, 7, 4, 3, 2
7, 7, 7, 3, 3, 3
7, 7, 6, 6, 4, 0
7, 7, 6, 6, 3, 1
7, 7, 6, 6, 2, 2
7, 7, 6, 5, 5, 0
7, 7, 6, 5, 4, 1
7, 7, 6, 5, 3, 2
7, 7, 6, 4, 4, 2
7, 7, 6, 4, 3, 3
7, 7, 5, 5, 5, 1
7, 7, 5, 5, 4, 2
7, 7, 5, 5, 3, 3
7, 7, 5, 4, 4, 3
7, 7, 4, 4, 4, 4
7, 6, 6, 6, 5, 0
7, 6, 6, 6, 4, 1
7, 6, 6, 6, 3, 2
7, 6, 6, 5, 5, 1
7, 6, 6, 5, 4, 2
7, 6, 6, 5, 3, 3
7, 6, 6, 4, 4, 3
7, 6, 5, 5, 5, 2
7, 6, 5, 5, 4, 3
7, 6, 5, 4, 4, 4
7, 5, 5, 5, 5, 3
7, 5, 5, 5, 4, 4
6, 6, 6, 6, 6, 0
6, 6, 6, 6, 5, 1
6, 6, 6, 6, 4, 2
6, 6, 6, 6, 3, 3
6, 6, 6, 5, 5, 2
6, 6, 6, 5, 4, 3
6, 6, 6, 4, 4, 4
6, 6, 5, 5, 5, 3
6, 6, 5, 5, 4, 4
6, 5, 5, 5, 5, 4
5, 5, 5, 5, 5, 5

Answer 2

No es muy fácil, pero al llamar a$S(b,s,m)$ la cantidad de distribuciones ($b$ books,$s$ students,$m$ máximo permitido para cada uno) se podría escribir:

ps

y calcular recursivamente los valores, con$$S(b,s,m)= \sum_{k=0}^{\min(\lfloor b/m \rfloor,s)} {s \choose k} \frac{b!}{(m!)^k(b-m \,k)!} S(b-mk,s-k,m-1) $ para$S(b,s,m) = s^b$