Re: [obm-l] Numeros de Catalan

["Luis Lopes" <llopes@xxxxxxxxxxxxx>]

Sauda,c~oes,

Oi Claudio,

> > Para 0 <= b <= 1/4:
> > SOMA(m>=0) Binom(2m,m)/(m+1) * b^m  =  (1 - raiz(1 - 4b))/2

Vc esqueceu do b no denominador.

SOMA(m>=0) Binom(2m,m)/(m+1) * b^m  =
(1 - raiz(1 - 4b))/2b

como pode ser visto no artigo mandado pelo N.

> > Uma outra consequencia eh que se expandirmos (1 - raiz(1 - 4x))/2 em
serie,
> > obteremos justamente a serie formal cujos coeficientes sao os numeros de
> > Catalan

Agora foi o x no denominador:

(1 - raiz(1 - 4x))/2x

[]'s
Luis



-----Mensagem Original-----
De: "Nicolau C. Saldanha" <nicolau@mat.puc-rio.br>
Para: <obm-l@mat.puc-rio.br>
Enviada em: terça-feira, 25 de novembro de 2003 09:22
Assunto: [obm-l] Numeros de Catalan


> On Mon, Nov 24, 2003 at 07:05:55PM -0200, Claudio Buffara wrote:
> > Nao sei se foi discutido ou nao, mas me parece que esse problema estah
> > relacionado aos numeros de Catalan.
> >
> > Eh facil ver que o jogo soh pode parar apos um numero impar de
lancamentos.
> > Se o jogo para no (2m+1)-esimo lancamento, entao terao sido obtidas m+1
> > caras e m coroas. Alem disso, ateh o 2m-esimo lancamento (que tem que
ter
> > dado cara), as caras nunca estiveram na frente.
> > O numero de maneiras disso acontecer eh Binom(2m,m)/(m+1) = m-esimo
numero
> > de Catalan. Logo, a probabilidade do jogo acabar no (2m+1)-esimo
lancamento
> > eh igual a P(2m+1) = Binom(2m,m)/(m+1) * p^m * (1-p)^(m+1).
> >
> > A probabilidade do jogo nao terminar nunca serah igual a:
> > 1 - (P(1) + P(3) + P(5) + ... )
>
> De fato, números de Catalan aparecem em muitíssimos problemas.
> Eu recomendo a leitura de
> http://www-math.mit.edu/~rstan/ec/catadd.ps.gz
> onde há 36 páginas de interpretações combinatórias diferentes
> para esta seqüência. O autor é Richard Stanley e este material
> está relacionado com os excelentes livros Enumerative Combinatorics, vols
1, 2.
>
> > Eh interessante observar que, para p >= 1/2:
> > P(1) + P(3) + P(5) + ... = (1-p)/p
> >
> > Ou seja, que:
> > (1-p) * SOMA(m>=0) Binom(2m,m)/(m+1) * (p*(1-p))^m  =  (1-p)/p ==>
> >
> > Quando p varia de 1/2 a 1, p*(1-p) varia de 1/4 a 0.
> > Fazendo b = p*(1-p) obtemos um resultado que talvez seja interessante
por si
> > soh (o que voce acha, Luis Lopes?):
> >
> > Para 0 <= b <= 1/4:
> > SOMA(m>=0) Binom(2m,m)/(m+1) * b^m  =  (1 - raiz(1 - 4b))/2
> >
> > Para b > 1/4, o termo geral nao tende a zero (teste da razao ou
Stirling) e
> > a serie diverge.
> >
> > Uma outra consequencia eh que se expandirmos (1 - raiz(1 - 4x))/2 em
serie,
> > obteremos justamente a serie formal cujos coeficientes sao os numeros de
> > Catalan.
>
> Esta é uma das maneiras clássicas de obter uma fórmula para os números de
> Catalan: faça a expansão de (1+x)^(1/2) usando o binômio de Newton:
>
> (1+x)^(1/2) = 1 + binom(1/2,1) x + ... + binom(1/2,k) x^k + ...
>
> onde
>
> binom(1/2,k) = (1/2)(1/2 - 1)(1/2 - 2)...(1/2 - (k-1))/k!
>              = (-1)^(k-1)/2^k  1*3*5*...*(2k-3)/k!
>              = (-1)^(k-1)/2^(2k-1) (2k-2)!/((k-1)!k!)
>              = (-1)^(k-1)/2^(2k-1) binom(2k-2,k-1)/k
>
> e os números de Catalan apareceram...
>
> []s, N.
>
> =========================================================================
> 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
=========================================================================