Bell-Polynom

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 j₁, j₂, j₃, ..., j_n−k+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

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 B_n, k 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

Wird die ganze Zahl n zu einer Summe zerlegt, in der die "1" j₁ mal vorkommt, die "2" j₂ 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

Es gilt beispielsweise

$B_{{6,2}}(x_{1},x_{2},x_{3},x_{4},x_{5})=6x_{5}x_{1}+15x_{4}x_{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_{4}x_{1}^{2}+60x_{3}x_{2}x_{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

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

Bell-Polynome und Stirling-Zahlen

Der Wert des Bell-Polynoms B_n,k(x₁,x₂,…), wenn alle x_i 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

Für Folgen $(x_{n})_{n=1,2,\dotsc }$ und $(y_{n})_{n=1,2,\dotsc }$ lässt sich eine Art Faltung definieren:

$(x\diamond y)_{n}=\sum _{j=1}^{n-1}{\binom {n}{j}}x_{j}y_{n-j},$

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

Sei $x_{n}^{k\diamond }$ der -te Term der Folge

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

Dann gilt:

$B_{n,k}(x_{1},\dots ,x_{n-k+1})={x_{n}^{k\diamond } \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\diamond x=(0,\ 2x_{1}^{2}\ ,\ 6x_{1}x_{2}\ ,\ 8x_{1}x_{3}+6x_{2}^{2}\ ,\dots )$

$x\diamond x\diamond x=(0\ ,\ 0\ ,\ 6x_{1}^{3}\ ,\ 36x_{1}^{2}x_{2}\ ,\dots )$

und dementsprechend,

$B_{4,3}(x_{1},x_{2})={\frac {(x\diamond x\diamond x)_{4}}{3!}}=6x_{1}^{2}x_{2}.$

Anwendungen

Formel von Faà di Bruno

→ 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

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 κ₁, ..., κ_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

Für eine beliebige (skalare) Folge a₁, a₂, a₃, ... 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)=np_{{n-1}}(x).$

Basierend auf einem Artikel in:

Wikipedia.de