Subfakultät

Poll without page-refresh

Article on other languages:

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: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}\}|.$

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

(Folge A000166 in OEIS).

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
a_n	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))$

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: Subfactorial auf MathWorld (englisch)
Folge A000166 in OEIS

Von „http://de.wikipedia.org/wiki/Subfakult%C3%A4t“

Kategorie: Kombinatorik

This article is from Wikipedia. All text is available under the terms of the GNU Free Documentation License.

Giant Panda

Mercedes Car

This site monitored by SitePinger.net