[obm-l] A outra diagonal do triângulo de Pascal

[Carlos Yuzo Shine <cyshine@xxxxxxxxx>]

Olá,

Hoje, numa aula de preparação, os alunos e o Edmilson
provaram um fato interessante (já conhecido): a soma
da diagonal "ao contrário" do triângulo de Pascal dá
Fibonacci.

Só relembrando: o triângulo de Pascal é formado pelos
binomiais.

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

As "diagonais ao contrário" são: 1; 1; 1 1; 1 2; 1 3
1; 1 4 3;... Observe que as somas são 1; 1; 2; 3; 5;
8;... que coincide com a seqüência de Fibonacci.

Colocando de modo algébrico:
Soma{k=0 a n}binom(n-k,k) = F(n+1),
em que F(0) = 0, F(1) = 1 e F(m+2) = F(m+1) + F(m).

Mas o que foi mais interessante foi a demonstração
dada hoje, que é uma contagem dupla que nem eu nem o
Edmilson vimos em nenhum livro.

É conhecido que o número de maneiras de se guardar
dominós 2 x 1 em uma caixinha 2 x n é igual a F(n+1).
Isso pode ser demonstrado utilizando o fato de que o
número de maneiras de se preencher uma caixinha 2 x
(n+2) é o número de maneiras de se preencher uma
caixinha 2 x (n+1) (no caso em que no final da
caixinha 2 x (n+2) há um dominó na vertical) somado ao
número de maneiras de se preencher uma caixinha 2 x n
(no caso em que no final da caixinha 2 x (n+2) há um
par de dominós na posição horizontal).

Mas podemos contar esse número "na raça": se temos k
pares de dominós na posição horizontal, temos n-2k
dominós na vertical. O número de maneiras de se
ordenar os dominós nessas posições é igual ao número
de anagramas com k H's e n-2k V's que é binom(n-k,k).
Somando tudo com k variando de 0 a n, obtemos Soma{k=0
a n}binom(n-k,k).

Assim, tal soma é igual a F(n+1).

[]'s
Shine

__________________________________
Do you Yahoo!?
The New Yahoo! Search - Faster. Easier. Bingo.
http://search.yahoo.com
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================