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