obwohl ich im Mathe-LK gar nicht mal so schlecht war, beiße ich mir gerade die Zähne aus am Aufstellen einer Formel für folgendes Problem:
„Gegeben sind n Steinchen, die in n Kuhlen liegen.
Wieviele Möglichkeiten gibt es, die n Steinchen auf die n Kuhlen neu zu verteilen, ohne dass auch nur eines davon wieder an seinem ursprünglichen Ort liegt?“
Mit Zählen (und bei größerem n mit Hilfe von Tabellenkalkulation) komme ich zwar zu Ergebnissen:
Lösung für n=3 ist: 2 zulässige von insgesamt 6 Möglichkeiten,
Lösung für n=4 ist: 9 zulässige von insgesamt 24 Möglichkeiten,
Lösung für n=5 ist: 44 zulässige von insgesamt 120 Möglichkeiten.
Der Anfang zur Formelaufstellung ist ebenfalls einfach:
Das erste Steinchen darf in genau (n-1) Kuhlen gelegt werden.
Aber schon beim zweiten hängt die Zahl der Möglichkeiten davon ab, wo man das erste hingelegt hatte: Liegt das erste genau in der zweiten Kuhle, hat das zweite Steinchen (n-1) Möglichkeiten, sonst nur (n-2). und so geht das dann weiter…
…wie kann man dessen Herr werden?
Vielen Dank im Voraus für Anregungen und Lösungen!
„Gegeben sind n Steinchen, die in n Kuhlen liegen.
Wieviele Möglichkeiten gibt es, die n Steinchen auf die n
Kuhlen neu zu verteilen, ohne dass auch nur eines davon wieder
an seinem ursprünglichen Ort liegt?“
Du suchst die Anzahl der fixpunktfreien Permutationen auf einer endlichen Menge (Mächtigkeit = n). Diese Anzahl ist gleich der sogenannten Subfakultät von n, geschrieben !n.
Die Definition (eine von mehreren einander äquivalenten) der Subfakultät lautet:
!n = n! ∑k = 0…n (–1)k/k!
Bemerkenswerterweise ist !n gleich dem e-ten Teil von n!, wenn man auf die nächstkleinere ganze Zahl rundet: !n = [n!/e] wobei „[]“ die Gaußklammer bezeichnet.
Weitere Informationen dazu findest Du in der Wikipedia:
„Gegeben sind n Steinchen, die in n Kuhlen liegen.
Wieviele Möglichkeiten gibt es, die n Steinchen auf die n
Kuhlen neu zu verteilen, ohne dass auch nur eines davon wieder
an seinem ursprünglichen Ort liegt?“
Du suchst die Anzahl der fixpunktfreien
Permutationen auf einer endlichen Menge (Mächtigkeit
= n). Diese Anzahl ist gleich der sogenannten Subfakultät von n, geschrieben !n.
Ah, super! Vielen Dank auch für die Formel!
Bemerkenswerterweise ist !n gleich dem e-ten Teil von n!, wenn
man auf die nächstkleinere ganze Zahl rundet: !n = [n!/e]
wobei „[]“ die Gaußklammer bezeichnet.
Das ist in der Tat erstaunlich. Mir war schon aufgefallen, daß die Anzehl der Gesamtmöglichkeiten geteilt durch die Anzahl der gültigen Möglichkeiten immer „so um die zwei-einhalb“ lag, hatte mir dabei aber vorsichtshalber nichts gedacht.
