Anzahl der Permutationen

21.10.2018, 17:51

Studentu

Anzahl der Permutationen

Hallo allerseits!

Sei $\begin{eqnarray*} I_n(k) \end{eqnarray*}$ die Anzahl der Permutationen von $\begin{eqnarray*} \{1, \cdots, n\} \end{eqnarray*}$ mit k Inversionen.

Zunächst möchte ich zeigen, dass $\begin{eqnarray*} I_n(k) = I_n(k-1) + I_{n-1}(k) \end{eqnarray*}$ , für k<n ist.
(Dann sind noch andere Unterpunkte zu zeigen, aber ich hoffe, dass mir die klar werden, sobald ich weiß, wie man generell mit diesem $\begin{eqnarray*} I_n(k) \end{eqnarray*}$ umgeht.)

Kann mir jemand verraten, ob es da eine bekannte Formel für das $\begin{eqnarray*} I_n(k) \end{eqnarray*}$ gibt oder wie man das Beispiel ansonsten angeht? (Ich wollte es nämlich mit vollständiger Induktion zeigen, aber weiß nicht einmal, wie dann der Induktionsanfang aussieht.)

Danke euch im Voraus!

21.10.2018, 22:39

Studentu

Auf diesen Beitrag antworten »

Ich habe gerade gemerkt, dass ich die Frage unabsichtlich in "Schulmathematik" gepostet habe. Kann sie bitte jemand in "Hochschulmathematik" verschieben?

22.10.2018, 11:32

HAL 9000

Auf diesen Beitrag antworten »

Diese Rekursion ist etwas knifflig, aber ich versuche sie mal zu erklären: $\begin{eqnarray*} I_n(k) \end{eqnarray*}$ zählt die Anzahl der Permutationen $\begin{eqnarray*} \pi \end{eqnarray*}$ mit genau $\begin{eqnarray*} k \end{eqnarray*}$ Inversionen. D.h., für jedes solche $\begin{eqnarray*} \pi \end{eqnarray*}$ gibt es genau $\begin{eqnarray*} k \end{eqnarray*}$ Paare $\begin{eqnarray*} (i,j) \end{eqnarray*}$ mit $\begin{eqnarray*} 1\leq i < j\leq n \end{eqnarray*}$ sowie $\begin{eqnarray*} \pi(i)>\pi(j) \end{eqnarray*}$ .

Für jede solche Permutation $\begin{eqnarray*} \pi \end{eqnarray*}$ betrachten wir nun die Position $\begin{eqnarray*} m \end{eqnarray*}$ mit $\begin{eqnarray*} \pi(m)=n \end{eqnarray*}$ .

1.Fall: $\begin{eqnarray*} m=n \end{eqnarray*}$

Hier gibt es kein Inversion $\begin{eqnarray*} (i,j) \end{eqnarray*}$ mit $\begin{eqnarray*} j=n \end{eqnarray*}$ , die Anzahl solcher Permutationen mit $\begin{eqnarray*} k \end{eqnarray*}$ Inversionen ist somit $\begin{eqnarray*} I_{n-1}(k) \end{eqnarray*}$ .

2.Fall: $\begin{eqnarray*} m<n \end{eqnarray*}$

Wir tauschen die Werte an den Positionen $\begin{eqnarray*} m \end{eqnarray*}$ und $\begin{eqnarray*} m+1 \end{eqnarray*}$ , dadurch verringert sich die Inversionszahl der so entstandenen Permutation $\begin{eqnarray*} \pi' \end{eqnarray*}$ um genau 1, sie hat somit genau $\begin{eqnarray*} k-1 \end{eqnarray*}$ Inversionen.

Diese Tausch-Abbildung ist bijektiv: Wir können eine beliebige Permutation $\begin{eqnarray*} \pi' \end{eqnarray*}$ mit genau $\begin{eqnarray*} k-1 \end{eqnarray*}$ Inversionen hernehmen, dort die Stelle $\begin{eqnarray*} m' \end{eqnarray*}$ mit $\begin{eqnarray*} \pi'(m')=n \end{eqnarray*}$ suchen und dann die Werte an den Positionen $\begin{eqnarray*} m' \end{eqnarray*}$ mit $\begin{eqnarray*} m'-1 \end{eqnarray*}$ tauschen und gelangen damit wieder zu $\begin{eqnarray*} \pi \end{eqnarray*}$ .

