TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 167

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

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

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)\leq k+1$ nur für alle $i\leq k\leq 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)\leq 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}$.