domingo, 3 de abril de 2011

Demonstração via combinatória (Fórmula de Euler)

[;C^{0}_{m}C^{p}_{h}+C^{1}_{m}C^{p-1}_{h}+C^{2}_{m}C^{p-2}_{h}+...+C^{p}_{m}C^{0}_{h}=C^{p}_{m+h} ;]

Vamos provar essa bela identidade utilizando apenas argumentos combinatórios.

Quantos subconjuntos com m mulheres e h homens temos em um grupo de p pessoas? Podemos pensar de duas formas diferentes: somando cada subconjunto possível ou simplesmente escolhendo p pessoas das m+h totais. 
De fato, o número de subgrupos nos quais há exatamente k mulheres é: [;C^{k}_{m}C^{p-k}_{h};]. Logo:

[;\sum^{p}_{k=0}{C^{k}_{m}C^{p-k}_{h}}=C^{p}_{m+h};]

É evidente que poderíamos fazer uma demonstração simples aplicando o Princípio da Indução Finita ou a seguinte identidade:

[;(1+x)^{m}\ .\ (1+x)^{h}=(1+x)^{m+h};]

O termo genérico do desenvolvimento de [;(1+x)^{m+h};] é [;T_{p+1}=C^{p}_{m+h}x^{p};], o que implica em o coeficiente em [;x^p;] ser [;C^{p}_{m+h};]. Por outro lado:

[;(1+x)^{h}=C^{0}_{h}+C^{1}_{h}x^1+C^{2}_{h}x^2+...+C^{h}_{h}x^{h};]

[;(1+x)^{m}=C^{0}_{m}+C^{1}_{m}x^1+C^{2}_{m}x^2+...+C^{m}_{m}x^{m};] 

O coeficiente de [;x^p;]  no produto [;(1+x)^{h}(1+x)^m;] é:
 
[;C^{0}_{m}C^{p}_{h}+C^{1}_{m}C^{p-1}_{h}+C^{2}_{m}C^{p-2}_{h}+...+C^{p}_{m}C^{0}_{h};]

Logo:
 
[;\sum^{p}_{k=0}{C^{k}_{m}C^{p-k}_{h}}=C^{p}_{m+h};]


Corolário (Fórmula de Lagrange) [;(C^{0}_{n})^2+(C^{1}_{n})^2+...+(C^{n}_{n})^2=C^{n}_{2n};]

Demonstração: Basta aplicar m=h=p=n na fórmula de Euler:

[;C^{0}_{n}C^{n}_{n}+C^{1}_{n}C^{n-1}_{n}+C^{2}_{n}C^{n-2}_{n}+...+C^{n}_{n}C^{n}_{n}=C^{n}_{2n} ;]

Mas [;C^{k}_{n}=C^{n-k}_{n};]. Logo:

[;\sum^{n}_{k=0}(C^{k}_{n})^2=C^{n}_{2n};]

Referência bibliográfica:
MORGADO, A.C. Análise Combinatória e Probabilidade. 9a ed. Rio de Janeiro: SBM
às

Um comentário:

  1. Unknown3 de agosto de 2015 às 08:14

    Olá pesoal do blog!

    Tentei visualizar os códigos em dois navegadores distintos: chrome e mozilla porém sem sucesso, sendo que no último uso o greasemonkey, não sei o que fazer, alguém pode me ajudar?!

    ResponderExcluir