Bell-Polynom

In 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.$

Komplette 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 komplettes Bell-Polynom bezeichnet. Zur besseren Abgrenzung gegenüber den kompletten Bell-Polynomen, werden die oben definierten Polynome B_n, k auch manchmal als "partielle" Bell-Polynome bezeichnet.

Die kompletten 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

Wir 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 ergebt, dem jeweiligen Koeffizienten des Bell-Polynoms.

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, y_n, 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 {Factoren} }.\,$

Dann gilt:

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

Die 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,\ 2x_{1}^{2}\ ,\ 6x_{1}x_{2}\ ,\ 8x_{1}x_{3}+6x_{2}^{2}\ ,\dots )$

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

und dementsprechend,

$B_{4,3}(x_{1},x_{2})={\frac {(x\diamondsuit x\diamondsuit 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 kompletten Bell-Polynome tauchen in der Exponentialfunktion einer formalen Potenzeihe 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 komplette 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).$

Literatur

• Eric Temple Bell: Partition Polynomials. In: Annals of Mathematics. 29. Jahrgang, Nr. 1/4, S. 38–46, doi:10.2307/1967979, JSTOR:1967979. 
• Louis Comtet: Advanced Combinatorics: The Art of Finite and Infinite Expansions. Reidel Publishing Company, 1974. 
• Steven Roman: The Umbral Calculus. Dover Publications. 
• Vassily G. Voinov, Mikhail S. Nikulin: On power series, Bell polynomials, Hardy-Ramanujan-Rademacher problem and its statistical applications. In: Kybernetika. 30. Jahrgang, Nr. 3, 1994, ISSN 0023-5954, S. 343–358. 
• George E. Andrews: The Theory of Partitions (= Cambridge Mathematical Library). 1st pbk Auflage. Cambridge University Press, 1998, ISBN 0-521-63766-X, S. 204–211. 
• Silvia Noschese, Paolo E. Ricci: Differentiation of Multivariable Composite Functions and Bell Polynomials. In: Journal of Computational Analysis and Applications. 5. Jahrgang, Nr. 3, 2003, S. 333–340, doi:10.1023/A:1023227705558. 
• Moncef Abbas, Sadek Bouroubi: On new identities for Bell's polynomial. In: Disc. Math. Nr. 293, 2005, S. 5–10, doi:10.1016/j.disc.2004.08.023. 
• Khristo N. Boyadzhiev: Exponential Polynomials, Stirling Numbers, and Evaluation of Some Gamma Integrals. In: Abstract and Applied Analysis. 2009. Jahrgang, 2009, S. Article ID 168672, doi:10.1155/2009/168672.  (contains also elementary review of the concept Bell-polynomials)
• Martin Griffiths: Families of sequences from a class of multinomial sums. In: Journal of Integer Sequences. 15. Jahrgang, 2012 (uwaterloo.ca).