[obm-l] Numeros de Catalan

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxx>]

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