Subfakultät

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

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

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 Beziehung $\phi(m)\neq m$ gilt. Die Subfakultät von $n$ ist definiert als

$!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!}+ ... +(-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 und !10 = 1 334.961 (Folge A000166 in OEIS).

[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

$!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]$

Wird in der letzten Formel vor der Division noch die Zahl Eins aufaddiert, 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.

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