Dem würde einzig die Möglichkeit $\begin{eqnarray*} m'=1 \end{eqnarray*}$ , also $\begin{eqnarray*} \pi'(1)=n \end{eqnarray*}$ entgegenstehen, da dort ein solcher Tausch nicht möglich ist. Aber diese Möglichkeit besteht hier nicht, da dann $\begin{eqnarray*} \pi' \end{eqnarray*}$ mindestens $\begin{eqnarray*} n-1 \end{eqnarray*}$ Inversionen haben müsste, was der Voraussetzung $\begin{eqnarray*} k<n \end{eqnarray*}$ widerspricht.

---------------------

Der Beweis zeigt auch, dass $\begin{eqnarray*} I_n(k) = I_n(k-1)+I_{n-1}(k) \end{eqnarray*}$ im Fall $\begin{eqnarray*} k\geq n \end{eqnarray*}$ nicht mehr stimmt; im weiteren Verlauf deiner Überlegungen wird für diesen Fall dann wohl irgendwann Formel $\begin{eqnarray*} I_n(k) = I_n(k-1)+I_{n-1}(k)-I_{n-1}(k-n) \end{eqnarray*}$ auftauchen.

Zitat:

Original von Studentu
Kann mir jemand verraten, ob es da eine bekannte Formel für das $\begin{eqnarray*} I_n(k) \end{eqnarray*}$ gibt

Wenn es da was einfaches gäbe, müsste man sich wohl nicht mit solchen Rekursionen rumplagen. Augenzwinkern

22.10.2018, 14:50

Studentu

Auf diesen Beitrag antworten »

Danke für die ausführliche Erklärung, Hal 9000! Big Laugh

Ich glaube, das habe ich nun verstanden (zumindest habe ich jeden Schritt in der Erklärung verstanden).
Wie mir dies für die anderen Unterpunkte helfen soll, sehe ich aber nicht.
Zunächst ist nämlich noch zu zeigen, dass $\begin{eqnarray*} \sum_k I_n(k) z^k = \prod_{j=0}^{n-1}(1+\cdots + z^j) \end{eqnarray*}$ und $\begin{eqnarray*} \sum_k I_n(k) = n! \end{eqnarray*}$ . (Ich vermute mal, k läuft da jeweils von 0 bis n-1?)
Müssen wir dafür vorher irgendwie die hergeleitete Rekursion lösen und die explizite Form dann hier einsetzen (geht das überhaupt?) oder wie ist das gemeint?

22.10.2018, 16:14

HAL 9000

Auf diesen Beitrag antworten »

Zumindest $\begin{eqnarray*} \sum_k I_n(k) = n! \end{eqnarray*}$ ist trivial: Jede Permutation hat eine bestimmte Inversionsanzahl, findet sich also in genau einem $\begin{eqnarray*} I_n(k) \end{eqnarray*}$ wieder. Somit muss die Summe aller $\begin{eqnarray*} I_n(k) \end{eqnarray*}$ gleich der Anzahl aller Permutationen sein, und das ist nun mal $\begin{eqnarray*} n! \end{eqnarray*}$ .

Aber es ist natürlich auch eine Folgerung der ersten Eigenschaft $\begin{eqnarray*} \sum_k I_n(k) z^k = \prod_{j=0}^{n-1}(1+\cdots + z^j) \end{eqnarray*}$ , wenn man $\begin{eqnarray*} z=1 \end{eqnarray*}$ einsetzt. Augenzwinkern

Begründen (für allgemeine $\begin{eqnarray*} z \end{eqnarray*}$ ) lässt sich diese erste Eigenschaft auch wieder inhaltlich: Nach Ausmultiplizieren ist

$\begin{eqnarray*} \prod_{j=0}^{n-1}(1+\cdots + z^j) = \sum_{(a_1,\ldots,a_n)} z^{a_1+a_2+\ldots+a_n} \end{eqnarray*}$

wobei über alle $\begin{eqnarray*} n \end{eqnarray*}$ -Tupel $\begin{eqnarray*} (a_1,\ldots,a_n) \end{eqnarray*}$ mit $\begin{eqnarray*} 0\leq a_j\leq j-1 \end{eqnarray*}$ für alle $\begin{eqnarray*} j=1,\ldots,n \end{eqnarray*}$ summiert wird. Wenn du jetzt eine Bijektion zwischen $\begin{eqnarray*} \pi\in S_n \end{eqnarray*}$ und der Menge aller Tupel $\begin{eqnarray*} (a_1,\ldots,a_n) \end{eqnarray*}$ in der Weise findest, dass die Inversionszahl von $\begin{eqnarray*} \pi \end{eqnarray*}$ genau $\begin{eqnarray*} a_1+a_2+\ldots+a_n \end{eqnarray*}$ ist, bist du durch.

