A identidade de Vandermonde - Vandermonde's identity

Em análise combinatória , a identidade de Vandermonde (ou convolução de Vandermonde ) é a seguinte identidade para coeficiente binomial :

${\ Displaystyle {m + n \ escolher R} = \ _ {soma k = 0} ^ {r} {m \ escolher k} {n \ escolher RK}}$

para quaisquer não negativos inteiros de r , m , n . A identidade é nomeado após Alexandre-Théophile Vandermonde (1772), embora já era conhecido em 1303 pelo matemático chinês Zhu Shijie (Chu Shi-Chieh). Veja Askey 1975, pp. 59-60 para a história.

Há um q -analog para este teorema chamado q identidade -Vandermonde .

A identidade de Vandermonde pode ser generalizada de várias maneiras, incluindo a identidade

${\ Displaystyle {n_ {1} + \ pontos + n_ {p} \ escolher m} = \ soma _ {K_ {1} + \ cdots + K_ {p} = M} {n_ {1} \ escolher K_ {1 }} {n_ {2} \ escolher k_ {2}} \ cdots {n_ {p} \ escolher k_ {p}}}$.

provas

prova algébrica

Em geral, o produto de dois polinómios com graus de m e n , respectivamente, é dada pela

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

onde usamos a convenção de que um _i  = 0 para todos os inteiros de i  >  m e b _j  = 0 para todos os números inteiros j  >  n . Pelo teorema binomial ,

${\ Displaystyle (1 + x) ^ {m + n} = \ _ {soma r = 0} ^ {m + n} {m + n \ r} escolher x ^ {r}.}$

Utilizando o teorema binomial também para o expoentes m e n , e, em seguida, a fórmula acima para o produto de polinómios, obtemos

${\ Displaystyle {\ begin {alinhados} \ soma _ {r = 0} ^ {m + n} {m + n \ escolher r} x ^ {r} & = (1 + x) ^ {m + n} \ \ & = (1 + x) ^ {m} (1 + x) ^ {n} \\ & = {\ biggl (} \ soma _ {i = 0} ^ {m} {m \ escolher i} x ^ {i} {\ biggr)} {\ biggl (} \ _ {soma de j = 0} ^ {n} {n \ j escolher} x ^ {j} {\ biggr)} \\ & = \ _ {soma r = 0} ^ {m + n} {\ biggl (} \ soma _ {k = 0} ^ {r} {m \ escolher k} {n \ escolher RK} {\ biggr)} x ^ {r}, \ final {alinhados}}}$

onde a convenção acima para os coeficientes dos polinómios concorda com a definição dos coeficientes binomial, porque ambos dão zero para todos os i  >  m e j  >  n , respectivamente.

Ao comparar os coeficientes de x ^r , a identidade de Vandermonde seguinte para todos os inteiros de r com 0 ≤  r  ≤  m  +  n . Para inteiros maiores r , ambos os lados da identidade de vandermonde são zero devido à definição do coeficiente binomial.

prova combinatória

A identidade de Vandermonde também admite uma combinatória prova dupla contagem , como segue. Suponha que uma comissão é composta por m homens e n mulheres. De quantas maneiras pode uma subcomissão de r membros ser formado? A resposta é

${\ Displaystyle {m + n \ escolher r}.}$

A resposta também é a soma de todos os valores possíveis de k , do número de subcomissões compostas de k homens e r  -  k mulheres:

${\ Displaystyle \ soma _ {k = 0} ^ {r} {m \ escolher k} {n \ escolher RK}.}$

prova geométrica

Dê uma grade retangular de rx (m + NR) quadrados. tem

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

caminhos que começam na parte inferior esquerda vértice e, movendo-se apenas para cima ou para a direita, a extremidade no vértice superior direito (isto é porque r movimentos do direito e m + nr -se move deve ser feita (ou vice-versa), em qualquer ordem, e o total comprimento de percurso é m + n ). Ligue para o vértice inferior esquerdo (0,0) .

Existem caminhos a partir de (0,0) que a extremidade (K, MK) , a partir de k movimentos do direito e mk se move para cima deve ser feita (e o comprimento de percurso é m ). Da mesma forma, existem caminhos a partir de (K, MK) que terminam em (R, M + nr) , como um total de rk movimentos do direito e (m + nr) - (MK) se move para cima deve ser feita e o comprimento do percurso deve ser rk + (m + nr) - (MK) = n . Assim, existem ${\ Displaystyle {\ binom {m} {k}}}$${\ Displaystyle {\ binom {n} {rk}}}$

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

