Abzählen der Abstiege in einer Permutation

Neue Frage »

lagrange92 Auf diesen Beitrag antworten »
Abzählen der Abstiege in einer Permutation
Meine Frage:
Eine Permutation hat einen Abstieg, wenn . A(n,k)sei die Anzahl der Permutationen in mit k-1 Abstiegen. Weiter ist .
i). Zeigen sie .

Meine Ideen:
Ich suche ja nun alle Permutationen, die eben gerade einen Abstieg haben. Ich weis aber nicht recht, wie ich das angehen soll. Ich habe schon gezeigt, dass A(n,1)=1 gilt, könnte man damit vielleicht schon etwas anfangen? unglücklich
Hat vielleicht jemand einen Tipp?
Danke. smile
Leopold Auf diesen Beitrag antworten »

Wie wäre es mit vollständiger Induktion und mit



Stelle dir vor, du hättest eine Permutation mit genau einem Abstieg



wobei . Jetzt fügst du das Element irgendwo ein und erhältst so eine Permutation . Wenn du es irgendwo vor einfügst, bekommst du zwei Abstiege, den von zu seinem rechten Nachbarn und den alten von zu . Wenn du zwischen und einfügst, behältst du den einen Abstieg, jetzt zwischen und . Und rechts von darfst du nur noch ganz hinten ansetzen, wenn du die Anzahl der Abstiege nicht vergrößern willst.
Das sollte oben den Summanden erklären. Zum andern Summanden kannst du dir selber ein paar Gedanken machen.
lagrange92 Auf diesen Beitrag antworten »

Dank dir habe ich den ersten Teil hingebracht. :-)
Allerdings hat sie noch einen zweiten Teil, bei welch em ich noch hänge. Für soll ich zeigen:
A (n+1, k)=kA (n, k)+(n-k+2)A (n, k-1).
Jetzt habe ich als Tipp die Menge der Permutationen in mit k-1 Abstiegen zu betrachten und n aus dieser Menge aus diesen Permutationen heraus zu nehmen und dann zu unterscheiden, ob auch dann noch ein aAbstieg vorliegt, gerade die Mengen, über die man summieren muss denke ich. Für den Fall, dass kein Abstieg vorliegt habe ich mir überlegt, dass ich betrachten muss, wie wir es auch zuvor gemacht haben, aber ich weis nicht genau, wie ich hier abzählen soll.
Bei dem anderen Teil wo dann wieder ein Abstieg vorliegt, hat man ja dann A (n-1, k).
Allerdings hört es da mit dem Verständnis auf. Ich danke dir schon mal für deine Hilfe. :-)
HAL 9000 Auf diesen Beitrag antworten »

Eigentlich musst du die Erklärung von Leopold (die den Fall k=2 betrifft) nur leicht variieren:

Statt einem solchen ba-Abstieg in der Permutation hast du nun solche Abstiege, was sich auf die Anzahl der möglichen Einfügestellen in der Erklärung auswirkt. Aber vom Prinzip her gibt es da nichts anderes, neues zu beachten.
lagrange92 Auf diesen Beitrag antworten »

Gut, dann schau ich nochmal, danke.
lagrange92 Auf diesen Beitrag antworten »

Es hat geklappt, danke. Wink
 
 
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »