Wieviele Möglichkeiten gibt es zehn Personen auf zehn Plätzen so umzusetzen, dass keiner auf seinem alten Platz sitzt?
In einem Fernsehstudio sitzen zehn Zuschauer auf einer kleinen Tribüne mit zehn Plätzen. Für die Aufzeichnung einer zweiten Sendung sollen die Zuschauer so umgesetzt werden, dass keiner auf seinem alten Platz sitzt. Wieviele Möglichkeiten gibt es, diese so umzusetzen?
Zur Vereinfachung des Problems stellen wir uns vor, dass wir zehn Würfel mit den Zahlen 1 bis 10 haben und es zehn Plätze gibt, die von 1 bis 10 nummeriert sind. Wieviele Möglichkeiten gibt es also die Würfel so anzuordnen, dass keine Würfelnummer mit der Platznummer übereinstimmt.
Das Folgeglied a[n] beschreibt die Anzahl der Möglichkeiten n durchnummerierte Würfel auf n durchnummerierte Plätze zu verteilen, ohne dass eine Würfelnummer mit der Platznummer übereinstimmt.
Fangen wir klein und schauen uns das Problem für kleine n an. Bei einem Würfel gibt es keine Lösung. Bei zwei Würfeln gibt es die Möglichkeit (21) und damit eine Lösung. Bei drei Würfeln gibt es die Möglichkeiten (231) und (312) und damit zwei Lösungen. Probiert man vier Würfel durch, dann bekommt man neun Lösungen.
Wie sieht es nun für a[5] aus. Für den ersten Platz kommen nur die Zahlen 2 bis 5 in Frage und damit gibt es vier Möglichkeiten. Auf die Plätze 2 bis 5 müssen nun vier Würfel verteilt werden. Dabei entsprechen jeweils drei Würfeln Platznummern und ein Würfel enspricht keiner Platznummer. Damit haben wir ein neues Problem:
Wieviele Möglichkeiten gibt es n-1 durchnummerierte Würfel und einen nicht nummerierten Würfel auf n durchnummerierte Plätze zu verteilen, ohne dass Platznummern und Würfelnummern übereinstimmen?
Zur Vereinfachung können wir den nicht nummerierten Würfel weglassen und uns einfach eine leeren Platz vorstellen.
Das Folgeglied b[n] beschreibt die Anzahl der Möglichkeiten n-1 durchnummerierte Würfel auf n durchnummerierte Plätze zu verteilen, ohne dass eine Würfelnummer mit einer Platznummer übereinstimmt.
Für das Folgeglied a[5] bzw. a[n] gilt dann
a[5] = 4 · b[4] bzw. a[n] = (n-1) · b[n-1] (1)
Fangen wir wieder klein an und schauen uns auch das zweite Problem für kleine n an. Bei einem Platz gibt es eine Lösung (.). Bei zwei Plätzen gibt es die Möglichkeit (.1) und damit ebenfalls eine Lösung. Bei drei Plätzen gibt es die Möglichkeiten (.12), (2.1) und (21.) und damit drei Lösungen.
Für b[4] gibt es zwei Situationen.
Der letzte Platz (4) ist leer. Dann gibt es genau a[3] = 2 Möglichkeiten der Anordnung der restlichen Würfel.
Der letzte Platz ist nicht leer. Dann gibt es genau b[3] = 3 Möglichkeiten der Anordnung der restlichen Würfel. Allerdings tritt der Fall drei mal auf.
Damit folgt: b[4] = 2 + 3 · 3 = 11.
Übertragen auf die allgemeine Lösung b[n] heißt das:
Der letzte Platz ist leer. Dann gibt es genau a[n-1] Möglichkeiten der Anordnung der restlichen Elemente.
Der letzte Platz ist nicht leer. Dann gibt es genau b[n-1] Möglichkeiten der Anordnung der restlichen Elemente. Allerdings tritt der Fall n-1 mal auf.
Damit folgt:
b[n] = a[n-1] + (n-1) · b[n-1]
Mit der Gleichung (1) folgt dann:
b[n] = a[n-1] + a[n]
Wir setzen in Gleichung (1) ein und erhalten:
a[n] = (n-1) · (a[n-1] + a[n-2])
Zusammen mit den oben bereits berechneten Werten ergibt sich folgende rekursive Formel:
a[1]=0; a[2]=1 a[n]=(n-1) · (a[n-1] + a[n-2])
Nun können wir (oder der Taschenrechner) den Wert für 10 Zuschauer berechnen.
a[3] = 2
a[4] = 9
a[5] = 44
a[6] = 265
a[7] = 1854
a[8] = 14 833
a[9] = 133 496
a[10] = 1 334 961
Es gibt also 1 334 961 Möglichkeiten die zehn Zuschauer so umzusortieren, dass keiner auf seinem alten Platz sitzt.
