TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 162

Aus VoWi
Wechseln zu: Navigation, Suche

Wieviele Permutationen \pi von [1,2,...,n] gibt es mit \pi(k) \le k+1 für alle  1 \le k \le n - 1?

Ich bin mir sehr unsicher, ob das stimmmt, aber ich werde es mal als "Anregung" hinschreiben:

k=1 -> \pi(1) ist entweder 1 oder 2.

k=2 -> \pi(2) ist entweder 1, 2 oder 3, jedoch muss man bedenken, dass entweder 1 oder 2 schon \pi(1) ist und daher als Möglichkeit wegfällt.

k=3 -> \pi(3) ist entweder 1, 2, 3 oder 4, jedoch muss man bedenken, dass entweder 1 & 2 oder 1 & 3 oder 2 & 3 schon \pi(1) bzw. \pi(2) ist und daher als Möglichkeit wegfallen.

Führt man diese Überlegung weiter, sieht man, dass es für jedes k 2 Möglichkeiten gibt. Ich würde daher sagen, dass es 2^n Möglichkeiten von Permutationen von \pi gibt.

lg f.l.o.


Hinweis: Nach längerer Überlegung glaub ich, dass die Lösung doch 2^{n-1}. Z.b. bei der Menge M={1,2} gibt es genau 2 Permutationen, da ja die Bedingung \pi(k) \le k+1 nur für alle  i \le k \le n - 1. Ist auch logisch da ja für das Element n keine Auswahl getroffen werden kann sondern das letzte Element, das noch übrig ist genommen werden muss (wegen der Bijektivität). Also fällt ein *2 weg und imo ist die richtige Antwort: 2^{n-1}

--Davincho 85.127.81.94 23:36, 8. Okt. 2010 (CEST)

Die Lösung von Davincho ist richtig. Eine nachvollziehbare Erklärung wäre: für \pi(k) \le k+1 kommen nur solche Permutationen in Frage, wo ausschließlich benachbarte Elemente vertauscht werden. Denn vertauscht man zwei Elemente, die 2 oder mehr Plätze voneinander entfernt sind, gilt für das Bild des kleineren Elements \pi(k) > k+1 . In einer Folge von n Zahlen gibt es n-1 benachbarte Zahlen, zB n=5: (1,2),(2,3),(3,4),(4,5). Jetzt kann man in der Permutation beliebig viele dieser Paare vertauschen, also entweder gar keines (identische Permutation), nur eines (dafür gibt es 4 Möglichkeiten für n=5), usw. Das entspricht der Bildung von allen möglichen Mengen von solchen benachbarten Paaren. Das ist genau die Potenzmenge über n-1 Elementen und die hat den Betrag 2^{n-1}.