Asymptotycznie, ile permutacji

Rozważ permutację $\sigma$ wynoszącą $[1..n]$ . Inwersję definiuje się jako parę $(i, j)$ indeksów takich, że $i < j$ i $\sigma(i) > \sigma(j)$ .

Zdefiniuj $A_k$ jako liczbę permutacji $[1..n]$ z co najwyżej $k$ inwersjami.

Pytanie: Jaka jest ścisła asymptotyczna granica dla $A_k$ ?

Podobne pytanie zostało zadane wcześniej: Liczba permutacji, które mają tę samą odległość Kendall-Tau

Ale pytanie powyżej dotyczące obliczania $A_k$ . Można go obliczyć za pomocą programowania dynamicznego, ponieważ spełnia przedstawioną tutaj relację powtarzalności: /programming/948341/dynamic-programming-number-of-ways-to-get-at-least-n-bubble -sort-swap

Zbadano również liczbę permutacji z dokładnie $k$ inwersjami, które można wyrazić jako funkcję generującą: http://en.wikipedia.org/wiki/Permutation#Inversions

Ale nie mogę znaleźć formuły zamkniętej ani asymptotycznej granicy.

Według Wikipedii liczba permutacji w przy dokładnie k inwersjach jest współczynnikiem X k w 1 ( 1 + X ) ( 1 + X + X 2 ) ⋯ ( 1 + X + ⋯ + X n - 1 ) . Oznacz to przez c ( n , k ) . To pokazuje, że 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)$ Zatem liczba permutacji wSnz co najwyżejkinwersjami jest równa liczbie permutacji wSn+1z dokładniekinwersjami. Ma to również zgrabny dowód kombinatoryczny (wskazówka: weźπ∈Sn+1i usuń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$

Jeśli interesuje nas tylko współczynnik , to czynniki X m dla m > k nie mają znaczenia. Zatem dla n > k , c ( n , k ) to współczynnik X k w $X^k$$X^m$$m > k$$n > k$$c(n,k)$$X^k$ To implikuje wzór 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.$$

Gdy jest stałe, asymptotycznie najważniejszym terminem jest ten odpowiadający t = k , a mamy c ( n , k ) = ( n - $k$$t = 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)$

$k$$\binom{n+t-k-1}{t} = \binom{n+t-k-1}{n-k-1}$ rośnie w $t$ i $\sum_{t=0}^k c(k,t) \leq k!$, dostajemy granice

$$\binom{n-1}{k} \leq c(n,k) \leq k! \binom{n-1}{k}.$$ Lepsze granice są z pewnością możliwe, ale zostawię to tobie.