Subfakultät

Praescriptum: Meine Antwort (C) gehörte nicht zu dieser, sondern zur vorigen Frage. @Mjinga hat auf meine Antwort auf ihre vorige Frage als Antwort eine neue Frage gestellt. Es ist also nicht so, dass ich auf diese Frage mit (C) geantwortet hätte *räusper*😉

https://twitter.com/Mjinga/status/337232057812017152

Erst von Hand versucht, alle Kombinationen aufzulisten. Auf 31 gekommen. Kann nicht sein.

Dann gedacht, wenn die Autos auch ihre Eingänge als Ausgänge nehmen dürften, wären es n! Möglichkeiten. 5! = 5*4*3*2*1 = 120. Das erste Auto darf bei einem der fünf Ausgänge nicht rausfahren, bleiben 4/5 der Möglichkeiten. Macht man das für alle fünf Autos, bleiben (4/5)^5 = 1024/3125 = 33 Prozent der ursprünglichen Möglichkeiten ohne die Einschränkung Ausfahrt ≠ Einfahrt übrig. 120*1024/3125 = 39,3 ist auch schon nahe am wirklichen, ganzzahligen Ergebnis (s.u.) dran.

Dann Wikipedia aufgemacht unter Permutation und die „fixpunktfreie Permutation“ gefunden, die sich gut anhört. Das Auto, das bei 1 reingefahren ist, kann bei 2, 3, 4 oder 5 rausfahren, aber nicht bei 1 und auch nicht bei größer 5, weil es dann mehr als eine ganze Runde gedreht hätte. Das Nicht-bei-1 bedeutet, es sind nur fixpunktfreie Permutationen erlaubt. Permutationen, weil alle Autos in verschiedene Richtungen rausfahren, das heißt, jede Richtung wird von einem Auto bedient, welches zuvor aus einer anderen Richtung hereingefahren ist.

Die Anzahl fixpunktfreier Permutationen gibt Wikipedia an mit der Subfakultät, ein Begriff, den ich noch nie gehört hab. Die Subfakultät !n ist definiert als:

!n = n! * Summe(k=0;n;(-1)^k/k!)

Für den Fall n = 5 ist das:

!5 = 5! * (1/0! – 1/1! + 1/2! – 1/3! + 1/4! – 1/5!)
= 120 * (1/1 – 1/1 + 1/2 – 1/6 + 1/24 – 1/120)
= 120 * (120 – 120 + 60 – 20 + 5 – 1) / 120
= 60 – 20 + 5 – 1
= 44

Wenn ich nun noch mal die Kombinationen von Hand aufzustellen versuche, kann ich auf 44 kommen:

Nr. 1 2 3 4 5
1 2 1 4 5 3
2 2 1 5 3 4
3 2 3 1 5 4
4 2 3 4 5 1
5 2 3 5 1 4
6 2 4 1 5 3
7 2 4 5 1 3
8 2 4 5 3 1
9 2 5 1 3 4
10 2 5 4 1 3
11 2 5 4 3 1
12 3 1 2 5 4
13 3 1 4 5 2
14 3 1 5 2 4
15 3 4 1 5 2
16 3 4 2 5 1
17 3 4 5 1 2
18 3 4 5 2 1
19 3 5 1 2 4
20 3 5 2 1 4
21 3 5 4 1 2
22 3 5 4 2 1
23 4 1 2 5 3
24 4 1 5 2 3
25 4 1 5 3 2
26 4 3 1 5 2
27 4 3 2 5 1
28 4 3 5 1 2
29 4 3 5 2 1
30 4 5 1 2 3
31 4 5 1 3 2
32 4 5 2 1 3
33 4 5 2 3 1
34 5 1 2 3 4
35 5 1 4 2 3
36 5 1 4 3 2
37 5 3 1 2 4
38 5 3 2 5 1
39 5 3 4 1 2
40 5 3 4 2 1
41 5 4 1 2 3
42 5 4 1 3 2
43 5 4 2 1 3
44 5 4 2 3 1

Das Schöne an der Subfakultät ist, dass sie im Verhältnis zur Fakultät schnell gegen 1/e geht mit der Eulerschen Zahl e = 2,71828. Schon bei n = 4 oder niedriger dürfte diese Näherung ausreichen, um es in Multiple-Choice-Optionen einrasten zu lassen. In unserem Fall ist 120/e = 44,15. Im Fall n = 4 ist !4 = 9, während 4!/e = 8,83 ist. Im Fall n = 3 ist !3 = 2, während !3/e = 1,10 ist.

Wenn man sich das merken könnte, könnte man die Näherung in Multiple-Choice-Aufgaben anwenden, wo n > 3 ist.

Schreibe einen Kommentar

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s


%d Bloggern gefällt das: