Considere uma permutação de . Uma inversão é definida como um par de índices tais que e .
Defina como o número de permutações de com no máximo inversões.
Pergunta: Qual é o forte limite assintótico para ?
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-swaps
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#Inversions
Mas não consigo encontrar uma fórmula de forma fechada ou um limite assintótico.
fonte
Respostas:
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 ,Sn k Xk
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 emXk Xm m>k n>k c(n,k) Xk
fonte