[obm-l] Re: [obm-l] Permutaçoes com pilhas.

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

On Tue, Dec 02, 2003 at 11:20:50PM -0200, Fabio Dias Moreira wrote:
> On 12/02/03 19:17:46, niski wrote:
> > Em uma aula de computação me deparei com o seguinte problema :
> > 
> > "Suponha que os inteiros 1, 2, 3 e 4 são lidos nesta ordem.  
> > Considerando todas as possíveis seqüências de operações de empilhar e  
> > desempilhar, decida quais da 4! (=24) permutações de 1,2,3,4 podem  
> > ser obtidas na saída de uma pilha. Por exemplo, a permutação 2,3,1,4  
> > pode ser obtida da seguinte forma: empilha 1, empilha 2, desempilha  
> > 2, empilha 3, desempilha 3, desempilha 1, empilha 4, desempilha 4. "
> > 
> > Fiz na força bruta. Me parece que são 10 permutacoes possiveis.
> > 
> > Pergunto mais genericamente agora...se eu tivesse os inteiros 1,2...n  
> > lidos nesta ordem, QUANTAS das n! permutacoes de 1,2,3...n podem ser  
> > obtidas na saida de uma pilha ?
> > [...]
> 
> Uma resposta final está definida unicamente por uma seqüência de 2n  
> caracteres, n E e n D, que equivalem às operações Empilhar e  
> Desempilhar. É obvio, a pilha secundária nunca pode ser desempilhada  
> quando está vazia, logo temos que remover estas possibilidades.
> 
> Represente graficamente o processo -- em um instante qualquer, após i  
> operações, plote o ponto (i, e-d), onde e é o número de Es que já foram  
> executados e d o número de Ds. Termine conectando pontos adjacentes.  
> Queremos saber o número de gráficos que tem todas as coordenadas y  
> positivas, i.e. que não tocam a reta (x, -1).
> 
> Este problema é um problema clássico de combinatória, e sua resposta  
> vale 1/n C(2n;n-1). Vale a pena tentar demosntrar isso sozinho.
> 
> Você tem certeza de que são só 10?
> 
>  1. EDEDEDED
>  2. EDEDEEDD
>  3. EDEEDEDD
>  4. EDEEDDED
>  5. EDEEEDDD
>  6. EEDEDEDD
>  7. EEDEDDED
>  8. EEDEEDDD
>  9. EEDDEDED
> 10. EEDDEEDD
> 11. EEEDEDDD
> 12. EEEDDEDD
> 13. EEEDDDED
> 14. EEEEDDDD
> 
> Eu conto 14, que é justamente o que a resposta prevê.

Este problema é uma das muitas interpretações combinatórias clássicas
para os números de Catalan. Veja o item (ii) na página 226 de
http://www-math.mit.edu/~rstan/ec/catalan.ps.gz
Aliás veja também os outros itens.

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