Bell-Polynom

Im mathematischen Teilgebiet d​er Kombinatorik bezeichnen d​ie Bell-Polynome, benannt n​ach Eric Temple Bell, folgende dreieckige Anordnung v​on Polynomen

${\displaystyle B_{n,k}(x_{1},x_{2},\dots ,x_{n-k+1})=\sum {\frac {n!}{j_{1}!j_{2}!\cdots j_{n-k+1}!}}\left({\frac {x_{1}}{1!}}\right)^{j_{1}}\left({\frac {x_{2}}{2!}}\right)^{j_{2}}\cdots \left({\frac {x_{n-k+1}}{(n-k+1)!}}\right)^{j_{n-k+1}}}$ ,

wobei die Summe über alle Sequenzen ${\displaystyle j_{1},j_{2},\dots ,j_{n-k+1}}$ von nicht-negativen ganzen Zahlen ${\displaystyle j_{i}}$ gebildet wird, so dass

${\displaystyle j_{1}+j_{2}+j_{3}+\cdots =k}$       und       ${\displaystyle 1\,j_{1}\;+\;2\,j_{2}\;+\;3\,j_{3}\;+\cdots =n}$ .

Das Bell-Polynom ${\displaystyle B_{n,k}(x_{1},x_{2},\dots ,x_{n-k+1})}$ ist ein Polynom in den Variablen ${\displaystyle x_{1},x_{2},\dots ,x_{n-k+1}}$. Seine Koeffizienten sind ganze Zahlen.

Vollständige Bell-Polynome

Die Summe

