Wie viele Permutationen von

Betrachten Sie eine Permutation von . Eine Inversion ist als ein Paar von Indizes definiert, so dass und . $\sigma$ $[1..n]$ $(i, j)$ $i < j$ $\sigma(i) > \sigma(j)$

Definieren Sie als die Anzahl der Permutationen von mit höchstens Inversionen. $A_k$ $[1..n]$ $k$

Frage: Was ist die enge asymptotische Grenze für ? $A_k$

Zuvor wurde eine verwandte Frage gestellt: Anzahl der Permutationen, die den gleichen Kendall-Tau-Abstand haben

Die obige Frage betraf jedoch die Berechnung von . Sie kann mit dynamischer Programmierung berechnet werden, da sie die hier gezeigte Wiederholungsrelation erfüllt: /programming/948341/dynamic-programming-number-of-ways-to-get-at-stest-n-bubble -Sortentausch $A_k$

Die Anzahl der Permutationen mit genau Inversionen wurde ebenfalls untersucht und kann als generierende Funktion ausgedrückt werden: http://en.wikipedia.org/wiki/Permutation#Inversions $k$

Aber ich kann keine geschlossene Formel oder keine asymptotische Bindung finden.

co.combinatorics permutations Vinayak Pathak
quelle

Wenn Sie ein generierendes Polynom für eine Sequenz haben, können Sie das generierende Polynom für die Präfixsummen ableiten, indem Sie das Polynom einfach mit

multiplizieren . In Ihrem Fall würden Sie das Polynom verwenden, mit dem Sie verknüpft haben, um die genau k-Inversionen zu berechnen.

1 / (1 - x)

$1/(1-x)$

Suresh Venkat

Dies ist oeis.org/A161169

András Salamon

@SureshVenkat Danke für den Tipp. Aber ich werde immer noch feststecken, wenn ich den Koeffizienten von

in diesem wirklich komplizierten Polynom in Bezug auf

und

finde, und ich verstehe nicht, wie ich das machen soll.

x^{k}

$x^k$

n

$n$

k

$k$

Vinayak Pathak

Um den Koeffizienten von

, nimm die

te Ableitung des erzeugenden Polynoms und bewerte sie mit

x^{k}

$x^k$

k

$k$

x = 0

$x = 0$

Sasho Nikolov

Antworten:

Laut Wikipedia ist die Anzahl der Permutationen in mit genau Inversionen der Koeffizient von in Bezeichne dies mit . Dies zeigt, dass $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)$

Sodie Anzahl von Permutationen in

mit höchstens

Inversionen ist auf die Anzahl von Permutationen in gleich

mit genau

Inversionen. Dies hat auch einen ordentlichen kombinatorischen Beweis (Hinweis: nimm

und entferne

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.$

Wenn konstant ist, ist der asymptotisch wichtigste Term derjenige, der , und wir haben Die gleichen asymptotischen Eigenschaften gelten für , nach denen Sie gesucht haben. $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)$

Bei nicht konstantem nimmt die Verwendung der Tatsache, dass in underhalten wir die Grenzen Bessere Grenzen sind sicherlich möglich, aber das überlasse ich Ihnen. $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
quelle

Mit Stirlings Approximation und den Binomialgrenzen können wir den letzten Ausdruck zu vereinfachen so . Dies ist natürlich nicht eng, aber es ist eine elegantere Grenze, als ich von diesen Annäherungen erwarten würde.

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$

SamM