Primo de Vandermonde binomio identidad

Question

El Vandermonde binomio identidad puede ser expresado como \begin{align*} \sum_{i+j=r} \binom{m}{i} \binom{n}{j} = \binom{m+n}{r} && r \leq m +n. \end{align*} Mientras se trabaja en un problema de álgebra, me topé con un formalmente similares, pero distintas de la identidad: \begin{align*} \sum_{i+j=r} \binom{i}{m}\binom{j}{n} = \binom{r+1}{m+n+1} && m+n \leq r. \end{align*} Esto no es difícil de probar o nada. El lado izquierdo enumera los subconjuntos $S \subseteq \{1,2,\ldots,r+1\}$ $|S| = m+n+1$ según la posición de la $(m+1)$st elemento más grande de $S$. Pero, he encontrado la similitud sorprendente suficiente para pedir la siguiente

Pregunta: Son los paralelismos entre estas dos fórmulas sólo una coincidencia? O, ¿hay algo más en juego aquí?

Answer 1

Esto no es una explicación completa, pero esta observación podría ser útil:

Tenga en cuenta la suma $$ S(s,r)= \sum_{m+n=s}\sum_{i+j=r} \binom{m}{i} \binom{n}{j}, $$ con $r\leq s$.

El uso de la primera fórmula, se convierte en $$ S(s,r) = \sum_{m+n=s} \binom{s}{r} = (s+1) \binom{s}{r} = \frac{(s+1)!}{r!(s-r)!}. $$ Por otro lado, al cambiar el orden de la suma y el uso de la segunda fromula, se convierte en $$ S(s,r) = \sum_{i+j=r} \binom{s+1}{r+1} = (r+1) \binom{s+1}{r+1} = \frac{(s+1)!}{r!(s-r)!}. $$

Esto sugiere que podría ser una buena forma de calcular el $S(s,r)$ (o tal vez una combinatoria interpretación de $S(s,r)$) que muestra una relación intuitiva entre las fórmulas que se dio.

---

De hecho hay una combinatoria de interpretación:

Considerar un conjunto de $s+1$ de la gente. $$\{1,2,\ldots,s+1\}$$ Queremos contar el número de maneras de seleccionar un presidente y $r$ a los miembros del comité a partir de este conjunto.

• Directamente, no se $(s+1) \cdot \binom{s}{r}$ maneras de hacer esto.
• Indirectamente, si $x$ es el presidente, entonces hay $m$ de la gente a la izquierda de $x$ $n$ de la gente a la derecha de $x$ donde $m+n=s$, el resto de las personas que podrían estar en el comité. Tenemos ahora un recuento de los posibles comités condicionada a no ser $i$ personas seleccionadas desde el lado izquierdo del grupo y $j=r-i$ seleccionado desde la derecha de la del grupo.

Answer 2

Puede ser ajustado para ser una convolución por el desplazamiento de la parte superior e inferior de los índices y, a continuación, debe haber un poder formal de la serie de $f(x)$ para que la segunda identidad

equivale al $x^t$ términos en $f(x)^p f(x)^q = f(x)^{p+q}$,

así como la identidad de la primera compara el $x^r$ coeficientes de $(1+x)^m (1+x)^n = (1+x)^{m+n}$.

Tomando $(I,J,R,M,N) = (i+1, j+1, r+2, m+1, n+1) $ la fórmula se convierte en

\begin{align*} \sum_{I+J=R} \binom{I-1}{M-1}\binom{J-1}{N-1} = \binom{R-1}{M+N-1} && M+N \leq R. \end{align*}

que ahora tiene la forma correcta $\sum_{I+J=R} c(M,I)c(N,J) =c(M+N,R)$

para $c(p,q)={{q-1} \choose {p-1}}$.

Podemos leer en $f(x)$$\sum c(1,v)x^v = 0 + x + x^2 + x^3 + \dots = \frac{x}{1-x}$ , $(t,p,q)=(R,M,N)$ y escribir todo en las variables originales. La identidad

equivale al $x^{r+2}$ coeficientes de $\hskip10pt (\frac{x}{1-x})^{m+1}(\frac{x}{1-x})^{n+1} = (\frac{x}{1-x})^{m+n+2}.$

La cancelación de los poderes de la $x$ da una prueba usando el teorema binomial con exponentes negativos, por

equiparación de la $x^{r-m-n}$ coeficientes de $\hskip10pt (\frac{1}{1-x})^{m+1}(\frac{1}{1-x})^{n+1} = (\frac{1}{1-x})^{m+n+2}.$