Identidad de Vandermonde

Véase también: Determinante de Vandermonde

En teoría combinatoria, la identidad de Vandermonde o convolución de Vandermonde, que recibe su nombre del matemático francés Alexandre-Théophile Vandermonde (1772), expresa la siguiente relación entre coeficientes binomiales:

${m+n \choose r}=\sum _{k=0}^{r}{m \choose k}{n \choose r-k},\qquad m,n,r\in \mathbb {N} _{0},$

Esta identidad ya había sido descubierta en 1303 por el matemático chino Zhu Shijie (Chu Shi-Chieh).​

Por otra parte, existe una q-analogía de este teorema denominada q-identidad de Vandermonde.

Prueba algebraica

En general, el producto de dos polinomios con grados m y n respectivamente, está dado por la ecuación:

${\biggl (}\sum _{i=0}^{m}a_{i}x^{i}{\biggr )}{\biggl (}\sum _{j=0}^{n}b_{j}x^{j}{\biggr )}=\sum _{r=0}^{m+n}{\biggl (}\sum _{k=0}^{r}a_{k}b_{r-k}{\biggr )}x^{r},$

en la cual se utiliza la convención de que a_i = 0 para todos los enteros i > m y b_j = 0 para todos los enteros j > n. Según el teorema del binomio:

$(1+x)^{m+n}=\sum _{r=0}^{m+n}{m+n \choose r}x^{r}.$

Usando el teorema del binomio para los exponentes m y n, y luego la fórmula anterior para el producto de polinomios, se obtiene:

${\begin{aligned}\sum _{r=0}^{m+n}{m+n \choose r}x^{r}&=(1+x)^{m+n}\\&=(1+x)^{m}(1+x)^{n}\\&={\biggl (}\sum _{i=0}^{m}{m \choose i}x^{i}{\biggr )}{\biggl (}\sum _{j=0}^{n}{n \choose j}x^{j}{\biggr )}\\&=\sum _{r=0}^{m+n}{\biggl (}\sum _{k=0}^{r}{m \choose k}{n \choose r-k}{\biggr )}x^{r},\end{aligned}}$

el convenio anteriormente establecido para los coeficientes de los polinomios está de acuerdo con la definición de los coeficientes binomiales, porque ambos dan cero para todo i > m y j > n, respectivamente.

Mediante la comparación de los coeficientes de x^r, se observa que la identidad de Vandermonde se cumple para todos los números enteros r con 0 ≤ r ≤ m + n. Para enteros mayores que r, los dos lados de la identidad de Vandermonde son cero debido a la definición de los coeficientes binomiales.

Prueba combinatoria

La identidad de Vandermonde admite una segunda demostración combinatoria, como se desarrolla a continuación. Supóngase que un comité consiste de m hombres y n mujeres. ¿De cuántas maneras puede formarse un subcomité de r miembros? La respuesta es

${m+n \choose r}.$

Además, la solución también es la suma de todos los valores posibles de k para la serie de subcomités que cuentan con k hombres y r − k mujeres:

$\sum _{k=0}^{r}{m \choose k}{n \choose r-k}.$

De la igualdad de ambos valores, se obtiene la identidad de Vandermonde.

Prueba geométrica

Tómese una rejilla rectangular de r · (m + n-r) cuadrados. Entonces, hay

${\binom {r+(m+n-r)}{r}}={\binom {m+n}{r}}$

caminos que se inician en el vértice inferior izquierdo, y que moviéndose sólo hacia arriba o hacia la derecha alcanzan el vértice superior derecho (esto es porque r es el número de pasos a la derecha y porque pueden hacerse hasta m + n-r movimientos hacia arriba (o viceversa) en cualquier orden, y la longitud total de la ruta es m + n).

Desígnese el vértice inferior izquierdo como el origen de un sistema de coordenadas cartesianas, (0,0). Hay ${\binom {m}{k}}$ caminos que van desde (0,0) hasta (k, m-k), dándose k pasos a la derecha y m-k hacia arriba (la longitud del camino es m). Del mismo modo, hay ${\binom {n}{r-k}}$ caminos a partir de (k, m-k) que terminan en (r, m + n-r), con un total de r-k movimientos a la derecha y (m + n-r) - (m-k) hacia arriba, con una longitud del camino que debe ser r-k + (m + n-r) - (m-k) = n. Por lo tanto hay

