Асимптотически, сколько перестановок из

Рассмотрим перестановку $\sigma$ из $[1..n]$ . Инверсия определяется как пара $(i, j)$ индексов, такая что $i < j$ и $\sigma(i) > \sigma(j)$ .

Определите $A_k$ как число перестановок в $[1..n]$ с не более чем $k$ инверсиями.

Вопрос: Какова жесткая асимптотическая оценка для $A_k$ ?

Ранее был задан связанный вопрос: количество перестановок, имеющих одинаковое расстояние Кендалла-Тау

Но вопрос выше касался вычисления $A_k$ . Он может быть вычислен с использованием динамического программирования, поскольку он удовлетворяет рекуррентному отношению, показанному здесь: /programming/948341/dynamic-programming-number-of-ways-to-get-at-least-n-bubble -sort-свопы

Количество перестановок с ровно $k$ инверсиями также было изучено и может быть выражено в виде производящей функции: http://en.wikipedia.org/wiki/Permutation#Inversions

Но я не могу найти формулу замкнутой формы или асимптотическую оценку.

Согласно Википедии, число перестановок в с ровно k инверсиями является коэффициентом X k в 1 ( 1 + X ) ( 1 + X + X 2 ) ⋯ ( 1 + X + ⋯ + X n - 1 ) . Обозначим это через c ( n , k ) . Это показывает, что с ( п + 1 $S_n$$k$$X^k$

$$1(1+X)(1+X+X^2)\cdots(1+X+\cdots+X^{n-1}).$$ $c(n,k)$ Таким образом, число перестановок в S n с не более чем k инверсиями равно числу перестановок в S n + 1 с ровно k инверсиями. Это также имеет хорошее комбинаторное доказательство (подсказка: возьмем π ∈ S n + 1 и удалим 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$

Если нас интересует только коэффициент , то факторы X m при m > k не имеют значения. Таким образом, для n > k , c ( n , k ) является коэффициентом X k в $X^k$$X^m$$m > k$$n > k$$c(n,k)$$X^k$ Это подразумевает формулу c(n,k)=k∑t=0(n+t-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.$$

Когда является постоянным, наиболее важным асимптотически является термин, соответствующий t = k , и мы имеем c ( n , k ) = ( n - $k$$t = k$ Та же самая асимптотика работает дляc(n+1,k), что вы и сделали.

$$c(n,k) = \binom{n-1}{k} + O_k(n^{k-1}) = \frac{1}{k!} n^k + O_k(n^{k-1}).$$ $c(n+1,k)$

Для непостоянных , используя тот факт, что ( n + t - k - $k$$\binom{n+t-k-1}{t} = \binom{n+t-k-1}{n-k-1}$$t$$\sum_{t=0}^k c(k,t) \leq k!$

$$\binom{n-1}{k} \leq c(n,k) \leq k! \binom{n-1}{k}.$$