La identidad de Vandermonde

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

${\displaystyle {m+n \elija r}=\sum _{k=0}^{r}{m \elija k}{n \elija rk}}$

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

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

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

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

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

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

donde utilizamos la convención de que a _i  = 0 para todos los enteros i  >  m y 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}.}$

Utilizando 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 \elija r}x^{r}&=(1+x)^{m+n}\\&=(1+x)^{m}(1+x)^{n}\\&={\biggl (}\sum _{i=0}^{m}{m \elija i}x^{i}{\biggr )}{\biggl (}\sum _{j=0}^{n}{n \elija j}x^{j}{\biggr )}\\&=\sum _{r=0}^{m+n}{\biggl (}\sum _{k=0}^{r}{m \elija k}{n \elija rk}{\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 todos los i  >  m y j  >  n , respectivamente.

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

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

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

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

${\displaystyle \sum _{k=0}^{r}{m \elija k}{n \elija rk}.}$

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

${\displaystyle {\binom {r+(m+nr)}{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 se deben realizar r movimientos hacia la derecha y m + n - r movimientos hacia arriba (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 se deben realizar k movimientos hacia la derecha y m − k 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 ), ya que se deben realizar un total de r − k movimientos hacia la derecha y ( m + n − r ) − ( m − k ) movimientos hacia arriba y la longitud del camino debe ser r − k + ( m + n − r ) − ( m − k ) = n . Por lo tanto, hay ${\displaystyle {\binom {m}{k}}}$${\displaystyle {\binom {n}{rk}}}$

${\displaystyle {\binom {m}{k}}{\binom {n}{rk}}}$

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

La identidad de Vandermonde se puede generalizar 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 a través de 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 de un primer conjunto de elementos; luego, de otro conjunto, y así sucesivamente , hasta que se haya elegido un total de elementos de los conjuntos. Por tanto, se eligen elementos del lado izquierdo, lo 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}}$

La identidad se generaliza a argumentos no enteros. En este caso, se la conoce como identidad de Chu-Vandermonde (véase Askey 1975, págs. 59-60) y adopta la forma

${\displaystyle {s+t \elija n}=\sum _{k=0}^{n}{s \elija k}{t \elija nk}}$

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

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

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

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

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

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 $estilo de visualización \;_{2}F_{1}}$${\displaystyle \Gamma (n+1)=n!}$

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

liberalmente.

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

Cuando ambos lados se han dividido por la expresión de la izquierda, de modo que la suma es 1, entonces los términos de la suma pueden interpretarse como probabilidades. La distribución de probabilidad resultante es la distribución hipergeométrica . Es decir, la distribución de probabilidad del número de canicas rojas en r extracciones sin reposición de una urna que contiene n canicas rojas y m canicas azules.

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