Identidade de Vandermonde

En combinatoria, a identidade de Vandermonde (ou a convolución de Vandermonde ) é a seguinte identidade para os coeficientes binomiais:

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

para calquera enteiros non negativos r, m, n. A identidade leva o nome de Alexandre-Théophile Vandermonde (1772), aínda que xa era coñecida en 1303 polo matemático chinés Zhu Shijie.

Existe un q-análogo a este teorema chamado identidade q-Vandermonde.

A identidade de Vandermonde pódese xeneralizar de moitas maneiras, incluíndo a identidade

${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}}.$

Probas

Demostración alxébrica

En xeral, o produto de dous polinomios con graos m e n, respectivamente, vén dado por

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

onde usamos a convención de que a_i = 0 para todos os números enteiros i>m e b_j = 0 para todos os números enteiros j > n. Polo teorema binomial,

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

Usando o teorema do binomio para os expoñentes m e n, e despois a fórmula anterior para o produto de polinomios, obtemos

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

Comparando os coeficientes de x^r, temos a identidade de Vandermonde para todos os números enteiros r con 0 ≤ r ≤ m + n. Para os enteiros maiores que r, ambos os dous lados da identidade de Vandermonde son cero debido á definición de coeficientes binomiais.

Proba combinatoria

A identidade de Vandermonde tamén admite unha proba combinatoria de duplo reconto, como segue. Supoñamos que un comité está formado por m homes e n mulleres. De cantas formas se pode formar un subcomité de r membros? A resposta é

${m+n \choose r}.$

A resposta tamén é a suma de todos os valores posibles de k, do número de subcomités formados por k homes e r − k mulleres:

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

Xeneralizacións

Identidade xeneralizada de Vandermonde

Pódese xeneralizar a identidade de Vandermonde do seguinte xeito:

$\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 identidade pódese obter mediante a derivación alxébrica anterior cando se usan máis de dous polinomios, ou mediante un simple argumento de conta dupla.

Por unha banda, un elixe $\textstyle k_{1}$ elementos dun primeiro conxunto de $\textstyle n_{1}$ elementos; despois $\textstyle k_{2}$ doutro conxunto de $\textstyle n_{2}$ elementos, e así para $\textstyle p$ deses conxuntos, en total temos $\textstyle m$ elementos escollidos entre os $\textstyle p$ conxuntos. Un, polo tanto, elixe $\textstyle m$ elementos de$\textstyle n_{1}+\dots +n_{p}$ no lado esquerdo, que tamén é exactamente o que se fai no lado dereito.

Identidade Chu-Vandermonde

Esta identidade xeneralízase a argumentos non enteiros. Neste caso, coñécese como a identidade Chu-Vandermonde e pode tomar distintas formas:

Como convolución de binomiais

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

para s e t sendo valores complexos en xeral e calquera número enteiro non negativo n. Pódese demostrar igual que a proba alxébrica anterior multiplicando as series de $(1+x)^{s}$ e $(1+x)^{t}$ e comparando termos coa serie binomial para $(1+x)^{s+t}$.

Exemplo

${\binom {e+\pi }{2}}={\dfrac {(e+\pi )(e+\pi -1)}{2\cdot 1}}={\dfrac {e^{2}+2e\pi +\pi ^{2}-e-\pi }{2}}.$

${\begin{aligned}\sum _{k=0}^{2}{\binom {e}{2}}{\binom {\pi }{2-k}}&={\binom {e}{0}}{\binom {\pi }{2}}+{\binom {e}{1}}{\binom {\pi }{1}}+{\binom {e}{2}}{\binom {\pi }{0}}\\&={\dfrac {\pi (\pi -1)}{2}}+e\pi +{\dfrac {e(e-1)}{2}}\\&={\dfrac {\pi ^{2}-\pi +2e\pi +e^{2}-e}{2}}.\end{aligned}}$

Con factoriais descendentes

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

Nesta forma é claramente recoñecible como unha variante sombra do teorema binomial.

Exemplo

$(e+\pi )^{\overline {2}}=(e+\pi )(e+\pi -1)=e^{2}+2e\pi +\pi ^{2}-e-\pi .$

${\begin{aligned}\sum _{k=0}^{2}{\binom {2}{k}}e^{\overline {2}}\pi ^{\overline {2-k}}&={\binom {2}{0}}1\cdot e(e-1)+{\binom {2}{1}}\pi e+{\binom {2}{2}}\\&=\pi (\pi -1)+e\pi +e(e-1)\\&=\pi ^{2}-\pi +2e\pi +e^{2}-e.\end{aligned}}$

Como variante do teorema hiperxeométrico de Gauss

A identidade Chu-Vandermonde tamén se pode ver como un caso especial do teorema hiperxeométrico de Gauss, usando a función hiperxeométrica con z = 1 e a = − n.

$\;_{2}F_{1}(-n,b;c;1)={\frac {\Gamma (c)\Gamma (c-b+n)}{\Gamma (c+n)\Gamma (c-b)}}={\dfrac {(c-b)^{\overline {n}}}{c^{\overline {n}}}}$

onde $\;_{2}F_{1}$ é a función hiperxeométrica e $\Gamma (n+1)=n!$ é a función gamma.

${\dfrac {1}{c^{\overline {n}}}}\sum _{k\mathop {=} 0}^{n}{\dbinom {n}{k}}({1-b-k})^{\overline {k}}({c+k})^{\overline {n-k}}={\dfrac {({c-b})^{\overline {n}}}{c^{\overline {n}}}}$.

Xeneralización

A identidade Rothe-Hagen é unha xeneralización adicional desta identidade:

$\sum _{k=0}^{n}{\frac {x}{x+kz}}{x+kz \choose k}{\frac {y}{y+(n-k)z}}{y+(n-k)z \choose n-k}={\frac {x+y}{x+y+nz}}{x+y+nz \choose n}.$

Distribución de probabilidade hiperxeométrica

Se dividimos os dous lados pola expresión da esquerda, de xeito que a suma sexa 1, entón os termos da suma poden interpretarse como probabilidades. A distribución de probabilidade resultante é a distribución hiperxeométrica. Esa é a distribución de probabilidade do número de bólas vermellas en r escollas sen substitución dunha urna que contén n bólas vermellas e m azuis.

Véxase tamén

Outros artigos

• Identidade de Rothe–Hagen