Uma proposição da análise combinatória

Quaisquer que sejam os inteiros  k  e n tais que 0\leq k \leq n,  tem-se

\displaystyle\sum_{i=k}^{n}\dbinom{n}{i}^{2}\dbinom{i}{k}=\dbinom{n}{k}\dbinom{2n-k}{n}

Demonstração:

Comecemos por reparar que poderíamos ter escolhido para limite inferior do somatório 0 , em vez de k, porque para i<k, \binom{i}{k}=0, por convenção usual.

O segundo membro (lado direito) conta o número de maneiras diferentes de escolher k elementos dum conjunto, tal como S=\left\{ s_{1},s_{2},\cdots,s_{n}\right\} com n elementos e, ao mesmo tempo, n elementos doutro conjunto, por exemplo X=\left\{ x_{1},x_{2},\ldots,x_{n},x_{n+1},\ldots,x_{2n-k}\right\} com 2n-k elementos.

Quanto ao primeiro membro, considerem-se dois subconjuntos de X disjuntos (sem elementos comuns), um X_{1}=\left\{x_{1},x_{2},\ldots,x_{n}\right\}  com n  elementos, e outro X_{2}=\left\{x_{n+1},\ldots,x_{2n-k}\right\} com 2n-k elementos, tais que X_{1}\cup X_{2}=X.

Escolhamos agora n elementos de X pertencendo i deles a X_{1} e n-i a X_{2}, com 0\leq i\leq n.

(a) Há \dbinom{n}{i} maneiras diferentes de escolher i elementos entre os n de X_{1};

(b) há \dbinom{n-k}{n-i}=\dbinom{n-k}{i-k} maneiras diferentes de escolher n-i elementos entre os n-k de X_{2};

(c) daqui decorre que, para um dado i, há \dbinom{n}{i}\dbinom{n-k}{i-k} maneiras distintas de seleccionar esses n elementos de X. Assim, cada parcela, \dbinom{n}{i}\dbinom{n-k}{i-k}\dbinom{n}{k} conta o número de maneiras diferentes de escolher n elementos de X (dos quais i\in X_{1} ) e, simultaneamente, k de S. Somando, para todos os possíveis valores de i , estas parcelas, obtemos o número total

\displaystyle\sum_{i=0}^{n}\dbinom{n}{i}\dbinom{n-k}{i-k}\dbinom{n}{k}=\displaystyle\sum_{i=0}^{n}\dbinom{n}{i}^{2}\dbinom{i}{k}=\sum_{i=k}^{n}\dbinom{n}{i}^{2}\dbinom{i}{k}

A primeira igualdade é justificada por

 \dbinom{n}{k}\dbinom{n-k}{i-k}=\dbinom{n}{i}\dbinom{i}{k}

 e a segunda pela observação inicial.

É claro que as duas contagens, a directa representada pelo produto do segundo membro e a indirecta, pela soma do primeiro (lado esquerdo) hão-de ser iguais, o que mostra

 \displaystyle\sum_{i=k}^{n}\dbinom{n}{i}^{2}\dbinom{i}{k}=\dbinom{n}{k}\dbinom{2n-k}{n},

 como pretendíamos. \blacksquare

Sobre Américo Tavares

eng. electrotécnico reformado / retired electrical engineer
Esta entrada foi publicada em Combinatória, Demonstração, Identidade matemática, Matemática, Teorema / Teoria com as etiquetas , , . ligação permanente.

Deixe uma Resposta

Preencha os seus detalhes abaixo ou clique num ícone para iniciar sessão:

Logótipo da WordPress.com

Está a comentar usando a sua conta WordPress.com Terminar Sessão / Alterar )

Imagem do Twitter

Está a comentar usando a sua conta Twitter Terminar Sessão / Alterar )

Facebook photo

Está a comentar usando a sua conta Facebook Terminar Sessão / Alterar )

Google+ photo

Está a comentar usando a sua conta Google+ Terminar Sessão / Alterar )

Connecting to %s