Subfakultät

aus Wikipedia, der freien Enzyklopädie

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.

[Bearbeiten] Formale Definition

Es sei $n\in\mathbb{N}_0$ und $M = \{1,2,\ldots,n\}$ . Eine Abbildung $\phi: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:M\rightarrow M$ , also

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

[Bearbeiten] 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

[Bearbeiten] 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$ .

[Bearbeiten] 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