$\sum_i k_i=K$, $\sum_i i k_i=N $.

Question

Deje $(k_0,k_1,k_2\dots) $ ser un conjunto ordenado de la no-negativos números enteros. Deje $A (N,K)$ ser el número de los distintos $k $-conjuntos tales que $$\sum_i k_i=K, \quad\sum_i i k_i=N.\tag{1} $$

Hay un nombre especial para $A (N,K)$ ¿y cuál es el camino más eficaz para calcular su valor para determinado$K$$N$? ¿Hay una manera eficaz de construir todos los $k$-establece satisfactorio (1).

ACTUALIZACIÓN:

$A(N,K)$ puede ser interpretado como el número total de resultados posibles de poner $N$ indistinguibles de las pelotas en $K$ indistinguibles de las bandejas, $k_i$ el número de contenedores que contengan $i$ bolas.

Por lo tanto, $A(N,K)$ no es nada como el número de particiones de $N$ a $K$ no negativo sumandos.

La siguiente tabla muestra $A(N,K)$$0\le N,K\le11$:

$$ \left(\begin{array}{rrrrrrrrrrrr} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 \\ 0 & 1 & 2 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 \\ 0 & 1 & 3 & 4 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 \\ 0 & 1 & 3 & 5 & 6 & 7 & 7 & 7 & 7 & 7 & 7 & 7 \\ 0 & 1 & 4 & 7 & 9 & 10 & 11 & 11 & 11 & 11 & 11 & 11 \\ 0 & 1 & 4 & 8 & 11 & 13 & 14 & 15 & 15 & 15 & 15 & 15 \\ 0 & 1 & 5 & 10 & 15 & 18 & 20 & 21 & 22 & 22 & 22 & 22 \\ 0 & 1 & 5 & 12 & 18 & 23 & 26 & 28 & 29 & 30 & 30 & 30 \\ 0 & 1 & 6 & 14 & 23 & 30 & 35 & 38 & 40 & 41 & 42 & 42 \\ 0 & 1 & 6 & 16 & 27 & 37 & 44 & 49 & 52 & 54 & 55 & 56 \\ \end{array}\right) $$ Por la evidencia numérica de la siguiente relación de recurrencia: $$ Un(N,K)=A(N,K-1)+A(N-K,K),\etiqueta{2} $$ con la convención de las $A(N,K)=0$$N<0$.

Answer 1

Respuesta anterior

Es el coeficiente de $x^K y^N$ en la función \begin{eqnarray*} \prod_{i=0}^{\infty} (1+x^{k_i} y^{ik_i}). \end{eqnarray*} No estoy seguro si esto tiene un nombre especial, pero el de arriba te da un método para calcular la $A(K,N)$.

Nueva respuesta

Edit: (a la luz de la actualización de la pregunta y Alex Zorn del comentario)

Considerar la infinita producto \begin{eqnarray*} \prod_{i=0}^{\infty} \frac{1}{(1-x y^{i})} =&(1+xy+ \cdots +x^{k_1}y^{k_1}+ \cdots) \times \\ &(1+xy^2+ \cdots +x^{k_2}y^{2k_2}+ \cdots) \times \\ & \ddots \\ &(1+xy^i+ \cdots +x^{k_i}y^{ik_i}+ \cdots) \times \cdots \end{eqnarray*} El coeficiente de $x^{K} y^{N}$ le dará $A(K,N)$ donde $A(K,N)$ es el número de particiones de $N$ a $K$ partes. $k_i$ cuenta la multiplicidad de el valor de $i$ en la partición representado por el producto que le dio un determinado $x^{K}y^{N}$ plazo.

Answer 2

El bijection entre el entero de las particiones de $N$ a $K$ no negativo partes y $k$-puede ser establecido de la siguiente manera. Deje $n=(n_1,n_2,\dots,n_K)$ ser una partición ($\sum_{j=1}^K n_j=N $). Introducir la función $f:\ n\mapsto(k_0,k_1,k_2\dots)$ que para todos los $i\ge0$ asigna $k_i$ para el conteo de ocurrencias (multiplicidad) de la número $i$ en la partición de $n:\ k_i=\sum_{j=1}^K\delta_{in_j}$. Por la construcción $k_i\ge0$, $\sum_{i\ge0 }k_i=K$, y $\sum_{i\ge0 }i k_i=N$. Obviamente, la función es bijective.

El procedimiento descrito representan probablemente la manera más eficaz para la construcción de $k$-juegos para determinado $N$ $K$ proporciona un método eficaz para la partición de los números enteros no-negativos (o positivos) sumandos.

La prueba de la relación de recurrencia (2) puede llevarse a cabo de la siguiente manera. $A(N,K)$ es el número de particiones de $N$ a $K$ no negativo partes. Las particiones pueden ser divididos en aquellos que tienen al menos un sumando es igual a 0 y aquellos que sólo han positivo sumandos. En este último caso podemos restar 1 de cada sumando para obtener la partición de $N-K$ a $K$ partes. En el primer caso se puede considerar un 0 como una parte determinada y reducir el problema a la partición de la número $N$ a $K-1$ partes.