22.10.2018, 19:14

Studentu

Auf diesen Beitrag antworten »

Die Erklärung für den zweiten Ausdruck, (und natürlich ebenfalls das mit z=1 setzen) habe ich verstanden, danke!

Was die gesucht Bijektion betrifft, bin ich noch am Überlegen bzw. Herumprobieren.

Es ist außerdem noch zu zeigen, dass
$\begin{eqnarray*} \sum_k (-1)^k I_n(k) = 0 \end{eqnarray*}$ für $\begin{eqnarray*} n \geq 2 \end{eqnarray*}$ , was sich auch leicht durch Einsetzen von -1 für z zeigen lassen müsste.
Dann ist aber noch $\begin{eqnarray*} \sum_k kI_n(k) = \frac{1}{2} \binom{n}{2} n! \end{eqnarray*}$ zu zeigen. Da ist meine Idee, dass es sich vielleicht auch mit Ableiten nach z und dann z=1 setzen zeigen lassen müsste. Oder bin ich damit auf dem Holzweg und es funktioniert besser wieder mit Überlegungen?

22.10.2018, 19:56

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Studentu
Es ist außerdem noch zu zeigen, dass
$\begin{eqnarray*} \sum_k (-1)^k I_n(k) = 0 \end{eqnarray*}$ für $\begin{eqnarray*} n \geq 2 \end{eqnarray*}$ , was sich auch leicht durch Einsetzen von -1 für z zeigen lassen müsste.

Genau.

Zitat:

Original von Studentu
Dann ist aber noch $\begin{eqnarray*} \sum_k kI_n(k) = \frac{1}{2} \binom{n}{2} n! \end{eqnarray*}$ zu zeigen. Da ist meine Idee, dass es sich vielleicht auch mit Ableiten nach z und dann z=1 setzen zeigen lassen müsste.

Ebenfalls eine gute Idee. Ein Tipp dazu:

Ist $\begin{eqnarray*} f(z) = \prod_{j=0}^{n-1} (1+\ldots+z^j) \end{eqnarray*}$ , dann lässt sich $\begin{eqnarray*} g(z) = \ln(f(z)) = \sum_{j=1}^{n-1} \ln(1+\ldots+z^j) \end{eqnarray*}$ aufwandsarm ableiten. Zusammen mit $\begin{eqnarray*} g'(z) = \frac{f'(z)}{f(z)} \end{eqnarray*}$ lässt sich dann einfach $\begin{eqnarray*} f'(1) = f(1)\cdot g'(1) \end{eqnarray*}$ berechnen.

23.10.2018, 18:21

Studentu

Auf diesen Beitrag antworten »

Hallo Hal,
die Unterpunkte zu zeigen, hat inzwischen geklappt. smile

Ich kenne mich allerdings bei dem noch offenen ersten Teil kaum aus. Folgende Fragen habe ich:
1) Wie hast du dir die Gültigkeit der Produkt = Summe - Formel überlegt? Mir ist zwar intuitiv irgendwie klar, dass sie stimmen muss, aber wenn ich es mir ganz genau überlege, dann bekomme ich Vorstellungsprobleme wegen der aufsteigenden (und somit nicht für jeden Faktor gleichen) Werte für j.

2) Wieso ist das Gewünschte gezeigt, wenn wir die Permutation haben? (Ich sehe den Zusammenhang zu $\begin{eqnarray*} \sum_k I_n(k) z^k \end{eqnarray*}$ nicht.

3) Die gesuchte Permutation habe ich leider auch nicht gefunden.

23.10.2018, 18:58

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Studentu
1) Wie hast du dir die Gültigkeit der Produkt = Summe - Formel überlegt?

Das ist nun mal das was rauskommt beim Ausmultiplizieren. Vielleicht machst du dir das mal für kleine n=1,2,3 klar.

Das Ausmultiplizieren geht so vonstatten:

Es wird Summand $\begin{eqnarray*} z^{a_1} \end{eqnarray*}$ aus 1 (notgedrungen ist da nur $\begin{eqnarray*} a_1=0 \end{eqnarray*}$ möglich) mit Summand $\begin{eqnarray*} z^{a_2} \end{eqnarray*}$ aus $\begin{eqnarray*} (1+z) \end{eqnarray*}$ mit Summand $\begin{eqnarray*} z^{a_3} \end{eqnarray*}$ aus $\begin{eqnarray*} (1+z+z^2) \end{eqnarray*}$ usw. bis hin mit Summand $\begin{eqnarray*} z^{a_n} \end{eqnarray*}$ aus $\begin{eqnarray*} (1+z+\ldots+z^{n-1}) \end{eqnarray*}$ multipliziert. Das ergibt (nach Potenzregel) das Produkt $\begin{eqnarray*} z^{a_1+a_2+\ldots+a_n} \end{eqnarray*}$ .

