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