caminhos que começam em (0,0) , na extremidade (R, M + nr) , e passar por (K, MK) . Este é um subconjunto de todos os caminhos que começam em (0,0) e terminam em (R, M + nr) , tal que a soma de k = 0 para k = r (como o ponto (K, MK) está confinada a estar dentro o quadrado) para se obter o número total de caminhos que começam em (0,0) e terminam em (R, m + nr) .

generalizações

A identidade de generalizada Vandermonde

Pode-se generalizar a identidade de Vandermonde da seguinte forma:

${\ Displaystyle \ soma _ {K_ {1} + \ cdots + K_ {p} = M} {n_ {1} \ escolher K_ {1}} {n_ {2} \ escolher K_ {2}} \ cdots {n_ {p} \ escolher K_ {p}} = {n_ {1} + \ + pontos n_ {p} \ escolher m}}$.

Esta identidade pode ser obtido através da derivação algébrica acima, quando mais do que dois polinómios são utilizados, ou por meio de uma simples contagem dupla argumento.

Por um lado, um escolhe elementos fora de um primeiro conjunto de elementos; em seguida, para fora de um outro conjunto e assim por diante, através de tais conjuntos, até um total de elementos foram escolhidos de entre os conjuntos. Um, portanto, escolhe elementos fora no lado esquerdo, que é também exatamente o que é feito no lado direito. ${\ 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}}$

identidade Chu-Vandermonde

A identidade generaliza a argumentos não inteiros. Neste caso, ela é conhecida como a identidade Chu-Vandermonde (ver ASKEY 1975, pp. 59-60 ) e toma a forma

${\ Displaystyle {s + t \ escolher n} = \ _ {soma k = 0} ^ {n} {s \ escolher k} {t \ escolher NK}}$

para gerais de valor complexo s e t e qualquer número inteiro não negativo n . Pode ser provado ao longo das linhas da prova algébrica acima por multiplicando a série binomial para e e comparando termos com a série binomial para . ${\ Displaystyle (1 + x) ^ {s}}$${\ Displaystyle (1 + x) ^ {t}}$${\ Displaystyle (1 + x) ^ {s + t}}$

Esta identidade pode ser re-escrita em termos de queda dos símbolos Pochhammer como

${\ Displaystyle (s + t) _ {n} = \ _ {soma k = 0} ^ {n} {n \ escolher k} (s) _ {k} (t) _ {NK}}$

de forma que ela é claramente reconhecível como um umbral variante do teorema binomial (para mais informações sobre as variantes de umbral o teorema binomial, ver tipo binomial ). A identidade Chu-Vandermonde também pode ser visto como um caso especial do teorema hipergeométrica de Gauss , que afirma que

${\ Displaystyle \; _ {2} F_ {1} (a, b, c; 1) = {\ frac {\ Gama (c) \ Gama (CAB)} {\ Gama (CA) \ Gama (cb)} }}$

onde representa a função hipergeométrico e é a função gama . Um recupera a identidade Chu-Vandermonde tomando um  = - n e aplicando a identidade ${\ Displaystyle \; _ {2} F_ {1}}$${\ Displaystyle \ Gama (n + 1) = n!}$

${\ Displaystyle {n \ escolher k} = (- 1) ^ {k} {KN-1 \ escolher k}}$

liberalmente.

A identidade Rothe-Hagen é mais uma generalização dessa identidade.

A distribuição de probabilidade hipergeométrico

Quando ambos os lados foram divididos pela expressão do lado esquerdo, de modo que a soma é 1, então os termos da soma pode ser interpretada como probabilidades. O resultante distribuição de probabilidade é a distribuição hipergeométrico . Que é a distribuição de probabilidade do número de esferas vermelhas em r chama sem substituição de uma urna contendo n vermelhos e m berlindes azuis.

Veja também

• A identidade de Pascal
• identidade Hockey-stick
• identidade Rothe-Hagen

Referências

• ASKEY, Richard (1975), polinómios ortogonais e funções especiais , Conference Series regional in Applied Mathematics, 21 , Philadelphia, PA: SIAM, pp viii + 110.