Bell-Polynom

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Im mathematischen Teilgebiet der Kombinatorik bezeichnen die Bell-Polynome, benannt nach Eric Temple Bell, folgende dreieckige Anordnung von Polynomen

B_{n,k}(x_1,x_2,\dots,x_{n-k+1})
=\sum{n! \over j_1!j_2!\cdots j_{n-k+1}!}
\left({x_1\over 1!}\right)^{j_1}\left({x_2\over 2!}\right)^{j_2}\cdots\left({x_{n-k+1} \over (n-k+1)!}\right)^{j_{n-k+1}},

wobei die Summe über alle Sequenzen j1, j2, j3, ..., jnk+1 der nicht-negativen ganzzahligen Werte gebildet wird, so dass

j_1+j_2+\cdots = k\quad\mbox{und}\quad j_1+2j_2+3j_3+\cdots=n.

Vollständige Bell-Polynome[Bearbeiten]

Die Summe

B_n(x_1,\dots,x_n)=\sum_{k=1}^n B_{n,k}(x_1,x_2,\dots,x_{n-k+1})

wird manchmal als ntes vollständiges Bell-Polynom bezeichnet. Zur besseren Abgrenzung gegenüber den vollständigen Bell-Polynomen, werden die oben definierten Polynome Bnk auch manchmal als "unvollständige" Bell-Polynome bezeichnet.

Die vollständigen Bell-Polynome genügen folgender Gleichung

B_n(x_1,\dots,x_n) = \det\begin{bmatrix}x_1 & {n-1 \choose 1} x_2 & {n-1 \choose 2}x_3 & {n-1 \choose 3} x_4 & {n-1 \choose 4} x_5 & \cdots & \cdots & x_n \\  \\
-1 & x_1 & {n-2 \choose 1} x_2 & {n-2 \choose 2} x_3 & {n-2 \choose 3} x_4 & \cdots & \cdots & x_{n-1} \\  \\
0 & -1 & x_1 & {n-3 \choose 1} x_2 & {n-3 \choose 2} x_3 & \cdots & \cdots & x_{n-2} \\  \\
0 & 0 & -1 & x_1 & {n-4 \choose 1} x_2 & \cdots  & \cdots & x_{n-3} \\  \\
0 & 0 & 0 & -1 & x_1 & \cdots & \cdots & x_{n-4} \\  \\
0 & 0 & 0 & 0 & -1 & \cdots & \cdots & x_{n-5} \\  \\
\vdots & \vdots & \vdots &  \vdots & \vdots & \ddots & \ddots & \vdots  \\  \\
0 & 0 & 0 & 0 & 0 & \cdots & -1 & x_1  \end{bmatrix}.

Kombinatorische Bedeutung[Bearbeiten]

Wird die ganze Zahl n zu einer Summe zerlegt, in der die "1" j1 mal vorkommt, die "2" j2 mal vorkommt, etc., dann entspricht die Anzahl der möglichen Partitionen einer Menge der Größe n, so dass die Vereinigung die Originalmenge ergibt, dem jeweiligen Koeffizienten des Bell-Polynoms. B_{n,k} ist dann die Summe aus allen Monomen vom Grad k.

Beispiele[Bearbeiten]

Es gilt beispielsweise

B_{6,2}(x_1,x_2,x_3,x_4,x_5)=6x_5x_1+15x_4x_2+10x_3^2

da es

6 Möglichkeiten gibt, eine Menge mit 6 Elementen zu zwei Mengen mit 5 und 1 Elementen zu partitionieren,
15 Möglichkeiten gibt, eine Menge mit 6 Elementen zu zwei Mengen mit 4 und 2 Elementen zu partitionieren, und es
10 Möglichkeiten gibt, eine Menge mit 6 Elementen zu zwei Mengen mit 3 und 3 Elementen zu partitionieren.

Als weiteres Beispiel gilt

B_{6,3}(x_1,x_2,x_3,x_4)=15x_4x_1^2+60x_3x_2x_1+15x_2^3

da es

15 Möglichkeiten gibt, eine Menge mit 6 Elementen zu drei Mengen mit jeweils 4, 1 und 1 Elementen zu partitionieren,
60 Möglichkeiten gibt, eine Menge mit 6 Elementen zu drei Mengen mit jeweils 3, 2 und 1 Elementen zu partitionieren, und es
15 Möglichkeiten gibt, eine Menge mit 6 Elementen zu drei Mengen mit jeweils 2, 2 und 2 Elementen zu partitionieren.

Eigenschaften[Bearbeiten]

  • B_{n,k}(1!,2!,\dots,(n-k+1)!) = \binom{n}{k}\binom{n-1}{k-1} (n-k)!

Bell-Polynome und Stirling-Zahlen[Bearbeiten]

