Colocando objetos idénticos en lugares idénticos.

Question

De cuántas maneras puede un 25 Idénticos libros pueden ser colocados en 5 cajas idénticas.

Sé que el proceso de contar, pero que es demasiado largo . Quiero enfoque diferente por lo que fácilmente se puede calcular el número necesario de la sala de Examen en pocos minutos.

Proceso de Conteo : Este problema puede ser tomado particiones de 25 en 5 partes.

25 = 25+0+0+0+0

25 = 24 +1 + 0 + 0 +0

25 = 23+ 1 +1 +0 + 0 ... .... Como de esta manera muchas combinaciones se hacen.: acerca de 377

¿Cómo podemos calcular sin este proceso de conteo manual.

Answer 1

La respuesta de Foobaz Juan definidas $p_k$$p_{\le k}$.

En primer lugar, observe que $p_{\le k}(n)=p_k(n+k)$. (Eso es porque podemos agregar un objeto a cada parte para asegurarse de que no hay piezas de tamaño cero.) Por lo tanto, si bien debemos tener cuidado de distinguir, las tablas para estas dos funciones son muy similares.

Vamos a escribir la tabla de $p_k(n)$$k=5$.

La columna de $k=1$ es idéntica $1$, por lo que podemos omitirlo. La columna de $k=2$ puede ser rellenado con $\lfloor\tfrac12n\rfloor$; después de eso, utilizamos la recurrencia $p_k(n)=p_{k-1}(n-1)+p_k(n-k)$ para obtener: $$\begin{array}{|c|cccc|}\hline&2&3&4&5\\\hline2&1\\3&1&1\\4&2&1&1\\5&2&2&1&1\\6&3&3&2&1\\\vdots&\vdots&\vdots&\vdots&\vdots\end{array}$$ Con la práctica, la tabla se puede continuar con bastante rapidez, pero tomará un par de minutos para llegar a la fila $25$, y cualquier error se propaga. Un examen no debe contener un problema, a menos que los números son muy pequeños. Sin embargo, las fórmulas no existen. No voy a intentar demostrar.

$$\begin{align*}p_2(n)&=\lfloor\tfrac12n\rfloor\\ p_3(n)&=[\tfrac1{12}n^2]\\ p_4(n)&=[\tfrac1{144}(n^3+3n^2\underbrace{-9n}_{\text{if }n\text{ odd}})]\end{align*}$$ En el segundo y tercer fórmulas, $[\ldots]$ significa que el entero más cercano.

El equivalente de la fórmula para $k=5$ $$p_5(n)=[\tfrac1{2880}(n^4+10n^3+10n^2-75n-45n(-1)^n)]$$

Sin embargo, en lugar de memorizar esto, se podría utilizar la recurrencia junto con la anterior fórmula.

$$\begin{align*}p_{\le 5}(25)=p_5(30)&=p_4(29)+p_4(24)+p_4(19)+p_4(14)+p_4(9)+p_4(4)\\&=185+108+54+23+6+1\\&=377\end{align*}$$

Answer 2

Usted podría utilizar una recurrencia.

Por ejemplo: poner $a=0,1,2,...,n$ libros en el primer cuadro y calcular, en cómo muchas maneras que usted puede poner el $n-a$ libros en $m-1$ cajas. Para evitar repeticiones, se asume, que en el siguiente cuadro se colocará a no menos libros, que a la anterior.

Por supuesto:

• si $n<a(m-1)$, entonces no hay opciones
• si $n\geq a$$m-1=1$, entonces no es una opción

Esta función tendría este aspecto:

$$F_m(n,a)=\begin{cases}1, & m=1 \wedge n\geq a\\ 0, & n<am\\ \sum_{k=0}^n F_{m-1}(n-k, k),&\text{in other cases}\end{casos} $$

Lo que usted necesita para calcular el es $F_5(25,0)$

Answer 3

En general, se puede utilizar la siguiente fórmula recursiva. Deje $P_k(n)$ ser el conjunto de particiones de $n$ con exactamente $k$ partes. Deje $p_{k}(n)$ el número de particiones de $n$ a $k$ partes es decir $p_{k}(n)=|P_k(n)|$. Entonces $$ p_{k}(n)=p_{k-1}(n-1)+p_{k}(n-k) $$ por la clasificación de los $\lambda=(\lambda_1,\dots,\lambda_k)\in P_k(n)$ (donde el $\lambda_i$ son débilmente decreciente y positiva), basado en si $\lambda_k=1$ o $\lambda_k>1$. Deje $p_{\leq k}(n)=\sum_{m=0}^kp_{m}(n)$ el número de particiones de $n$ en la mayoría de los $k$ partes.

En el caso de querer calcular $$ p_{\leq 5}(25)=\sum_{m=0}^5p_{m}(25). $$ Pero tenga en cuenta que hay algunos valores especiales de $k$ que hacen que sea fácil de calcular. De hecho $p_{0}(25)=0$, $p_{1}(25)=1$, $p_2(25)=\lfloor 25/2\rfloor=12$.

Alternativamente, podemos notar que las particiones de $n$ en la mayoría de los $k$ partes corresponden bijectively a particiones de $n$, donde la mayor parte es en la mayoría de las $k$. Así $$ \begin{align} \sum_{n\geq 0}p_{\leq k}(n)x^n&=(1+q+q^2+\dotsb)(1+q^2+q^4+\dotsb)\dotsb(1+q^k+q^{2k}+\dotsb)\\ &=\frac{1}{(1-q)(1-q^2)\dotsb(1-q^k)} \end{align} $$ En particular, encontramos que en su caso $$ p_{\leq 5}(25)=[p^{25}]\left(\frac{1}{(1-q)(1-p^2)\dotsb(1-q^5)} \right)=377 $$ el uso de un sistema algebraico por computadora, por ejemplo.

Answer 4

Número de particiones de m en b positivo partes (bloques) que se describe a continuación: https://oeis.org/A008284 en la OEIS artículo.

$P(m,b) = P(m-1, b-1) + P(m-k,b)$

La recurrencia de la fórmula significa que, dado un $P(m,b)$ partición de m en b bloques, dos situaciones que pueden ocurrir:

1) un singleton es en la partición; removemos y obtener el $ P(m-1, b-1)$ de los casos

2) no hay singleton en la partición; eliminamos una pieza de cada bloque y obtener el $P(m-k, b)$ de los casos.

por ejemplo, para P(7,3)

5+1+1 <\begin{align*}p_2(n)&=\lfloor\tfrac12n\rfloor\\ p_3(n)&=[\tfrac1{12}n^2]\\ p_4(n)&=[\tfrac1{144}(n^3+3n^2\underbrace{-9n}_{\text{if }n\text{ odd}})]\end> 5+1

4+2+1 <----> 4+2

3+3+1 <----> 3+3

3+2+2 <----> 2+1+1

Después de completar la tabla dada por Andrew Madera a la fila 25, se obtiene:

P(25,1) + P(25,2) + P(25,3)+ P(25,4)+ P(25,5) = $1+12+52+120+192 = 377$