Re: [obm-l] numeros binomiais, conjectura

[Carlos Gustavo Tamm de Araujo Moreira <gugu@xxxxxxx>]

   Este belo argumento combinatório do Shine generaliza a idéia do Dirichlet
e da' uma prova do resultado quando os A_j e os n_j são naturais. Aproveito 
para dar outra prova deste resultado, agora por indução, usando a relação de
Stiffel C(n+1,k+1)=C(n,k+1)+C(n,k). Lembremos que queremos provar que, para
A = A_1+A_2+...+A_t, soma(produto(C(A_j,n_j),j=1..t),n_1+...+n_t=n)=C(A,n) (os 
A_i são dados e os n_i variam sobre as t-uplas de naturais cuja soma e' n). 
Da' para provar isso por indução em A+n+t: Se A+n+t=1, t=1, A=n=0 e os dois 
lados valem 1. Em geral, supondo A_1>0, temos, por hipótese de indução,
C(A-1,n)=soma(C(A_1-1,n_1).produto(C(A_j,n_j),j=2..t),n_1+...+n_t=n) e 
C(A-1,n-1)=soma(C(A_1-1,n_1-1).produto(C(A_j,n_j),j=2..t),n_1>0,n_1+...+n_t=n-1).
Note que, se n_1=0, C(A_1,n_1)=1=C(A_1-1,n_1). Assim, como, para n_1>0,
C(A_1-1,n_1)+C(A_1-1,n_1-1)=C(A_1,n_1), somando as duas igualdades, obtemos 
C(A,n)=C(A-1,n)+C(A-1,n-1)=soma(C(A_1,n_1).produto(C(A_j,n_j),j=2..t),n_1+...+n_t=n)=
=soma(produto(C(A_j,n_j),j=1..t),n_1+...+n_t=n). O caso A_1=0 segue de
trocar t por t-1, o que termina a prova por indução. 
   Entretanto o Eric havia dito que queria provar o resultado supondo os A_j
complexos. E' possível deduzir o caso complexo do caso natural (exercício!). 
Por outro lado, vale a pena observar que esse meu argumento com funções
geratrizes funciona no caso complexo, definindo, para |x|<1 e A complexo,
(1+x)^A=e^(A.log(1+x)), onde log(1+x)=x-x^2/2+x^3/3-x^4/4+... (e, para todo
z complexo, e^z=1+z+z^2/2+z^3/6+...=soma(k=0 a infinito)(z^k/k!)). Além
disso, ainda vale, para |x|<1, (1+x)^A=1+Ax+(A(A-1)/2).x^2+...=
=soma(k=0 a infinito)(C(A,k).x^k).
   Abraços,
             Gugu

>
>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
>=========================================================================
>

=========================================================================
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
=========================================================================