Mostrando

Question

Demostrar que para números enteros $n \geq 0$ y $a \geq 1$, $${n + a - 1 \choose a - 1} = \sum_{k = 0}^{\left\lfloor n/2 \right\rfloor} {a \choose n-2k}{k+a-1 \choose a-1}.$ $

Pensé que dejo esta pregunta, que era una tarea que hice, pues pensé que la solución era tan agradable.

Answer 1

Esto también se puede hacer uso de variables complejas.

Supongamos que buscamos para evaluar $$\sum_{k=0}^{\lfloor n/2\rfloor} {un\elegir n-2k} {k+1\elegir un-1}.$$

Introducir la representación integral $${un\elegir n-2k} =\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{a}}{z^{n-2k+1}} \; dz.$$

Tenga en cuenta que esta integral es cero cuando $k>\lfloor n/2\rfloor$ así podemos extender la suma de los infinitos términos.

Esto da por la suma de la integral $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{a}}{z^{n+1}} \sum_{k\ge 0} {k+1\elegir un-1} z^{2k} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{a}}{z^{n+1}} \frac{1}{(1-z^2)^a} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{1}{(1-z)^a} \; dz.$$

Este último evalúa a $${n+a-1\choose a-1}$$ por inspección (binomio de Newton).

Answer 2

Tenemos $a$ etiquetado de cajas y $n$ indistinguibles de las bolas. El lado izquierdo es el número de maneras de distribuir las bolas entre las cajas. El término

$$\binom{a}{n-2k}\binom{k+a-1}{a-1}$$

en la derecha es el número de maneras de distribuir la $k$ pares de pelotas entre las cajas y, a continuación, elija $n-2k$ de las cajas, cada una de las cuales es para recibir uno de los restantes $n-2k$ bolas. Por lo tanto, $k = \sum_{\text{box } i} \left\lfloor \dfrac{\text{number of balls in box } i}{2} \right\rfloor$. Claramente esto puede ser cualquier cosa, desde la $0$ a través de $\lfloor n/2\rfloor$, por lo que la derecha también se da el número de maneras de distribuir las bolas entre las cajas.

(Esta es, esencialmente, Samuel Yusim de la prueba, pero presentados de una manera que al menos algunos lectores encontrarán un poco más amigable.)

Answer 3

Supuestamente deberíamos tener un bijection $$f: M(n, a) \to \bigcup_{k=0}^{\left\lfloor n/2 \right\rfloor}\left( B(a, n-2k)\times M(k, a)\right)$$ (where $B(a, n-2k)$ is simply the set of all $n-2k$-element subsets of $\{1, 2, \los puntos, un\}$ and $M(n, a)$ is the set of $n$-element multisets with $un$ types). So take the function $$f: (c_1, \dots, c_a) \mapsto (S, (d_1, \dots, d_a))$$ where $d_i = \left\lfloor c_i/2 \right\rfloor$ and $S = \{\alpha \in \{1, \dots,\} : \left\lfloor c_\alpha/2 \right\rfloor \neq c_\alpha/2\}$. Now, it's probably worth mentioning that the set $S$ as defined here is always going to be of size $n-2k$ for some $k$ between $0$ and $\a la izquierda\lfloor n/2 \right\rfloor$, since if $n$ is even, an even number of terms in the multiset will be odd, and if $$ n es impar, un número impar de términos tendrán un valor impar.

La inversa de esta función va a ser $$g: \bigcup_{k=0}^{\left\lfloor n/2 \right\rfloor}\left( B(a, n-2k)\times M(k, a)\right) \to M(n, a)$$ defined by $$g : (S, (d_1, \dots, d_a)) \mapsto (c_1, \dots, c_a)$$ where $c_i = \begin{cases} 2d_i & i \notin S \\ 2d_i + 1 & i \in S \end{casos}$. It should be clear that this is the inverse of $f$, y por lo tanto, estamos bien.