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

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

on 03.12.03 00:39, niski at fabio@niski.com wrote:

>> Oi, Niski:
>> 
>> Soh pra clarificar: dada uma permutacao fixa "p" de {1,2,...,n}, digamos:
>> 1 -> p(1), 2 -> p(2), ..., n -> p(n),
> 
> Não entendi muito bem sua notação.
> p(1) entende-se por "posição 1"?
> 
Minha notacao reflete o fato de que uma permutacao de {1,2,...,n} eh uma
bijecao "p" desse conjunto nele mesmo, a qual leva x em p(x).

De qualquer forma, veja a mensagem do Fabio Dias Moreira, na qual ele dah o
numero correto de permutacoes realizaveis por uma pilha.

Repare que a solucao dele envolve uma "corrida" entre os E's e os D's onde
os D's nunca estao na frente, o que faz sentido pois voce nao pode
desempilhar mais numeros do que os que estao empilhados. Isso estah
relacionado aos numeros de Catalan - tema de uma mensagem enviada pelo
Nicolau ha alguns dias.

Eu ainda gostaria de ver uma caracterizacao das permutacoes realizaveis. A
condicao que eu mencionei anteriormente (p(k+1) - p(k) >= -1, para 1 <= k <=
n-1) de fato nao eh necessaria, mas suficiente. Existem permutacoes
realizaveis que nao a satisfazem. Por exemplo: 3-2-4-1 eh relizavel por meio
de E1 E2 E3 D3 D2 E4 D4 D1, apesar de p(4) - p(3) = 1 - 4 = -3 < -1.

Um abraco,
Claudio.


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