Entero partición con un número fijo de sumandos pero sin fin

Question

Para una fija $n$$M$, estoy interesado en el número de desordenada entero no negativo soluciones a $$\sum_{i = 1}^n a_i = M$$

O, en otras palabras, estoy interesado en el número de soluciones con distintos números. Para$n = 2$$M = 5$, me gustaría plantear soluciones $(1,4)$ $(4,1)$ equivalente, y elegir la solución con $a_1 \ge a_2 \ge ... \ge a_n \ge 0$ como el representante de la clase de equivalente de soluciones.

Sé cómo obtener el número de total, ordenado, las soluciones con las "estrellas y barras" método. Pero, por desgracia, no puedo solo hay que dividir el resultado por $n!$, ya que sólo funcionaría si todos los $a_i$ son distintos.

Answer 1

Quieres saber el número de particiones de $M$ en la mayoría de los $n$ partes. Un estándar bijection (transposición de la Joven diagrama) muestra que este es igual al número de particiones de $M$ en partes de tamaño en la mayoría de las $n$. Este número $p_n(M)$, fija $n$, la generación de la función

$$\sum_{M \ge 0} p_n(M) t^M = \frac{1}{(1 - t)(1 - t^2)...(1 - t^n)}.$$

Mediante el cálculo de la fracción parcial de la descomposición de esta función racional, se puede escribir de una forma cerrada para $p_n(M)$ (de nuevo, para que fija $n$). Esto es eficiente en el régimen en el que las $M$ es grande en comparación a $n$. No sé qué régimen te importa.

Para lo que vale, el dominante plazo (fijo $n$$M \to \infty$) es fácil de extraer: es dada por

$$p_n(M) \approx \frac{1}{n!} {M+n-1 \choose n-1}$$

que se deduce del hecho de que el polo dominante en $t = 1$ tiene multiplicidad $n$ y a partir de un cálculo del coeficiente del término correspondiente en la fracción parcial de la descomposición. En otras palabras, dividiendo el número que se obtiene de las estrellas-y-bares por $n!$ es aproximadamente correcto (fijo $n$$M \to \infty$) debido a que en este régimen la probabilidad de que cualquiera de los dos números de la misma se vuelve despreciable. También hay una bonita forma geométrica para ver esto, como $p_n(M)$ es el número de número entero no negativo soluciones de $x_2, ... x_n$ a

$$2x_2 + 3x_3 + ... + nx_n \le M$$

y esto se aproxima el volumen de la correspondiente simplex en $\mathbb{R}^{n-1}$.

Ver Wilf del generatingfunctionology para el fondo general sobre la generación de funciones y, por muy poderosos métodos para la extracción de asymptotics, ver Flajolet y Sedgewick de la Analítica de la Combinatoria.

Answer 2

Deje que el número de particiones ser $P_n(M)$. Mirando el número más pequeño en la partición, $a_n$, obtenemos una periodicidad de $P_n(M)$: $$P_n(M) = P_{n-1}(M) + P_{n-1}(M-n) + P_{n-1}(M-2n) + P_{n-1}(M-3n) + ...$$ Donde$P_n(0)=1$$P_n(M)=0$$M<0$. El primer término de la suma anterior viene de dejar a $a_n=0$, el segundo término de $a_n=1$, el tercero de $a_n=2$, etc.

Ahora veamos $g_n$, la generación de la función de $P_n$: $$g_n(x) = \sum_{M=0}^\infty P_n(M)\;x^M$$ Conectar la recurrencia en esta suma de los rendimientos de una recurrencia de $g_n$: $$\begin{align} g_n(x)&=\sum_{M=0}^\infty P_n(M)\;x^M\\ &=\sum_{M=0}^\infty (P_{n-1}(M) + P_{n-1}(M-n) + P_{n-1}(M-2n) + P_{n-1}(M-3n) + ...)\;x^M\\ &=\sum_{M=0}^\infty P_{n-1}(M)\;(1+x^n+x^{2n}+x^{3n}+...)\\ &=g_{n-1}(x)/(1-x^n) \end{align}$$ Tenga en cuenta que$P_0(0)=1$$P_0(M)=0$$M>0$. Esto significa que $g_0(x)=1$. Combinado con la recurrencia de $g_n$, obtenemos que $$g_n(x)=1/(1-x)/(1-x^2)/(1-x^3)/.../(1-x^n)$$ Por ejemplo, si $n=1$, obtenemos $$g_1(x) = 1/(1-x) = 1+x+x^2+x^3+...$$ Por lo tanto, $P_1(M) = 1$ todos los $M$. Si $n=2$, obtenemos $$\begin{align} g_2(x) &= 1/(1-x)/(1-x^2)\\ &= 1+x+2x^2+2x^3+3x^4+3x^5+4x^6+4x^7+5x^8+5x^9+6x^{10}+... \end{align}$$ Así, $P_2(7)=4$, $P_2(10)=6$, etc.