Secara asimptotik, berapa banyak permutasi

Pertimbangkan permutasi dari . Inversi didefinisikan sebagai pasangan dari indeks sedemikian rupa sehingga dan . $\sigma$ $[1..n]$ $(i, j)$ $i < j$ $\sigma(i) > \sigma(j)$

Tetapkan untuk menjadi jumlah permutasi dengan paling banyak inversi. $A_k$ $[1..n]$ $k$

Pertanyaan: Apa terikat ketat asimptotik untuk ? $A_k$

Pertanyaan terkait diajukan sebelumnya: Jumlah permutasi yang memiliki jarak Kendall-Tau yang sama

Tetapi pertanyaan di atas adalah mengenai komputasi . Ia dapat dihitung menggunakan pemrograman dinamis, karena ia memenuhi relasi perulangan yang ditunjukkan di sini: /programming/948341/dynamic-programming-number-of-ways-to-get-at-least-n-bubble -sort-swap $A_k$

Jumlah permutasi dengan inversi tepat juga telah dipelajari dan dapat dinyatakan sebagai fungsi pembangkit: http://en.wikipedia.org/wiki/Permutation#Inversions $k$

Tetapi saya tidak dapat menemukan formula bentuk tertutup atau ikatan asimptotik.

co.combinatorics permutations Vinayak Pathak
sumber

Jika Anda memiliki polinomial pembangkit untuk suatu urutan, Anda dapat memperoleh polinomial pembangkit untuk jumlah awalan hanya dengan mengalikan polinomial dengan

. Dalam kasus Anda, Anda akan menggunakan polinomial yang ditautkan dengan yang menghitung inversi persis-k.

1 / (1 - x)

$1/(1-x)$

Suresh Venkat

Ini oeis.org/A161169

András Salamon

@ SureshVenkat Terima kasih atas tipnya. Tapi aku masih akan terjebak dengan mencari koefisien

dalam benar-benar rumit polinomial dalam hal

dan

dan saya tidak melihat bagaimana melakukan hal itu.

x^{k}

$x^k$

n

$n$

k

$k$

Vinayak Pathak

untuk mendapatkan koefisien

, mengambil

-th turunan dari polinomial menghasilkan dan mengevaluasi di

x^{k}

$x^k$

k

$k$

x = 0

$x = 0$

Sasho Nikolov

Jawaban:

Menurut Wikipedia, jumlah permutasi dalam dengan inversi yang tepat adalah koefisien dalam Nyatakan ini dengan . Ini menunjukkan bahwa $S_n$ $k$ $X^k$

1 (1 + X) (1 + X + X^{2}) \dots (1 + X + \dots + X^{n - 1}) .

$1(1+X)(1+X+X^2)\cdots(1+X+\cdots+X^{n-1}).$

c (n, k)

$c(n,k)$

Jadi jumlah permutasi dalam

dengan paling banyakinversi

sama dengan jumlah permutasi dalam

denganinversi

tepat. Ini memiliki bukti kombinatorial rapi juga (petunjuk: take

dan menghapus

c (n + 1, k) = \sum_{l = 0}^{k} c (n, k - l) .

$c(n+1,k) = \sum_{l=0}^k c(n,k-l).$

S_{n}

$S_n$

k

$k$

S_{n + 1}

$S_{n+1}$

k

$k$

π \in S_{n + 1}

$\pi\in S_{n+1}$

n + 1

$n+1$

$X^k$ $X^m$ $m > k$ $n > k$ $c(n,k)$ $X^k$

\begin{aligned} 1 (1 + X) \dots (1 + X + \dots + X^{k - 1}) (1 + X + \dots + X^{k} + \dots)^{n - k} \\ = & 1 (1 + X) \dots (1 + X + \dots + X^{k - 1}) \frac{1}{(1 - X)^{n - k}} \\ = & 1 (1 + X) \dots (1 + X + \dots + X^{k - 1}) \sum_{t = 0}^{\infty} (\binom{t + n - k - 1}{t}) X^{t} . \end{aligned}

$\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), n > k .

$c(n,k) = \sum_{t=0}^k \binom{n+t-k-1}{t} c(k,k-t), \quad n > k.$

$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,k) = \binom{n-1}{k} + O_k(n^{k-1}) = \frac{1}{k!} n^k + O_k(n^{k-1}).$

c (n + 1, k)

$c(n+1,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}) .

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

Yuval Filmus
sumber

c (n, k) \leq k! (\binom{n - 1}{k}) \leq e k^{k + 1 / 2} e^{- k} (e (n - 1) / k)^{k}

$c(n,k)\leq k!\binom{n-1}{k} \leq ek^{k+1/2}e^{-k}(e(n-1)/k)^k$

c (n, k) \leq e \sqrt{k} (n - 1)^{k}

$c(n,k) \leq e\sqrt{k}(n-1)^k$