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

[Fabio Dias Moreira <fabio.dias.moreira@xxxxxxxxxxxx>]

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�.

[]s,

-- 
F�bio "ctg \pi" Dias Moreira
GPG key ID: 6A539016BBF3190A (available at wwwkeys.pgp.net)

PGP signature