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 é <[EMAIL PROTECTED]> =========================================================================