Subfakultät

Bedeutung der Subfakultät

Die Subfakultät ist eine Funktion aus der Kombinatorik. Für eine natürliche Zahl n gibt sie an, wie viele fixpunktfreie Permutationen einer Menge mit n Elementen es gibt, und wird als !n geschrieben. Eine Permutation ordnet die Elemente einer Menge neu an; sie ist fixpunktfrei, wenn kein Element an seiner ursprünglichen Stelle bleibt. Solche Permutationen heißen auch Derangements.

Zum Vergleich: Die Fakultät n! zählt alle möglichen Permutationen einer n-elementigen Menge. Die Subfakultät zählt daraus nur diejenigen ohne Fixpunkt. Beispielsweise gelten !0 = 1, !1 = 0, !2 = 1, !3 = 2, !4 = 9, !5 = 44 und !6 = 265.

Definition und direkte Berechnung

Für n ≥ 0 ist die Subfakultät definiert durch

!n = n! · Σ(k=0 bis n) ((−1)^k / k!)

beziehungsweise

!n = n! · (1 − 1/1! + 1/2! − 1/3! + ··· + (−1)^n/ n!).

Die alternierenden Vorzeichen sind ein wesentliches Merkmal dieser Formel. Sie liefert die Anzahl der fixpunktfreien Permutationen direkt aus der Fakultät.

Näherungen und Rekursionen

Die Subfakultät ist eng mit der eulerschen Zahl e verbunden. Eine sehr gute Näherung lautet

!n ≈ n!/e.

Für n ≥ 1 ergibt das Runden auf die nächstliegende ganze Zahl sogar den exakten Wert:

!n = [n!/e].

Dabei bezeichnet [x] die x nächstliegende ganze Zahl. Eine weitere exakte Rundungsdarstellung ist

!n = ⌊(n! + 1)/e⌋

für n ≥ 1. Die Gaußklammer ⌊x⌋ bedeutet, dass der Nachkommateil abgeschnitten wird.

Zur schrittweisen Berechnung können rekursive Formeln verwendet werden:

!n = n · !(n−1) + (−1)^n

und

!n = (n−1) · (!(n−1) + !(n−2)).

In der zweiten Formel entspricht !(n−1) + !(n−2) der Anzahl fixpunktfreier Permutationen einer n-elementigen Menge, bei denen ein Element fest vorgegeben ist.

Beispiel mit farbigen Kugeln

Es gibt sechs verschiedenfarbige Kugeln und zu jeder Farbe ein passendes Kästchen. Gesucht sind Verteilungen, bei denen jedes Kästchen genau eine Kugel enthält, aber keine Kugel im Kästchen ihrer eigenen Farbe liegt. Das ist genau eine fixpunktfreie Permutation der sechs Kugeln.

Mit der Definitionsformel ergibt sich

!6 = 6! · (1 − 1/1! + 1/2! − 1/3! + 1/4! − 1/5! + 1/6!) = 265.

Es gibt also 265 mögliche Verteilungen.

Erweiterung und Zahlenspiel

Die Subfakultät kann mit einer Integraldarstellung von natürlichen Zahlen auf komplexe Zahlen erweitert werden:

!z = ∫₀^∞ e^(−t)(t−1)^z dt.

Dabei gilt z ∈ ℂ und Re(z) > −1; Re(z) bezeichnet den Realteil von z. Außerdem gilt die Darstellung !n = Γ(n+1, −1)/e mit der unvollständigen Gammafunktion Γ.

In der Unterhaltungsmathematik wird die einzige subfakultative narzisstische Zahl genannt. Sie ist gleich der Summe der Subfakultäten ihrer Dezimalziffern:

148349 = !1 + !4 + !8 + !3 + !4 + !9.

In anderen Zahlensystemen können ebenfalls Zahlen mit dieser Eigenschaft vorkommen. In Basis 5 gilt zum Beispiel 9 = 1 · 5 + 4 = !1 + !4 = 0 + 9. Die Basis 5 ist die kleinste Basis, in der eine Zahl mit dieser Eigenschaft existiert.