Subfakultät-Rechner

Ermitteln Sie die Anzahl der fixpunktfreien Permutationen von n Objekten.

So wird gerechnet

Die Subfakultät !n zählt die fixpunktfreien Permutationen: Anordnungen von n verschiedenen Objekten, bei denen kein Objekt an seiner ursprünglichen Position landet. Das Werkzeug verwendet die Rekursion !n = (n − 1) × (!(n − 1) + !(n − 2)) mit !0 = 1 und !1 = 0. Gleichwertig ist !n die der Zahl n! / e nächstgelegene ganze Zahl.

n muss eine ganze Zahl zwischen 0 und 170 sein; eine Dezimalzahl wie 5,5 liefert kein Ergebnis. Die Werte wachsen schnell, und ab etwa n = 18 übersteigen die Zwischenergebnisse das, was gewöhnliche Gleitkommaarithmetik exakt darstellen kann, sodass bei sehr großen Ergebnissen nur die führenden Ziffern verlässlich sind. Für n = 1 lautet die Antwort 0, weil sich ein einzelnes Objekt nicht verschieben lässt.

Rechenbeispiel

Für n = 5: !0 = 1, !1 = 0; !2 = 1 × (0 + 1) = 1; !3 = 2 × (1 + 0) = 2; !4 = 3 × (2 + 1) = 9; !5 = 4 × (9 + 2) = 44; Probe: 5! / e = 120 / 2,71828 ≈ 44,15, nächste ganze Zahl 44. Das Werkzeug zeigt 44.

Dieses Beispiel ausprobieren →

Häufige Fehler

  • !n mit n! verwechseln: Für 5 sind es 44 und 120.
  • Annehmen, !n zähle Permutationen, bei denen sich mindestens ein Objekt bewegt; das wäre n! − 1. Bei einer fixpunktfreien Permutation muss sich jedes Objekt bewegen.
  • „!5“ aus einer anderen Schreibweise als Fakultät lesen; hier steht das Ausrufezeichen vorn.
  • Bei großem n jeder Ziffer des Ergebnisses trauen; Ergebnisse ab etwa n = 18 sind Näherungen.

Quellen

Über diesen Rechner

Die Subfakultät !n, auch Anzahl der fixpunktfreien Permutationen von n genannt, zählt die Permutationen von n Objekten, bei denen kein Objekt an seiner ursprünglichen Position landet. Sie ist definiert durch !n = n! · Σ(k=0 bis n) (−1)^k/k! und liegt für großes n sehr nahe bei n!/e – tatsächlich ist !n die der Zahl n!/e nächstgelegene ganze Zahl. Beispielsweise ist !4 = 9: Von den 24 Permutationen von 4 Objekten lassen nur 9 jedes Objekt auf einem anderen Platz.

Die klassische Veranschaulichung ist das „Hutproblem“ (oder „Problem der falsch adressierten Briefe“): Geben n Personen ihre Hüte an der Garderobe ab und werden sie zufällig zurückgegeben, ist !n die Anzahl der Möglichkeiten, dass jede einzelne Person den falschen Hut zurückbekommt. Studierende der Kombinatorik, Wahrscheinlichkeitskurse und Rätselfreunde nutzen Subfakultätsberechnungen, um Aufgaben zu fixpunktfreien Permutationen zu lösen, und das Konzept reicht bis in Kryptografie und Codierungstheorie, wo immer Permutationen nach dem Muster „nichts bleibt auf seinem ursprünglichen Platz“ eine Rolle spielen.

War das hilfreich?

Sie können bis zu 3 Reaktionen auswählen.

Kommentare

  • Schreiben Sie den ersten Kommentar.

Beliebte Rechner

Alle Rechner