Der Wert des Bell-Polynoms Bn,k(x1,x2,...), wenn alle xi gleich "1" sind, ist eine Stirling Zahl zweiter Art

B_{n,k}(1,1,\dots)=S(n,k)=\left\{{n\atop k}\right\}.

Die Summe

\sum_{k=1}^n B_{n,k}(1,1,1,\dots) = \sum_{k=1}^n \left\{{n\atop k}\right\}

entspricht der nten Bellzahl, welche die Anzahl der möglichen Partitionen einer Menge mit n Elementen beschreibt.

Faltungsidentität[Bearbeiten]

Für Folgen xn, yn, n = 1, 2, ..., lässt sich eine Art Faltung definieren:

(x \diamondsuit y)_n = \sum_{j=1}^{n-1} {n \choose j} x_j y_{n-j}.

wobei die Grenzen der Summe "1" und "n-1" anstelle von "0" und "n" sind.

Sei x_n^{k\diamondsuit}\, der nte Term der Folge

\displaystyle\underbrace{x\diamondsuit\cdots\diamondsuit x}_{k\ \mathrm{Faktoren}}.\,

Dann gilt:

B_{n,k}(x_1,\dots,x_{n-k+1}) = {x_{n}^{k\diamondsuit} \over k!}.\,

Die Faltungsidentität kann benutzt werden um einzelne Bell-Polynome zu berechnen. Die Berechnung von  B_{4,3}(x_1,x_2) ergibt sich mit

 x = ( x_1 \ , \ x_2 \ , \ x_3 \ , \ x_4 \ , \dots )
 x \diamondsuit x = ( 0,\  2 x_1^2 \ ,\  6 x_1 x_2 \ , \  8 x_1 x_3 + 6 x_2^2 \ , \dots )
 x \diamondsuit x \diamondsuit x = (  0 \ ,\ 0 \  , \ 6 x_1^3 \ , \ 36 x_1^2 x_2 \ , \dots )

und dementsprechend,

 B_{4,3}(x_1,x_2) = \frac{ ( x \diamondsuit x \diamondsuit x)_4 }{3!} = 6 x_1^2 x_2.

Anwendungen[Bearbeiten]

Formel von Faà di Bruno[Bearbeiten]

Hauptartikel: Formel von Faà di Bruno

Die Formel von Faà di Bruno kann mithilfe der Bell-Polynome wie folgt ausdrückt werden:

{d^n \over dx^n} f(g(x)) = \sum_{k=0}^n f^{(k)}(g(x)) B_{n,k}\left(g'(x),g''(x),\dots,g^{(n-k+1)}(x)\right).

Auf ähnliche Art und Weise lässt sich eine Potenzreihen-Version der Formel von Faà di Bruno aufstellen. Angenommen

f(x)=\sum_{n=1}^\infty {a_n \over n!} x^n \qquad
\mathrm{und} \qquad g(x)=\sum_{n=1}^\infty {b_n \over n!} x^n.

Dann

g(f(x)) = \sum_{n=1}^\infty
{\sum_{k=1}^{n} b_k B_{n,k}(a_1,\dots,a_{n-k+1}) \over n!} x^n.

Die vollständigen Bell-Polynome tauchen in der Exponentialfunktion einer formalen Potenzreihe auf:

\exp\left(\sum_{n=1}^\infty {a_n \over n!} x^n \right)
= \sum_{n=0}^\infty {B_n(a_1,\dots,a_n) \over n!} x^n.

Momente und Kumulanten[Bearbeiten]

Die Summe

B_n(\kappa_1,\dots,\kappa_n)=\sum_{k=1}^n B_{n,k}(\kappa_1,\dots,\kappa_{n-k+1})

ist das nte Moment einer Wahrscheinlichkeitsverteilung, deren erste n Kumulanten κ1, ..., κn sind. Anders ausgedrückt ist das nte Moment das nte vollständige Bell-Polynom ausgewertet an den n ersten Kumulanten.

Darstellung von Polynomfolgen mit binomialer Eigenschaft[Bearbeiten]

Für eine beliebige (skalare) Folge a1, a2, a3, ... sei

p_n(x)=\sum_{k=1}^n B_{n,k}(a_1,\dots,a_{n-k+1}) x^k.

Diese Polynomfolge erfüllt die binomiale Eigenschaft, d.h.

p_n(x+y)=\sum_{k=0}^n {n \choose k} p_k(x) p_{n-k}(y)

für n ≥ 0. Es gilt, dass alle Polynomfolgen welche die binomiale Eigenschaft erfüllen von dieser Form sind.

Falls die Potenzreihe

h(x)=\sum_{n=1}^\infty {a_n \over n!} x^n

als rein formell angenommen gilt, so ergibt sich für alle n

h^{-1}\left( {d \over dx}\right) p_n(x) = n p_{n-1}(x).

Literatur[Bearbeiten]