La identidad de Vandermonde

Teorema matemático sobre coeficientes binomiales convolucionados

En combinatoria , la identidad de Vandermonde (o convolución de Vandermonde ) es la siguiente identidad para coeficientes binomiales :

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

para cualquier número entero no negativo r , m , n . La identidad lleva el nombre de Alexandre-Théophile Vandermonde (1772), aunque ya era conocida en 1303 por el matemático chino Zhu Shijie . ^[1]

Hay un q -análogo a este teorema llamado q -identidad de Vandermonde .

La identidad de Vandermonde se puede generalizar de numerosas maneras, incluida la identidad

${\displaystyle {n_{1}+\dots +n_{p} \choose m}=\sum _{k_{1}+\cdots +k_{p}=m}{n_{1} \choose k_{1}}{n_{2} \choose k_{2}}\cdots {n_{p} \choose k_{p}}.}$

Pruebas

prueba algebraica

En general, el producto de dos polinomios con grados m y n , respectivamente, viene dado por

${\displaystyle {\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},}$

donde usamos la convención de que a i ₌  0 para todos los enteros i  >  my b _j  = 0 para todos los enteros j  >  n . Por el teorema del binomio ,

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

Usando el teorema del binomio también para los exponentes m y n , y luego la fórmula anterior para el producto de polinomios, obtenemos

${\displaystyle {\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}}}$

donde la convención anterior para los coeficientes de los polinomios concuerda con la definición de los coeficientes binomiales, porque ambos dan cero para todo i  >  m y j  >  n , respectivamente.

Al comparar los coeficientes de x ^r , se sigue la identidad de Vandermonde para todos los números enteros r con 0 ≤  r  ≤  m  +  n . Para números enteros más grandes r , ambos lados de la identidad de Vandermonde son cero debido a la definición de coeficientes binomiales.

Prueba combinatoria

La identidad de Vandermonde también admite una prueba combinatoria de doble contabilización , como sigue. Supongamos que un comité está formado por m hombres yn mujeres . ¿ De cuántas maneras se puede formar un subcomité de r miembros? La respuesta es

${\displaystyle {m+n \choose r}.}$

La respuesta es también la suma de todos los valores posibles de k , del número de subcomités formados por k hombres y r  −  k mujeres:

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

prueba geométrica

Tome una cuadrícula rectangular de r x ( m + n − r ) cuadrados. Hay

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

caminos que comienzan en el vértice inferior izquierdo y, moviéndose solo hacia arriba o hacia la derecha, terminan en el vértice superior derecho (esto se debe a que r movimientos hacia la derecha y m + n - r movimientos hacia arriba deben realizarse (o viceversa) en cualquier orden, y la longitud total del camino es m  +  n ). Llame al vértice inferior izquierdo (0, 0).

Hay caminos que comienzan en (0, 0) y terminan en ( k , m − k ), ya que k se mueve hacia la derecha y m − k se deben realizar movimientos hacia arriba (y la longitud del camino es m ). De manera similar, hay caminos que comienzan en ( k , m − k ) y terminan en ( r , m + n − r ), como un total de r − k movimientos hacia la derecha y ( m + n − r ) − ( m − k ) Se deben realizar movimientos ascendentes y la longitud del camino debe ser r − k + ( m + n − r ) − ( m − k ) = n . Así hay ${\displaystyle {\binom {m}{k}}}$ ${\displaystyle {\binom {n}{r-k}}}$

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

caminos que comienzan en (0, 0), terminan en ( r , m + n − r ) y pasan por ( k , m − k ). Este es un subconjunto de todos los caminos que comienzan en (0, 0) y terminan en ( r , m + n − r ), por lo que la suma de k = 0 a k = r (como el punto ( k , m − k ) es confinado a estar dentro del cuadrado) para obtener el número total de caminos que comienzan en (0, 0) y terminan en ( r , m + n − r ).

Generalizaciones

Identidad de Vandermonde generalizada

Se puede generalizar la identidad de Vandermonde de la siguiente manera:

${\displaystyle \sum _{k_{1}+\cdots +k_{p}=m}{n_{1} \choose k_{1}}{n_{2} \choose k_{2}}\cdots {n_{p} \choose k_{p}}={n_{1}+\dots +n_{p} \choose m}.}$

Esta identidad se puede obtener mediante la derivación algebraica anterior cuando se utilizan más de dos polinomios, o mediante un simple argumento de doble conteo .

Por un lado, se eligen elementos a partir de un primer conjunto de elementos; luego de otro conjunto, y así sucesivamente, a través de dichos conjuntos, hasta que se haya elegido un total de elementos de los conjuntos. Por lo tanto, se eligen elementos del lado izquierdo, que es exactamente lo que se hace en el lado derecho. ${\displaystyle \textstyle k_{1}}$ ${\displaystyle \textstyle n_{1}}$ ${\displaystyle \textstyle k_{2}}$ ${\displaystyle \textstyle p}$ ${\displaystyle \textstyle m}$ ${\displaystyle \textstyle p}$ ${\displaystyle \textstyle m}$ ${\displaystyle \textstyle n_{1}+\dots +n_{p}}$

Identidad Chu-Vandermonde

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

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

para s y t generales de valores complejos y cualquier entero no negativo n . Se puede demostrar siguiendo las líneas de la prueba algebraica anterior multiplicando la serie binomial de y y comparando términos con la serie binomial de . ${\displaystyle (1+x)^{s}}$ ${\displaystyle (1+x)^{t}}$ ${\displaystyle (1+x)^{s+t}}$

Esta identidad puede reescribirse en términos de los símbolos de Pochhammer que caen como

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

en cuya forma es claramente reconocible como una variante umbral del teorema binomial (para más información sobre las variantes umbral del teorema binomial, consulte tipo binomial ). La identidad Chu-Vandermonde también puede considerarse un caso especial del teorema hipergeométrico de Gauss , que establece que

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

donde es la función hipergeométrica y es la función gamma . Se recupera la identidad de Chu-Vandermonde tomando a  = − n y aplicando la identidad ${\displaystyle \;_{2}F_{1}}$ ${\displaystyle \Gamma (n+1)=n!}$

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

liberalmente.

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

La distribución de probabilidad hipergeométrica.

Cuando ambos lados se han dividido por la expresión de la izquierda, de modo que la suma sea 1, entonces los términos de la suma pueden interpretarse como probabilidades. La distribución de probabilidad resultante es la distribución hipergeométrica . Esa es la distribución de probabilidad del número de canicas rojas en r extraídas sin reemplazo de una urna que contiene n canicas rojas ym azules.

Ver también

• La identidad de Pascal.
• Identidad del palo de hockey
• Identidad Rothe-Hagen

Referencias

1. Véase Askey, Richard (1975), Polinomios ortogonales y funciones especiales , Serie de conferencias regionales sobre matemáticas aplicadas, vol. 21, Filadelfia, PA: SIAM, págs. 59–60por la historia.