23.10.2018, 20:21

Studentu

Auf diesen Beitrag antworten »

Okay, danke! Deine Herangehensweise ist eine ganz andere als ich sie gehabt habe und bleibt viel übersichtlicher.
Ich glaube, damit habe ich nun auch die gesuchte Bijektion gefunden:

Die n-te Zahl wird so aufgeschrieben, dass die Anzahl von Inversionen in Höhe $\begin{eqnarray*} a_1 \end{eqnarray*}$ durch sie entstehen. Da $\begin{eqnarray*} a_1=0 \end{eqnarray*}$ , wird die Zahl n einfach aufgeschrieben: n
Die n-1-te Zahl wird dann so aufgeschrieben, dass die Anzahl von Inversionen in Höhe $\begin{eqnarray*} a_2 \end{eqnarray*}$ durch sie entstehen, also entweder 0, dann schreibt man n-1, n
oder 1, dann schreibt man n, n-1.
Die k-te Zahl wird dann so aufgeschrieben, dass die Anzahl von Inversionen in Höhe $\begin{eqnarray*} a_{n-k+1} \end{eqnarray*}$ durch sie entstehen, indem man sie an die von links aus gesehen $\begin{eqnarray*} a_{n-k+1} \end{eqnarray*}$ -te Stelle setzt (wobei ganz links außen die 0-te Stelle ist).
Ich glaube, das kann man noch schöner formulieren; entsteht auf diese Weise nicht einfach die zur Inversionstafel $\begin{eqnarray*} (a_n, a_{n-1}, ..., a_1) \end{eqnarray*}$ gehörige Permutation?

Wenn das richtig ist, dann fehlt nur noch Punkt 2). Ich würde mich über eine Erklärung dafür sehr freuen.

23.10.2018, 21:42

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Studentu
Die n-te Zahl wird so aufgeschrieben, dass die Anzahl von Inversionen in Höhe $\begin{eqnarray*} a_1 \end{eqnarray*}$ durch sie entstehen. Da $\begin{eqnarray*} a_1=0 \end{eqnarray*}$ , wird die Zahl n einfach aufgeschrieben: n
Die n-1-te Zahl wird dann so aufgeschrieben, dass die Anzahl von Inversionen in Höhe $\begin{eqnarray*} a_2 \end{eqnarray*}$ durch sie entstehen, also entweder 0, dann schreibt man n-1, n
oder 1, dann schreibt man n, n-1.
Die k-te Zahl wird dann so aufgeschrieben, dass die Anzahl von Inversionen in Höhe $\begin{eqnarray*} a_{n-k+1} \end{eqnarray*}$ durch sie entstehen, indem man sie an die von links aus gesehen $\begin{eqnarray*} a_{n-k+1} \end{eqnarray*}$ -te Stelle setzt (wobei ganz links außen die 0-te Stelle ist).
Ich glaube, das kann man noch schöner formulieren; entsteht auf diese Weise nicht einfach die zur Inversionstafel $\begin{eqnarray*} (a_n, a_{n-1}, ..., a_1) \end{eqnarray*}$ gehörige Permutation?

Ja, ich denke das geht so. Freude

Punkt 2) ? Nun, $\begin{eqnarray*} a_1+\ldots+a_n \end{eqnarray*}$ ist ja einfach die Inversionsanzahl der so konstruierten Permutation. Wenn wir nun schauen, wieviele Permutationen auf dieselbe Inversionsanzahl $\begin{eqnarray*} k \end{eqnarray*}$ kommen, dann ist das ja nach Definition $\begin{eqnarray*} I_n(k) \end{eqnarray*}$ , andererseits aber gleich der Anzahl der Tupel $\begin{eqnarray*} (a_1,\ldots,a_n) \end{eqnarray*}$ in unserer Summe mit der Eigenschaft $\begin{eqnarray*} a_1+\ldots+a_n=k \end{eqnarray*}$ - nun, genau das was wir brauchen. Augenzwinkern

27.10.2018, 16:48

Studentu

Auf diesen Beitrag antworten »

Danke, HAL 9000!
Mit deinen Erklärungen macht nun alles Sinn. Freude

Neue Frage »

Antworten »

Anzahl der Permutationen

Verwandte Themen