Steigende und fallende Faktorielle

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.

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 den 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}}$

$x^{\underline x} =x^{\underline{x-1}}=x!$

mit der Fakultät x!

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}}$

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.

Explizite Formel

Eine explizite Formel für die Fallende Faktorielle $x^{\underline{m}} = (x)_m$ ist offensichtlich gegeben durch: $(x)_m = \frac{x!}{(x-m)!}$

Weblinks

• Erläuterung in MathWorld (engl.)