Fallende Faktorielle

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

Die Begriffe der fallenden Faktoriellen, in Symbolen

$x^{\underline{m}} \qquad \mbox{oder} \qquad (x)_m,$

und der steigenden Faktoriellen, in Symbolen

$x^{\overline{m}} \qquad \mbox{oder} \qquad (x)^m,$

treten in der Kombinatorik im Zusammenhang mit einer allgemeinen Definition des Binomialkoeffizienten auf.

[Bearbeiten] Definitionen und Bedeutung

Die fallende Faktorielle $x^{\underline{m}} = (x)_m$ ist definiert als

$x^{\underline{m}} = x(x-1)(x-2) \cdots (x-m+1) = \prod_{i=0}^{m-1} (x-i)$ .

Sie bezeichnet die Anzahl der geordneten Proben vom Umfang m ohne Wiederholung aus einer x-elementigen Teilmenge, oder äquivalent: die Variation von x Elementen zur Klasse m ohne Wiederholung. Beispielsweise gibt es $(x) m$ Möglichkeiten, m unterscheidbare Kugeln so auf x Urnen zu verteilen, dass keine Urne mehr als eine Kugel enthält. Die steigende Faktorielle $x^{\overline{m}} = (x)^m$ wird analog definiert:

$x^{\overline{m}} = x(x+1)(x+2) \cdots (x+m-1) = \prod_{i=0}^{m-1} (x+i)$ .

Den Zusammenhang zum Binomialkoeffizienten schaffen folgende Beziehungen:

${x \choose k} = \frac{x^{\underline{k}}}{k!} = \frac{(x)_k}{k!}, \qquad {x + k - 1 \choose k} = \frac{x^{\overline{k}}}{k!} = \frac{(x)^k}{k!}$ .

Um mit fallenden Faktoriellen arbeiten zu können sind folgende Beziehungen sehr hilfreich:

$1^{\underline{m}} = 0$

$x^{\underline{1}} = x^{\overline{1}} = x$

$x^{\underline{0}} = 1$

$(-x)^{\overline{m}} = (-1)^mx^{\underline{m}}$

Es gelten außerdem die rekursiven Beziehungen:

$x^{\underline{m}} = x^{\underline{m-1}}(x-m+1)$

oder allgemeiner:

$x^{\underline{m+n}} = x^{\underline{m}}(x-m)^{\underline{n}}$

$xx^{\underline{m}} = x^{\underline{m+1}}+mx^{\underline{m}}$

[Bearbeiten] Notation

Üblicherweise wird für die fallende Faktorielle das Symbol $(x) k$ verwendet. Da das jedoch zu Verwechslungen mit einer gebräuchlichen Notation für das Pochhammer-Symbol führen kann, verwendet man manchmal auch das Symbol $x^{\underline{k}}$ . Entsprechendes gilt für die Notation der steigenden Faktoriellen.