Subfakultät

Die Subfakultät ist eine mathematische Funktion, die hilfreich bei der Berechnung von bestimmten Permutationen ist.

Berechnung für !n

!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 11 Subfakultäten sind !0 = 1, !1 = 0, !2 = 1, !3 = 2, !4 = 9, !5 = 44, !6 = 265, !7 = 1 854, !8 = 14 833, !9 = 133 496 und !10 = 1 334 961 (Folge A000166 in OEIS)

Beispiel einer Anwendung

Angenommen man hat 6 verschiedenfarbige Kugeln, und zu jeder Kugel ein Kästchen in der passenden Farbe. Weiter angenommen jede der Kugeln liegt in einem der Kästchen, wieviele Möglichkeiten gibt es, dass keine der Kugeln in einem Kästchen ihrer Farbe liegt.

Des Rätsels Lösung: Es sind $!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$ Möglichkeiten.

Im Gegensatz zur Subfakultät werden bei der Fakultät alle Möglichkeiten (Permutationen) berechnet.

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 vor der Division noch ein Faktor von Eins addiert, dann erspart man sich die Unterscheidung, wann man abrunden und wann man aufrunden muß, und kann stattdessen den Nachkommateil einfach abschneiden:

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

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

a_{n}=n*a_{n-1}+(n-1)*a_{n-2}

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

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

!n=(n-1)*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
a_n	1	1	3	11	53	309	2.119	16.687	148.329	1.468.457	16.019.531

Eine rekursive Formel ist folgende:

!n=!(n-1)*n+(-1)^{n}

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

|http://mathworld.wolfram.com/Subfactorial.html