Subfakultät

Die Subfakultät ist eine vornehmlich in dem mathematischen Gebiet der Kombinatorik auftretende Funktion. Die Subfakultät gibt die Anzahl der fixpunktfreien Permutationen (auch Derangements) auf einer endlichen Menge an. Sie ist eng mit der Fakultät verwandt, welche die Gesamtzahl der Permutationen auf einer endlichen Menge angibt.

Formale Definition

Es sei $n\in\mathbb{N}_0$ und $M = \{1,2,\ldots,n\}$. Eine Abbildung $\phi\colon M\rightarrow M$ heißt fixpunktfrei, wenn für alle $m\in M$ die Ungleichung $\phi(m)\neq m$ gilt, und bijektiv, wenn sie anschaulich nur die Reihenfolge der Elemente von M verändert. Die Subfakultät von n ist definiert als die Anzahl der fixpunktfreien bijektiven Abbildungen $\phi\colon M\rightarrow M$, also

$!n = |\{\phi\colon M\rightarrow M\mid\phi\mbox{ bijektiv und fixpunktfrei}\}|.$

Formel für !n

Die Subfakultät kann mit Hilfe der Fakultät explizit berechnet werden. Es gilt:

$!n = n!\left(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}\pm \cdots +(-1)^n\frac{1}{n!}\right) = n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}$

Die ersten elf Werte der Subfakultät sind:

• !0 = 1
• !1 = 0
• !2 = 1
• !3 = 2
• !4 = 9
• !5 = 44
• !6 = 265
• !7 = 1854
• !8 = 14.833
• !9 = 133.496
• !10 = 1.334.961

Beispiel einer Anwendung

Angenommen man hat 6 verschiedenfarbige Kugeln, und zu jeder Kugel ein Kästchen in der passenden Farbe. Zu bestimmen ist die Anzahl der Möglichkeiten, die Kugeln so auf die Kästchen zu verteilen, dass jedes Kästchen genau eine Kugel enthält, aber keine Kugel in einem gleichfarbigen Kästchen zu liegen kommt.

Nach der Definition der Subfakultät gibt es genau !6 Möglichkeiten. Mit Hilfe der obigen Formel berechnet man $!6 = 6!\cdot\left(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\frac{1}{5!}+\frac{1}{6!}\right) = 265$.

Weitere Möglichkeiten zur Berechnung

• Es gilt

$!n = \frac{\Gamma(n+1, -1)}{e}$

mit der Eulerschen Zahl e und der unvollständigen Gammafunktion Γ.

• $!n \approx \frac{n!}{e}$ stellt eine sehr gute Näherung dar.

Wird entsprechend gerundet, bekommt man eine exakte Formel:

• $!n = \left[ \frac {n!}{e} \right]$

wobei zur nächstliegenden ganzen Zahl gerundet wird. Wird in der letzten Formel vor der Division noch die Zahl Eins addiert, so erspart man sich die Unterscheidung, ob ab- oder aufgerundet werden muss. Stattdessen schneidet man den Nachkommateil einfach ab:

• Für $n\geq 1$: $!n = \left\lfloor \frac{n!+1}{e} \right\rfloor$ nach Mehdi Hassani (vgl. Gaußklammer.)

Vergleich der Näherungen
n	$\frac{n!}{e}$	$\left[ \frac {n!}{e} \right]$	$\frac{n!+1}{e}$	$\left\lfloor \frac{n!+1}{e} \right\rfloor$
1	0,3679	0	0,7358	0
2	0,7358	1	1,1036	1
3	2,2073	2	2,5752	2
4	8,8291	9	9,1970	9
5	44,1455	44	44,5134	44
6	264,8732	265	265,2411	265
7	1854,1124	1854	1854,4803	1854
8	14832,8991	14833	14833,2669	14833
9	133496,0916	133496	133496,4595	133496

• Es existiert eine Folge mit den Anfangsgliedern a₀=1 und a₁=1, und der rekursiven Berechnungsvorschrift:

$a_n = n\cdot a_{n-1} + (n-1)\cdot a_{n-2} = \ !(n+1)+!n$

so dass folgende Folge entsteht: 1, 1, 3, 11, 53, 309, 2 119 ... (Folge A000255 in OEIS)

Die Subfakultät lässt sich nun nach folgender Formel berechnen:

$!n = (n-1)\cdot a_{n-2}$

!n	0	0	1	2	9	44	265	1.854	14.833	133.496	1.334.961
n	0	1	2	3	4	5	6	7	8	9	10
an	1	1	3	11	53	309	2.119	16.687	148.329	1.468.457	16.019.531

• Die beiden folgenden Formeln sind rekursiv:

$!n = !(n-1)\cdot n + (-1)^n$

$!n = (n-1)\cdot (!(n-1)+!(n-2))$

• Die Integraldarstellung verallgemeinert die Subfakultät um ihren Definitionsbereich von den natürlichen bis hin zu den komplexen Zahlen:

$!z = \int_0^\infty \mathrm e^{-t} (t-1)^z \mathrm dt, \qquad \operatorname{Re}(z) > -1$

Subfakultative narzisstische Zahl

Die einzige Zahl, die gleich der Summe ihrer der Subfakultät unterzogenen Ziffern ist, lautet:

148 349 = !1 + !4 + !8 + !3 + !4 + !9

Weblinks

• Eric W. Weisstein: Subfakultät. In: MathWorld. (englisch)
• Folge A000166 in OEIS