${\displaystyle 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 ${\displaystyle n}$tes vollständiges Bell-Polynom bezeichnet. Zur besseren Abgrenzung gegenüber den vollständigen Bell-Polynomen, werden die oben definierten Polynome ${\displaystyle B_{n,k}}$ auch manchmal als unvollständige oder partielle Bell-Polynome bezeichnet.

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

${\displaystyle B_{n}(x_{1},\dots ,x_{n})=\det {\begin{bmatrix}x_{1}&{\binom {n-1}{1}}x_{2}&{\binom {n-1}{2}}x_{3}&{\binom {n-1}{3}}x_{4}&{\binom {n-1}{4}}x_{5}&\cdots &\;\;x_{n}\\\\-1&x_{1}&{\binom {n-2}{1}}x_{2}&{\binom {n-2}{2}}x_{3}&{\binom {n-2}{3}}x_{4}&\cdots &\;\;x_{n-1}\\\\0&-1&x_{1}&{\binom {n-3}{1}}x_{2}&{\binom {n-3}{2}}x_{3}&\cdots &\;\;x_{n-2}\\\\0&0&-1&x_{1}&{\binom {n-4}{1}}x_{2}&\cdots &\;\;x_{n-3}\\\\0&0&0&-1&x_{1}&\cdots &\;\;x_{n-4}\\\\\vdots &\vdots &\vdots &\vdots &\ddots &\ddots &\;\;\vdots \\\\0&0&0&0&\cdots &-1&\;\;x_{1}\end{bmatrix}}}$

Rekursive Darstellungen

Eine rekursive Definition d​er Bell-Polynome ist:

${\displaystyle B_{0,0}()}$	${\displaystyle =1}$ ,
${\displaystyle B_{n,0}(x_{1},\dots ,x_{n+1})}$	${\displaystyle =0}$	für	${\displaystyle n\geq 1}$ ,
${\displaystyle B_{n,k}(x_{1},\dots ,x_{n-k+1})}$	${\displaystyle =0}$	für	${\displaystyle n\geq 0,k>n}$

und

${\displaystyle B_{n,k}(x_{1},\dots ,x_{n-k+1})}$

${\displaystyle =\sum _{i=1}^{n-k+1}{\binom {n-1}{i-1}}B_{n-i,k-1}(x_{1},\dots ,x_{n-i-k+2})\,x_{i}}$

für

${\displaystyle n\geq 1,k\leq n}$ .

Die vollständigen Bell-Polynome können folgendermaßen rekursiv definiert werden

${\displaystyle B_{0}(x_{1},\ldots ,x_{n+1})=1}$

und

${\displaystyle B_{n+1}(x_{1},\ldots ,x_{n+1})=\sum _{i=0}^{n}{\binom {n}{i}}B_{n-i}(x_{1},\ldots ,x_{n-i})\,x_{i+1}}$

für ${\displaystyle n\geq 0}$ .

Sie erfüllen auch die folgende rekursive Differentialformel: [1]

${\displaystyle {\begin{aligned}B_{n}(x_{1},\ldots ,x_{n})={\frac {1}{n-1}}\left[\sum _{i=2}^{n}\right.&\sum _{j=1}^{i-1}(i-1){\binom {i-2}{j-1}}x_{j}x_{i-j}{\frac {\partial B_{n-1}(x_{1},\dots ,x_{n-1})}{\partial x_{i-1}}}\\[5pt]&\left.{}+\sum _{i=2}^{n}\sum _{j=1}^{i-1}{\frac {x_{i+1}}{\binom {i}{j}}}{\frac {\partial ^{2}B_{n-1}(x_{1},\dots ,x_{n-1})}{\partial x_{j}\partial x_{i-j}}}\right.\\[5pt]&\left.{}+\sum _{i=2}^{n}x_{i}{\frac {\partial B_{n-1}(x_{1},\dots ,x_{n-1})}{\partial x_{i-1}}}\right].\end{aligned}}}$

Kombinatorische Bedeutung

Gegeben sei eine nicht-negative ganze Zahl ${\displaystyle n\in \mathbb {N} _{0}}$ als Elementeanzahl der zu partitionierenden Menge.

Wird die ganze Zahl (= eine Menge der Größe) ${\displaystyle n}$ in eine Summe von ${\displaystyle k}$ Summanden (= Partitionen) zerlegt, in der der Summand (= die Partitionsgröße) 1 ${\displaystyle j_{1}}$ mal, die 2 ${\displaystyle j_{2}}$ mal und der Summand ${\displaystyle i}$ ${\displaystyle j_{i}}$ mal vorkommt, dann entspricht die Anzahl der möglichen Partitionierungen, die mit einer ${\displaystyle n}$-elementigen Menge gebildet werden können, dem den ${\displaystyle k}$ Partitionsgrößen ${\displaystyle (1,2,\dots ,k)}$ zuzuordnenden Koeffizienten des Monoms ${\displaystyle x_{1}^{j_{1}}\cdots x_{k}^{j_{k}}}$ im Bell-Polynom. ${\displaystyle B_{n,k}}$ ist dann das Polynom aus allen Monomen mit dem Totalgrad ${\displaystyle k=j_{1}+j_{2}+j_{3}+\cdots =k}$ und der Mengengröße ${\displaystyle n=1\,j_{1}\;+\;2\,j_{2}\;+\;3\,j_{3}\;+\cdots }$.

Die Namen (eigentlich: die Nummern) der Unbestimmten		${\displaystyle x_{1},}$	${\displaystyle x_{2},}$	${\displaystyle \dots ,}$	${\displaystyle x_{n-k+1}}$
fungieren dabei nur als Pfosten zum Anheften der Anzahl		${\displaystyle j_{1},}$	${\displaystyle j_{2},}$	${\displaystyle \dots ,}$	${\displaystyle j_{n-k+1}}$
der Partitionen in der Partitionierung, die genau	Summand ${\displaystyle \in \{}$	${\displaystyle 1,}$	${\displaystyle 2,}$	${\displaystyle \dots ,}$	${\displaystyle n\!-\!k\!+\!1}$	${\displaystyle \}}$	Elemente haben sollen,
als Exponent der Potenz ${\displaystyle x_{i}^{j_{i}}}$.

Ein Exponent 1 wird normalerweise nicht notiert. Ist der Exponent 0, dann wird die ganze Potenz ${\displaystyle x_{i}^{0}}$ unterdrückt. Die größte Partitionsgröße bei ${\displaystyle k}$ Partitionen ist ${\displaystyle n\!-\!k\!+\!1}$, welche Partitionsgröße dann genau ${\displaystyle j_{n-k+1}=1}$ mal vorkommt. Die kleinste Partitionsgröße (= 1) kommt dann in dieser Partitionierung genau ${\displaystyle j_{1}=k-1}$ mal vor.

Die bevorzugte Reihenfolge der Monome im Bell-Polynom ist die lexikographisch aufsteigende mit niedrigstem Rang für ${\displaystyle x_{1}}$, also ${\displaystyle x_{1}^{\,2}x_{2}=x_{1}x_{1}x_{2}}$ kommt vor ${\displaystyle x_{1}x_{2}}$ kommt vor ${\displaystyle x_{2}}$.

Beispiele

• ${\displaystyle B_{n,1}(x_{1},\dots ,x_{n})=x_{n}}$ für ${\displaystyle n\geq 1}$ .
• ${\displaystyle B_{n,k}(x_{1},\dots ,x_{n-k+1})=0}$ für ${\displaystyle k>n}$ .
• ${\displaystyle B_{n,n}(x_{1},\dots ,x_{n-k+1})=x_{1}^{n}}$ für ${\displaystyle n\geq 1,k\leq n}$ .
• Ferner ist

${\displaystyle B_{6,2}(x_{1},x_{2},x_{3},x_{4},x_{5})=6x_{1}x_{5}+15x_{2}x_{4}+10x_{3}^{2}}$ ,

da es

(Monom ${\displaystyle 6\,x_{1}x_{5}\longrightarrow }$) 6 Möglichkeiten gibt, eine Menge mit ${\displaystyle n=6}$ Elementen zu ${\displaystyle k=2}$ Partitionen mit 1 und 5 Elementen zu partitionieren,

(Monom ${\displaystyle 15\,x_{2}x_{4}\longrightarrow }$) 15 Möglichkeiten gibt, eine Menge mit ${\displaystyle n=6}$ Elementen zu ${\displaystyle k=2}$ Partitionen mit 2 und 4 Elementen zu partitionieren, und es

(Monom ${\displaystyle 10\,x_{3}^{2}\longrightarrow }$) 10 Möglichkeiten gibt, eine Menge mit ${\displaystyle n=6}$ Elementen zu ${\displaystyle k=2}$ Partitionen mit 3 und 3 Elementen zu partitionieren.

• Ein weiteres Beispiel ist

${\displaystyle B_{6,3}(x_{1},x_{2},x_{3},x_{4})=15x_{1}^{2}x_{4}+60x_{1}x_{2}x_{3}+15x_{2}^{3}}$

da es

(Monom ${\displaystyle 15\,x_{1}^{2}x_{4}\longrightarrow }$) 15 Möglichkeiten gibt, eine Menge mit ${\displaystyle n=6}$ Elementen zu ${\displaystyle k=3}$ Partitionen mit jeweils 1, 1 und 4 Elementen zu partitionieren,

(Monom ${\displaystyle 60\,x_{1}x_{2}x_{3}\longrightarrow }$) 60 Möglichkeiten gibt, eine Menge mit ${\displaystyle n=6}$ Elementen zu ${\displaystyle k=3}$ Partitionen mit jeweils 1, 2 und 3 Elementen zu partitionieren, und es

(Monom ${\displaystyle 15\,x_{2}^{3}\longrightarrow }$) 15 Möglichkeiten gibt, eine Menge mit ${\displaystyle n=6}$ Elementen zu ${\displaystyle k=3}$ Partitionen mit jeweils 2, 2 und 2 Elementen zu partitionieren.

Eigenschaften

• ${\displaystyle 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 ${\displaystyle B_{n,k}(x_{1},x_{2},\dots )}$, wenn alle ${\displaystyle x_{i}}$ gleich 1 sind, ist eine Stirling-Zahl zweiter Art

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

Die Summe

${\displaystyle \sum _{k=1}^{n}B_{n,k}(1,1,1,\dots )=\sum _{k=1}^{n}\left\{{n \atop k}\right\}}$

entspricht der ${\displaystyle n}$ten Bellzahl, welche die Anzahl der möglichen Partitionen einer Menge mit ${\displaystyle n}$ Elementen beschreibt.

Faltungsidentität

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

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

wobei die Grenzen der Summe ${\displaystyle 1}$ und ${\displaystyle n-1}$ anstelle von ${\displaystyle 0}$ und ${\displaystyle n}$ sind.

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

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

dann gilt:

${\displaystyle 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 ${\displaystyle B_{4,3}(x_{1},x_{2})}$ ergibt sich mit

${\displaystyle x=(x_{1}\ ,\ x_{2}\ ,\ x_{3}\ ,\ x_{4}\ ,\dots )}$

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

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

und dementsprechend,

${\displaystyle 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 v​on Faà d​i Bruno k​ann mithilfe d​er Bell-Polynome w​ie folgt ausdrückt werden:

${\displaystyle {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 u​nd Weise lässt s​ich eine Potenzreihen-Version d​er Formel v​on Faà d​i Bruno aufstellen. Angenommen

${\displaystyle 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

${\displaystyle 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 i​n der Exponentialfunktion e​iner formalen Potenzreihe auf:

${\displaystyle \exp \left(\sum _{n=1}^{\infty }{\frac {a_{n}}{n!}}x^{n}\right)=\sum _{n=0}^{\infty }{\frac {B_{n}(a_{1},\dots ,a_{n})}{n!}}x^{n}}$ .

Momente und Kumulanten

Die Summe

${\displaystyle B_{n}(\kappa _{1},\dots ,\kappa _{n})=\sum _{k=1}^{n}B_{n,k}(\kappa _{1},\dots ,\kappa _{n-k+1})}$

ist das ${\displaystyle n}$te Moment einer Wahrscheinlichkeitsverteilung, deren erste ${\displaystyle n}$ Kumulanten ${\displaystyle \kappa _{1},\dots ,\kappa _{n}}$ sind. Anders ausgedrückt ist das ${\displaystyle n}$te Moment das ${\displaystyle n}$te vollständige Bell-Polynom ausgewertet an den ${\displaystyle n}$ ersten Kumulanten.

Darstellung von Polynomfolgen mit binomialer Eigenschaft

Für eine beliebige (skalare) Folge :${\displaystyle a_{1},a_{2},a_{3},\dots }$ sei

${\displaystyle p_{n}(x)=\sum _{k=1}^{n}B_{n,k}(a_{1},\dots ,a_{n-k+1})x^{k}}$ .

Diese Polynomfolge erfüllt d​ie binomiale Eigenschaft, d. h.

${\displaystyle p_{n}(x+y)=\sum _{k=0}^{n}{n \choose k}p_{k}(x)p_{n-k}(y)}$

für ${\displaystyle n\geq 0}$. Es gilt, dass alle Polynomfolgen, welche die binomiale Eigenschaft erfüllen, von dieser Form sind.

Für die Inverse ${\displaystyle h^{-1}}$ der Komposition der formalen Potenzreihe

${\displaystyle h(x)=\sum _{n=1}^{\infty }{a_{n} \over n!}x^{n}}$

ergibt sich für alle ${\displaystyle n}$

${\displaystyle h^{-1}{\bigl (}p_{n}^{\prime }(x){\bigr )}=np_{n-1}(x)}$

mit den obigen Polynomen ${\displaystyle p_{n}(x)}$ mit Koeffizienten in ${\displaystyle a_{1},\dots ,a_{n-k+1}}$ .

Literatur

• Eric Temple Bell: Partition Polynomials. In: Annals of Mathematics. Band 29, Nr. 1/4, 1927, S. 38–46, doi:10.2307/1967979, JSTOR:1967979.
• Louis Comtet: Advanced Combinatorics: The Art of Finite and Infinite Expansions. Reidel Publishing Company, Dordrecht, Holland / Boston, U.S. 1974.
• Steven Roman: The Umbral Calculus. Academic Press, 1984, ISBN 0-08-087430-4 (123library.org).
• Vassily G. Voinov, Mikhail S. Nikulin: On power series, Bell polynomials, Hardy-Ramanujan-Rademacher problem and its statistical applications. In: Kybernetika. Band 30, Nr. 3, 1994, ISSN 0023-5954, S. 343–358 (kybernetika.cz [PDF]).
• George Andrews: The Theory of Partitions (= Cambridge Mathematical Library). 1. 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. Band 5, 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. Band 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, doi:10.1155/2009/168672.
• Martin Griffiths: Families of sequences from a class of multinomial sums. In: Journal of Integer Sequences. Band 15, 2012 (cs.uwaterloo.ca).

Einzelnachweise

1. Nikita Alexeev, Anna Pologova, Max A. Alekseyev: Generalized Hultman Numbers and Cycle Structures of Breakpoint Graphs. In: Journal of Computational Biology. 24, Nr. 2, 2017, S. 93–105. arxiv:1503.05285. doi:10.1089/cmb.2016.0190., sect. 4.2