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