Considere una permutación de . Una inversión se define como un par de índices tales que y .
Defina como el número de permutaciones de con a lo sumo inversiones.
Pregunta: ¿Cuál es el límite asintótico estrecho para ?
Antes se hizo una pregunta relacionada: Número de permutaciones que tienen la misma distancia Kendall-Tau
Pero la pregunta anterior se refería a la computación . Se puede calcular mediante programación dinámica, ya que satisface la relación de recurrencia que se muestra aquí: /programming/948341/dynamic-programming-number-of-ways-to-get-at-least-n-bubble -sort-swaps
También se ha estudiado el número de permutaciones con exactamente inversiones y se puede expresar como una función generadora: http://en.wikipedia.org/wiki/Permutation#Inversions
Pero no puedo encontrar una fórmula de forma cerrada o un límite asintótico.
fuente
Respuestas:
Según Wikipedia, el número de permutaciones en con exactamente k inversiones es el coeficiente de X k en 1 ( 1 + X ) ( 1 + X + X 2 ) ⋯ ( 1 + X + ⋯ + X n - 1 ) . Denote esto por c ( n , k ) . Esto muestra que c ( n + 1 ,Sn k Xk
Si solo nos interesa el coeficiente de , entonces los factores X m para m > k no hacen ninguna diferencia. Entonces, para n > k , c ( n , k ) es el coeficiente de X k enXk Xm m>k n>k c(n,k) Xk
fuente