Assintoticamente, quantas permutações de

17

Considere uma permutação σ de [1..n] . Uma inversão é definida como um par (i,j) de índices tais que i<j e σ(i)>σ(j) .

Defina Ak como o número de permutações de [1..n] com no máximo k inversões.

Pergunta: Qual é o forte limite assintótico para Ak ?

Uma pergunta relacionada foi feita antes: Número de permutações que têm a mesma distância Kendall-Tau

Mas a pergunta acima era sobre a computação . Ele pode ser calculado usando programação dinâmica, pois satisfaz a relação de recorrência mostrada aqui: /programming/948341/dynamic-programming-number-of-ways-to-get-ateastln-bubble -sort-swapsAk

O número de permutações com exatamente inversões também foi estudado e pode ser expresso como uma função geradora: http://en.wikipedia.org/wiki/Permutation#Inversionsk

Mas não consigo encontrar uma fórmula de forma fechada ou um limite assintótico.

Vinayak Pathak
fonte
2
Se você tiver um polinômio gerador para uma sequência, poderá derivar o polinômio gerador para as somas do prefixo apenas multiplicando o polinômio por . No seu caso, você usaria o polinômio ao qual vincula que calcula exatamente as k inversões. 1/(1x)
Suresh Venkat
2
Isto é oeis.org/A161169
András Salamon
11
@SureshVenkat Obrigado pela dica. Mas eu ainda vai ser preso com encontrar o coeficiente de neste realmente complicado polinômio em termos de n e k e eu não vejo como fazer isso. xknk
Vinayak Pathak
3
para obter o coeficiente de , pegue a derivada k- ésima do polinômio gerador e avalie-o em x = 0 . xkkx=0
Sasho Nikolov

Respostas:

12

Segundo a Wikipedia, o número de permutações em com exatamente k inversões é o coeficiente de X k em 1 ( 1 + X ) ( 1 + X + X 2 ) ( 1 + X + + X n - 1 ) . Denote isso por c ( n , k ) . Isso mostra que c ( n + 1 ,SnkXk

1(1+X)(1+X+X2)(1+X++Xn1).
c(n,k)
c(n+1,k)=l=0kc(n,kl).
Portanto, o número de permutações em com no máximo k inversões é igual ao número de permutações em S n + 1 com exatamente k inversões. Isso também tem uma prova combinatória pura (dica: pegue π S n + 1 e remova n + 1 ).SnkSn+1kπSn+1n+1

Se estamos interessados ​​apenas no coeficiente de , os fatores X m para m > k não fazem diferença. Assim, para n > k , c ( n , k ) é o coeficiente de X k em XkXmm>kn>kc(n,k)Xk

1(1+X)(1+X++Xk1)(1+X++Xk+)nk=1(1+X)(1+X++Xk1)1(1X)nk=1(1+X)(1+X++Xk1)t=0(t+nk1t)Xt.
c(n,k)=t=0k(n+tk1t)c(k,kt),n>k.

kt=k

c(n,k)=(n1k)+Ok(nk1)=1k!nk+Ok(nk1).
c(n+1,k)

k(n+tk1t)=(n+tk1nk1)tt=0kc(k,t)k!

(n1k)c(n,k)k!(n1k).
Yuval Filmus
fonte
c(n,k)k!(n1k)ekk+1/2ek(e(n1)/k)kc(n,k)ek(n1)k
SamM