[obm-l] Permutacoes com ciclos de ordem >= 3

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

Oi, Rogerio (e demais colegas):

Fiz algum porgresso nesse problema:

Sejam:
F(n) = numero de permutacoes de {1,2,...,n} sem pontos fixos nem
transposicoes (ciclos de ordem 2);
D(n) = numero de permutacoes caoticas de {1,2,...,n};
D(n,k) = numero de permutacos caoticas de {1,2,...,n} com exatamente k
transposicoes.

Eh claro que D(n) = SOMA(0<=k<=[n/2]) D(n,k)
e tambem que D(n) = n!*(1/2! - 1/3! + 1/4! - ... + (-1)^n/n!)  (*)

D(n,k) pode ser calculado da seguinte forma:
- Escolha dos 2k elementos de {1,2,...,n} que irao compor as k
transposicoes: Binom(n,2k) maneiras;
- Particao desses 2k elementos pelas k transposicoes: (2k)!/(2^k*k!)
maneiras;
- Permutacao caotica sem transposicoes dos demais n - 2k elementos de
{1,2,...,n}: F(n-2k) maneiras.

Logo, D(n,k) = Binom(n,2k)*((2k)!/(2^k*k!))*F(n-2k)

E assim:
D(n) = SOMA(0<=k<=[n/2]) Binom(n,2k)*((2k)!/(2^k*k!))*F(n-2k) ==>
D(n) = F(n) + SOMA(1<=k<=[n/2]) Binom(n,2k)*((2k)!/(2^k*k!))*F(n-2k) ==>

F(n) = D(n) - SOMA(1<=k<=[n/2]) Binom(n,2k)*((2k)!/(2^k*k!))*F(n-2k),
onde D(n) eh dada pela formula (*) acima.

Nao eh uma formula fechada bonitinha (que eu nao creio que exista - ou seja,
F(n) nao deve poder ser expressa como uma combinacao de "funcao
combinatorias elementares"), mas jah eh alguma coisa...

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