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

Aus VoWi
Zur Navigation springen Zur Suche springen

Wieviele Permutationen von [1,2,...,n] gibt es mit für alle ?

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 -> ist entweder 1 oder 2.

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

k=3 -> ist entweder 1, 2, 3 oder 4, jedoch muss man bedenken, dass entweder 1 & 2 oder 1 & 3 oder 2 & 3 schon bzw. 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 Möglichkeiten von Permutationen von gibt.

lg f.l.o.


Hinweis: Nach längerer Überlegung glaub ich, dass die Lösung doch . Z.b. bei der Menge M={1,2} gibt es genau 2 Permutationen, da ja die Bedingung nur für alle . 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:

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