Re: A importancia dos Mestres

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

On Wed, 9 May 2001, Paulo Santa Rita wrote:

> Ola Pessoal,
> 
> Nao sei se voces perceberam, mas os Prof que comumente orientam a Nossa 
> Lista estao sumidos ... Faz bastante tempo que nao vemos uma mensagem 
> matematica dos Prof´s Nicolau, Wagner,Jose Paulo, Ralph, Morgado, Gustavo 
> Tamm e muitos outros ...

Atendendo a pedidos, aí vai um problema muito clássico mas sempre interessante.

Uma máquina engole bolinhas numeradas 1, 2, ..., n nesta ordem.
Dentro da máquina as bolinhas ficam empilhadas, a última que entrou em cima.
A qualquer momento a máquina pode cuspir a bolinha que está no topo
de sua pilha interna (desde que a pilha não esteja vazia).
Seja a_n o número de seqüências diferentes que podem ser cuspidas.
Calcule a_n.

Exemplo: Para n = 3 temos a_n = 5:

ececec -> 123
eceecc -> 132
eeccec -> 213
eececc -> 231
eeeccc -> 321

onde 'e' e 'c' significam respectivamente 'engole' e 'cospe'

Os primeiros valores são 1,2,5,14,42,132,429,1430,4862,16796.
Este problema tem uma resposta simples que pode ser obtida
de muitas formas diferentes.

[]s, N.