${\binom {m}{k}}{\binom {n}{r-k}}$

caminos con origen en (0,0) y final en (r, m + n-r), y que pasan por (k, m-k). Este es un subconjunto de todos los caminos con inició en (0,0) y que terminan en (r, m + n-r), dado que la suma desde k = 0 a k = r (el punto (k, m-k) se limita para que esté dentro de la rejilla) para obtener el número total de caminos iniciados en (0,0) y que terminan en (r, m + n-r).

Identidad generalizada de Vandermonde

Si en la derivación algebraica anteriormente demostrada se utilizan dos polinomios, se obtiene como resultado la identidad de Vandermonde generalizada. Para y + 1 polinomios:

$\sum _{k_{1}+\cdots +k_{y}=0}^{x}{n \choose k_{1}}{n \choose k_{2}}\cdots {n \choose k_{y}}{n \choose x-\sum _{j=1}^{y}k_{j}}={\left(y+1\right)n \choose x}.$

Otra generalizacion de la identidad de Vandermonde se obtiene de la siguiente identidad​ al evaluar en t=0. Sean $p,q,s\leq p+q$. Para $t\leq s$:

${p+q+t \choose s}{s \choose t}=\sum _{a+c=s,n\leq a,r\leq c,n+r=t}{p+n \choose a}{a \choose n}{q+r \choose c}{c \choose r}-\sum _{a+c=s-1,n\leq a,r\leq c,n+r=t-1}{p+n \choose a}{a \choose n}{q+r \choose c}{c \choose r}.$

Distribución de probabilidad hipergeométrica

Cuando ambos lados de la ecuación son divididos por la expresión de la izquierda, el término de la derecha queda igualado a 1, y entonces los términos de la suma se pueden interpretar como probabilidades. La distribución de probabilidad resultante es la distribución hipergeométrica (es el clásico caso de la distribución de probabilidad del número de canicas rojas obtenidas en r extracciones sin reemplazo de una urna que contenga n canicas rojas y m azules).

Identidad de Chu-Vandermonde

La identidad se puede generalizar a argumentos no enteros. En este caso, se conoce como la identidad de Chu-Vandermonde (ver Askey 1975, pp. 59–60) y toma la forma

${s+t \choose n}=\sum _{k=0}^{n}{s \choose k}{t \choose n-k}$

en general para valores complejos s y t y para cualquier número entero no negativo n. Se puede demostrar a lo largo de las líneas de la prueba algebraica anterior por el producto de Cauchy de series binomiales para $(1+x)^{s}$ y $(1+x)^{t}$ y comparando sus términos con la serie binomial para $(1+x)^{s+t}$.

Esta identidad puede ser reescrita en términos de los símbolos de Pochhammer

$(s+t)_{n}=\sum _{k=0}^{n}{n \choose k}(s)_{k}(t)_{n-k}$

En esta forma es claramente reconocible como la variante del cálculo de umbral del teorema del binomio. (Para más información sobre las variantes UMBRAL del teorema del binomio, ver tipo binomial). La identidad de Chu-Vandermonde por lo tanto, puede considerarse como un caso especial del teorema hipergeométrico de Gauss, que toma la forma

$\;_{2}F_{1}(a,b;c;1)={\frac {\Gamma (c)\Gamma (c-a-b)}{\Gamma (c-a)\Gamma (c-b)}}$

donde aparecen la función hipergeométrica $\;_{2}F_{1}$ y la función gamma $\Gamma (n+1)=n!$. La identidad de Chu-Vandermonde se puede recuperar mediante la adopción del cambio a = −n y la aplicación de la identidad

${n \choose k}=(-1)^{k}{k-n-1 \choose k}$

finalmente.

La identidad de Rothe-Hagen es una generalización de esta identidad.

Referencias

• Askey, Richard (1975), Orthogonal polynomials and special functions, Regional Conference Series in Applied Mathematics 21, Philadelphia, PA: SIAM, pp. viii+110 .

• Datos: Q3147827