¿Cómo resolver esta suma múltiples?

Question

¿Cómo resolver esta suma?

$$\sum_{0\le x_1\le x_2...\le x_n \le n}^{}\binom{k+x_1-1}{x_1}\binom{k+x_2-1}{x_2}...\binom{k+x_n-1}{x_n}$ $ donde conocen a $k$, $n$.

Debido a la identidad de palo de hockey, $$\sum_{i=0}^n\binom{i+k-1}{i}=\binom{n+k}{k}$ $

Answer 1

Supongamos que buscamos para evaluar $$\sum_{0\le x_1\le x_2\cdots \le x_n \le n} {k+x_1-1\elegir x_1} {k+x_2-1\elegir x_2} \cdots {k+x_n-1\elegir x_n}.$$

El uso de la Polya Enumeración Teorema y el ciclo de índice de la grupo simétrico esto se convierte en $A$Z(S_n) \left(Q_0+Q_1+Q_2+\cdots +Q_n\right)$$

evaluados en $$Q_m = {k-1+m\choose m}.$$

Ahora la OGF del ciclo de índice $Z(S_n)$ del grupo simétrico es $$G(z) = \exp \left(a_1 \frac{z}{1} + a_2 \frac{z^2}{2} + a_3 \frac{z^3}{3} + \cdots \right).$$

Cédula de generación de función se convierte en $$H(z) = \exp \left(\sum_{p\ge 1} \frac{z^p}{p} \sum_{m=0}^n {k-1+m\elegir m}^p\right) = \exp \left(\sum_{m=0}^n \sum_{p\ge 1} \frac{z^p}{p} {k-1+m\elegir m}^p\right) \\ = \exp \left(\sum_{m=0}^n \log\frac{1}{1-{k-1+m\elegir m} z}\right) = \prod_{m=0}^n \frac{1}{1-{k-1+m\elegir m} z}.$$

Algunos pensaron que muestra que esto podría haber sido obtenida por la inspección.

Utilizamos parcial fracciones de los residuos en esta función que nos re-escribir como sigue: $$(-1)^{n+1} \prod_{m=0}^n {k-1+m\elegir m}^{-1} \prod_{m=0}^n \frac{1}{z-1/{k-1+m\elegir m}}.$$

El cambio a los residuos obtenemos $$(-1)^{n+1} \prod_{m=0}^n {k-1+m\elegir m}^{-1} \sum_{m=0}^n \frac{1}{z-1/{k-1+m\elegir m}} \\ \times \prod_{p=0, \; p\ne m}^n \frac{1}{1/{k-1+m\elegir m}-1/{k-1+p\elegir p}}.$$

La preparación para extraer los coeficientes obtenemos $$(-1)^{n} \prod_{m=0}^n {k-1+m\elegir m}^{-1} \sum_{m=0}^n \frac{{k-1+m\elegir m}}{1-z{k-1+m\elegir m}} \\ \times \prod_{p=0, \; p\ne m}^n \frac{1}{1/{k-1+m\elegir m}-1/{k-1+p\elegir p}}.$$

Haciendo el coeficiente de extracción obtenemos $$(-1)^{n} \prod_{m=0}^n {k-1+m\elegir m}^{-1} \sum_{m=0}^n {k-1+m\elegir m}^{n+1} \\ \times \prod_{p=0, \; p\ne m}^n \frac{1}{1/{k-1+m\elegir m}-1/{k-1+p\elegir p}} \\ = (-1)^{n} \prod_{m=0}^n {k-1+m\elegir m}^{-1} \sum_{m=0}^n {k-1+m\elegir m}^{2n+1} \\ \times \prod_{p=0, \; p\ne m}^n \frac{1}{1-{k-1+m\elegir m}/{k-1+p\elegir p}} \\ = (-1)^{n} \sum_{m=0}^n {k-1+m\elegir m}^{2n} \prod_{p=0, \; p\ne m}^n \frac{1}{{k-1+p\elegir p}-{k-1+m\elegir m}}.$$

La complejidad de aquí es buena ya que la fórmula tiene una ecuación cuadrática número de los términos en $n.$ El número de particiones de un total de enumeración habría que tener en cuenta es dada por

$A$Z(S_n) \left(Q_0+Q_1+Q_2+\cdots +Q_n\right)$$

evaluados en$Q_0 = Q_1 = Q_2 = \cdots = Q_n = 1$, lo que le da la sustituir la generación de la función

$$A(z) = \exp\left((n+1)\log\frac{1}{1-z}\right) = \frac{1}{(1-z)^{n+1}}.$$

Este rendimientos para el número total de particiones $${n+n\choose n} = {2n\choose n}$$ que por Stirling ha asintótica (consulte OEIS A00984) $$\frac{4^n}{\sqrt{\pi n}} \quad\text{y}\quad n^2\o\left(\frac{4^n}{\sqrt{\pi n}}\right).$$

Por ejemplo, cuando se $n=24$ $k=5$ tendríamos que considerar ${48\choose 24} = 32.247.603.683.100$ particiones pero la fórmula fácilmente rendimientos $$424283851839410438109261697709077430045882514844\\ 665327684062172306602549601581316037895634544256\\ 47212676100.$$

La exploración adicional de estas fórmulas puede realizarse usando la siguiente Arce código que contrasta total de la enumeración y el cerrado la leche de fórmula.

A :=
proc(n, k)
 opción de recordar;
 local iter;

 iter :=
proc(l)
 si nops(l) = 0, entonces
 agregar(iter([p]), p=0..n)
 elif nops(l) < n, entonces
 agregar(iter([op(l), q]), p=op(-1, l)..n)
otra cosa
 mul(binomial(k-1+l[q], l[q]), p=1..n);
fi;
end;

el iter([]);
end;

EX := 
proc(n, k)
 opción de recordar;

(-1)^n*agregar(binomial(k-1+m,m)^(2*n)*
 mul(1/(binomial(k-1+p,p)-binomio(k-1+m,m)), p=0..m-1)*
 mul(1/(binomial(k-1+p,p)-binomio(k-1+m,m)), p=m+1..n),
m=0..n);
end;