Combinatoria Prueba Binomial-tipo de Identidad

Question

Yo estoy buscando para encontrar una combinatoria de prueba para los siguientes: la Fijación de $k,n$ no negativo, quiero que $$\sum a_1\dots a_k={n+k-1\choose 2k-1}$$ where the sum ranges over all $a_1+\dots +a_k=n$ with $a_i\ge 0$ $\forall i\in [k]$.

Supongo que he estado buscando en el lado derecho con una versión modificada de "estrellas y barras" tipo de mentalidad. Voy a escribir $n+k-1$ estrellas y, a continuación, círculo de $2k-1$ de ellos. Voy a barrido de izquierda a derecha, poner las estrellas en un cubo, y cuando llego a la segunda círculo puedo poner una línea a través de él para iniciar una nueva cubeta. Sigo poniendo las cosas en el cubo de pasar al siguiente círculo de estrellas, y, a continuación, dibuje una línea a través de la de después. Esto debería dar a me $k$ baldes con $a_i$ cosas en cada uno de ellos (y con el $\sum a_i=n$ desde que cruzamos cada segundo círculo de la estrella).

Es este el derecho bijection en algún sentido? Entiendo lo que me hizo, pero no estoy seguro si entiendo por qué lo hice bien (si es que). Es decir, ¿cuál es el procedimiento inverso y cuál es el lado izquierdo contando?

Answer 1

Usted está en el camino correcto. El $k-1$ un círculo de estrellas en la posiciones numeradas son los límites entre el $k$ cubos, y el otro $k$ un círculo de estrellas elegir un elemento específico de cada segmento. Por lo tanto, $\binom{n+k-1}{2k-1}$ cuenta el número de maneras de dividir a $n$ cosas en $k$ baldes y elegir una cosa de cada cubo.

Ahora considere un determinado vector de contenido, $\langle a_1,\dots,a_k\rangle$, lo $a_i$ cosas en el $i$-th cubo. ¿Cuantas veces este vector se contarán en que el coeficiente binomial? Una vez para cada forma de la elección de un objeto de cada uno de ellos, y hay $a_1a_2\dots a_k$ maneras de hacerlo. Por lo tanto, el contenido de vectores $\langle a_1,\dots,a_k\rangle$ son contados $a_1a_2\dots a_k$ veces en el coeficiente binomial. Y en el lado izquierdo usted está simplemente en sumar esos productos a través de todo el contenido posible de los vectores.

(Interesante de identidad; yo no había visto antes.)

Answer 2

Tenga en cuenta que $$ 1x^1+2x^2+3x^3+4x^4+\dots=\frac{x}{(1-x)^2}\etiqueta{1} $$ Si elevamos $(1)$ $k^{\text{th}}$ de la potencia, el coeficiente de $x^n$ sería la suma de todos los productos de $k$ enteros positivos que se suma a $n$. Es decir, queremos encontrar el coeficiente de $x^{n-k}$$(1-x)^{-2k}$: $$ \begin{align} (-1)^{n-k}\binom{-2k}{n-k} &=\binom{n+k-1}{n-k}\\[6pt] &=\binom{n+k-1}{2k-1}\tag{2} \end{align} $$