Re: [obm-l] numeros binomiais, conjectura

[Carlos Yuzo Shine <cyshine@xxxxxxxxx>]

Uma outra maneira de provar é usando combinatória:

Considere t caixinhas C_1, C_2, ..., C_t, sendo que a
caixinha C_i tem A_i objetos, ou seja, temos A = A_1 +
A_2 +...+ A_t objetos.

Suponha que queiramos retirar um total de n objetos
dessas caixas, sem nenhuma restrição.

Podemos fazer isso retirando N_i objetos da caixa C_i,
de modo que N_1 + N_2 + ... + N_t = n. O número de
maneiras de retirar os objetos dessa maneira é igual a
produto(C(A_j,n_j),j=1..t.

O total de maneiras de retirar n objetos é obtido
considerando todas as possibilidades para os números
naturais N_1, N_2, ..., N_t tais que N_1 + N_2 + ... +
N_t = n; então, esse total é
  soma(produto(C(A_j,n_j),j=1..t),n_1+...+n_t=n).

Mas podemos escolher os n objetos da seguinte maneira:
retire todos os A objetos de suas caixas e escolha,
dentre eles, os seus n objetos. Há C(A,n) maneiras de
se fazer isso. Assim, o total acima é também igual a  
C(A,n), ou seja,

soma(produto(C(A_j,n_j),j=1..t),n_1+...+n_t=n)=C(A,n).

A maneira que o Gugu propôs, na verdade, é muito
parecida com a que escrevi; ele faz a mesma contagem
dupla acima utilizando séries formais (as famosas
funções geratrizes). Tem um artigo na Eureka! 12 (não
sei ao certo se o número é esse mesmo) falando
exatamente sobre esse assunto. Vale a pena ler.

[]'s
Shine

--- Carlos Gustavo Tamm de Araujo Moreira
<gugu@impa.br> wrote:

>    Pelo que eu entendi, os A_i são dados e os N_i
> variam sobre as t-uplas de
> naturais cuja soma e' n. Uma prova relativamente
> curta e' a seguinte:
> escreva (1+x)^A=produto((1+x)^A_j,j=1..t) e olhe
> para o coeficiente de x^n
> em cada um dos dois lados: eles são C(A,n) e
> soma(produto(C(A_j,n_j),j=1..t),n_1+...+n_t=n),
> respectivamente.
>    Abraços,
>               Gugu
>  
> >
> >Sejam 
> >
> >n = n_1 + n_2 +...+ n_t 
> >A = A_1 + A_2 +...+ A_t
> >
> >Entao
> >
> >soma(produto(C(A_j,n_j),j=1..t),n_1+...+n_t=n) =
> >C(A,n)
> >
> >Alguem pode me dizer se essa conjectura eh
> verdadeira?
> >Se for, ela jah foi provada?
> >Alguns casos particulares sao faceis de ver, por
> >exemplo:
> >
> >C(A+B,2)=C(A,2)C(A,0)+C(A,1)C(B,1)+C(A,0)C(B,2)
> >
> >Supondo que:
> >
> >C(A+B,n)=soma(C(A,i)C(B,n-i),i=1..n)
> >
> >Eh facil mostrar que 
> >
> >C(A+B+C,n)=C((A+B)+C,n)=
> >=soma(C(A,i)C(B,j)C(C,k),0<=i,j,k<=n,i+j+k=n)
> >
> >Ah! O caso C(A+B,n)=soma(C(A,i)C(B,n-i),i=1..n)
> >para n=3 jah verifiquei e estah certo, isto eh:
> >
> >C(A+B,3)=C(A,3)+C(A,2)C(B,1)+C(A,1)C(B,2)+C(B,3)
> >
> >Abra,cos!
> >
> >
> >=======================================
> >geocities.yahoo.com.br/mathfire2001
> >Enciclopedia de Matematica - Aulas
> >Formulas para primos - Grupos de Estudo
> >Projeto Matematica para Todos
> >mathfire2001@yahoo.com.br
> >=======================================
> >
> >__________________________________________________
> >Converse com seus amigos em tempo real com o Yahoo!
> Messenger 
> >http://br.download.yahoo.com/messenger/ 
>
>=========================================================================
> >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
>
>=========================================================================
> >
> 
>
=========================================================================
> 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
>
=========================================================================
> 


__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.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
=========================================================================