Re: [obm-l] Numeros de Catalan (era Problemas em Aberto II)

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

On Sun, Mar 02, 2003 at 10:17:00AM -0300, Nicolau C. Saldanha wrote:
> On Thu, Feb 27, 2003 at 03:04:44PM -0300, Cláudio (Prática) wrote:
> > 15. 
> >  
> >  _ _ _ _ _ _ _ 1 2 ... n _
> >  _|_| |_|_| |_|_|_|_|_|_|_
> >  B   \_\ /_/      A
> >        \_|_/
> >         |_|
> >         |_|
> >         |_| C
> >         |o|
> >  
> >  Imagine que o 'desenho' acima é uma linha férrea,
> >  aonde o segmento B é extensão do segmento A e o
> >  segmento C se conecta com ambos segmentos.
> >  Os numeros no segmento A representam n vagões
> >  _soltos_ e enumerados.
> >  Os vagoes podem se mover de A -> B, A -> C e C -> B,
> >  mas nunca de C -> A nem B -> A nem B -> C..
> >  
> >  De quantas formas eh possivel reagrupar os vagões no
> >  segmento B?
> >  
> >  (há espaço suficiente para n vagões tanto em A,
> >  quanto em B e em C)
> 
> Estes são os merecidamente famosos números de Catalan,...

Depois de mandar a resposta anterior achei que valia a pena mandar outra
mais coerente com o nome da lista, simplesmente demonstrando de forma elementar
uma fórmula para a resposta.

Antes de mais nada observe que a passagem A -> B é desnecessária;
basta fazer A -> C seguido imediatamente de C -> B.

Encodifique uma passagem de vagões por uma poligonal de (0,0) a (n+1,n)
onde uma passagem A -> C é representada por um traço para cima
(de (x,y) para (x,y+1)) e uma passagem C -> B por um traço para a direita
(de (x,y) para (x+1,y)) e acrescente no final um último traço para a direita.
Observe que esta trajetória está toda no semiplano nx <= (n+1)y.

Um subconjunto de n elementos de {1,2,...,2n+1} também é representado
por uma palavra de n Y's e (n+1) X's ou por uma trajetória de (0,0) a (n+1,n)
(nos elementos você sobe, nos não-elementos você anda para a direita). 
Identifique as palavras por permutação cíclica, assim formando
binom(2n+1,n)/(2n+1) = binom(2n,n)/(n+1) classes de (2n+1) elementos cada.
Em cada classe há exatamente uma trajetória que fica no semiplano nx <= (n+1)y.

Assim a resposta é binom(2n,n)/(n+1), o número de Catalan...

[]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
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================