Asymptotiquement, combien de permutations de

Considérons une permutation $\sigma$ de $[1..n]$ . Une inversion est définie comme une paire $(i, j)$ d'indices tels que $i < j$ et $\sigma(i) > \sigma(j)$ .

Définissez $A_k$ comme le nombre de permutations de $[1..n]$ avec au plus $k$ inversions.

Question: Quelle est la limite asymptotique étroite pour $A_k$ ?

Une question connexe a été posée auparavant: nombre de permutations qui ont la même distance Kendall-Tau

Mais la question ci-dessus concernait le calcul de . Il peut être calculé à l'aide de la programmation dynamique, car il satisfait la relation de récurrence indiquée ici: /programming/948341/dynamic-programming-number-of-ways-to-get-at-least-n-bubble -sort-swaps$A_k$

Le nombre de permutations avec exactement inversions a également été étudié et il peut être exprimé comme une fonction génératrice: http://en.wikipedia.org/wiki/Permutation#Inversions$k$

Mais je ne trouve pas de formule de forme fermée ou de borne asymptotique.

Selon Wikipedia, le nombre de permutations dans avec exactement k inversions est le coefficient de X k dans 1 ( 1 + X ) ( 1 + X + X 2 ) ⋯ ( 1 + X + ⋯ + X n - 1 ) . Notons c ( n , k ) . Cela montre que c ( n + 1 $S_n$$k$$X^k$

$$1(1+X)(1+X+X^2)\cdots(1+X+\cdots+X^{n-1}).$$ $c(n,k)$ Ainsi, le nombre de permutations dans S n avec au plus k inversions est égal au nombre de permutations dans S n + 1 avec exactement k inversions. Cela a aussi une preuve combinatoire nette (indice: prenez π ∈ S n + 1 et supprimez n + 1 ). $$c(n+1,k) = \sum_{l=0}^k c(n,k-l).$$ $S_n$$k$$S_{n+1}$$k$$\pi\in S_{n+1}$$n+1$

Si nous ne nous intéressons qu'au coefficient de , alors les facteurs X m pour m > k ne font aucune différence. Donc pour n > k , c ( n , k ) est le coefficient de X k dans $X^k$$X^m$$m > k$$n > k$$c(n,k)$$X^k$

$$\begin{align*} &1(1+X)\cdots(1+X+\cdots+X^{k-1}) (1+X+\cdots+X^k+\cdots)^{n-k} \\ = &1(1+X)\cdots(1+X+\cdots+X^{k-1}) \frac{1}{(1-X)^{n-k}} \\ = &1(1+X)\cdots(1+X+\cdots+X^{k-1}) \sum_{t=0}^\infty \binom{t+n-k-1}{t} X^t. \end{align*}$$ $$c(n,k) = \sum_{t=0}^k \binom{n+t-k-1}{t} c(k,k-t), \quad n > k.$$

$k$ est constant, le terme asymptotiquement le plus important est celui correspondant à $t = k$, et nous avons

$$c(n,k) = \binom{n-1}{k} + O_k(n^{k-1}) = \frac{1}{k!} n^k + O_k(n^{k-1}).$$ The same asymptotics work for $c(n+1,k)$, which is what you were after.

For non-constant $k$, using the fact that $\binom{n+t-k-1}{t} = \binom{n+t-k-1}{n-k-1}$ is increasing in $t$ and $\sum_{t=0}^k c(k,t) \leq k!$, we get the bounds

$$\binom{n-1}{k} \leq c(n,k) \leq k! \binom{n-1}{k}.$$ Better bounds are surely possible, but I'll leave that to you.