Identidade de Vandermonde

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

(\binom{m + n}{r}) = \sum_{k = 0}^{r} (\binom{m}{k}) (\binom{n}{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.^[1]

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

(\binom{n_{1} + \dots + n_{p}}{m}) = \sum_{k_{1} + \dots + k_{p} = m} (\binom{n_{1}}{k_{1}}) (\binom{n_{2}}{k_{2}}) \dots (\binom{n_{p}}{k_{p}}) .

Probas

Demostración alxébrica

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

(\sum_{i = 0}^{m} a_{i} x^{i}) (\sum_{j = 0}^{n} b_{j} x^{j}) = \sum_{r = 0}^{m + n} (\sum_{k = 0}^{r} a_{k} b_{r - k}) 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} (\binom{m + n}{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{matrix} \sum_{r = 0}^{m + n} (\binom{m + n}{r}) x^{r} & = (1 + x)^{m + n} \\ = (1 + x)^{m} (1 + x)^{n} \\ = (\sum_{i = 0}^{m} (\binom{m}{i}) x^{i}) (\sum_{j = 0}^{n} (\binom{n}{j}) x^{j}) \\ = \sum_{r = 0}^{m + n} (\sum_{k = 0}^{r} (\binom{m}{k}) (\binom{n}{r - k})) x^{r}, \end{matrix}

Comparando os coeficientes de x^{Modelo:Espazosr}, 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 é

(\binom{m + n}{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} (\binom{m}{k}) (\binom{n}{r - k}) .

Xeneralizacións

Identidade xeneralizada de Vandermonde

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

\sum_{k_{1} + \dots + k_{p} = m} (\binom{n_{1}}{k_{1}}) (\binom{n_{2}}{k_{2}}) \dots (\binom{n_{p}}{k_{p}}) = (\binom{n_{1} + \dots + n_{p}}{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 $k_{1}$ elementos dun primeiro conxunto de $n_{1}$ elementos; despois $k_{2}$ doutro conxunto de $n_{2}$ elementos, e así para $p$ deses conxuntos, en total temos $m$ elementos escollidos entre os $p$ conxuntos. Un, polo tanto, elixe $m$ elementos de $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 ^[1] e pode tomar distintas formas:

Como convolución de binomiais

(\binom{s + t}{n}) = \sum_{k = 0}^{n} (\binom{s}{k}) (\binom{t}{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 + π}{2}) = \frac{(e + π) (e + π - 1)}{2 \cdot 1} = \frac{e^{2} + 2 e π + π^{2} - e - π}{2} .$

$\begin{matrix} \sum_{k = 0}^{2} (\binom{e}{2}) (\binom{π}{2 - k}) & = (\binom{e}{0}) (\binom{π}{2}) + (\binom{e}{1}) (\binom{π}{1}) + (\binom{e}{2}) (\binom{π}{0}) \\ = \frac{π (π - 1)}{2} + e π + \frac{e (e - 1)}{2} \\ = \frac{π^{2} - π + 2 e π + e^{2} - e}{2} . \end{matrix}$

Con factoriais descendentes

(s + t)^{\underline{n}} = \sum_{k = 0}^{n} (\binom{n}{k}) s^{\underline{k}} t^{\underline{n - k}}

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

Exemplo

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

$\begin{matrix} \sum_{k = 0}^{2} (\binom{2}{k}) e^{\overline{2}} π^{\overline{2 - k}} & = (\binom{2}{0}) 1 \cdot e (e - 1) + (\binom{2}{1}) π e + (\binom{2}{2}) \\ = π (π - 1) + e π + e (e - 1) \\ = π^{2} - π + 2 e π + e^{2} - e . \end{matrix}$

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{Γ (c) Γ (c - b + n)}{Γ (c + n) Γ (c - b)} = \frac{(c - b)^{\overline{n}}}{c^{\overline{n}}}

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

\frac{1}{c^{\overline{n}}} \sum_{k = 0}^{n} (\binom{n}{k}) (1 - b - k)^{\overline{k}} (c + k)^{\overline{n - k}} = \frac{(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 + k z} (\binom{x + k z}{k}) \frac{y}{y + (n - k) z} (\binom{y + (n - k) z}{n - k}) = \frac{x + y}{x + y + n z} (\binom{x + y + n z}{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.

Notas

Modelo:Reflist

Véxase tamén

Modelo:Commonscat

Outros artigos

Identidade de Rothe–Hagen

Modelo:Control de autoridades

↑ ^1,0 ^1,1 Modelo:Cita libro.

[askey-1] 1,0 ^1,1 Modelo:Cita libro.

[1]

Identidade de Vandermonde

Índice

Probas

Demostración alxébrica

Proba combinatoria

Xeneralizacións

Identidade xeneralizada de Vandermonde

Identidade Chu-Vandermonde

Como convolución de binomiais

Exemplo

Con factoriais descendentes

Exemplo

Como variante do teorema hiperxeométrico de Gauss

Xeneralización

Distribución de probabilidade hiperxeométrica

Notas

Véxase tamén

Outros artigos

Menú de navegación

Identidade de Vandermonde

Probas

Demostración alxébrica

Proba combinatoria

Xeneralizacións

Identidade xeneralizada de Vandermonde

Identidade Chu-Vandermonde

Como convolución de binomiais

Exemplo

Con factoriais descendentes

Exemplo

Como variante do teorema hiperxeométrico de Gauss

Xeneralización

Distribución de probabilidade hiperxeométrica

Notas

Véxase tamén

Outros artigos

Menú de navegación

Procura