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 \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 $j_1,j_2,\dots ,j_{n-k+1}$ von nicht-negativen ganzen Zahlen $j_i$ gebildet wird, so dass

$j_1+j_2+j_3+\cdots =k$       und       $1j_1+2j_2+3j_3+\cdots =n$ .

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

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 $n$tes 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 oder partielle Bell-Polynome bezeichnet.

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

$B_n(x_1,\dots ,x_n)=\det \left[\begin{array}{ccccccc}{x}_1& (\genfrac{}{}{0ex}{}{n-1}{1})x_2& (\genfrac{}{}{0ex}{}{n-1}{2})x_3& (\genfrac{}{}{0ex}{}{n-1}{3})x_4& (\genfrac{}{}{0ex}{}{n-1}{4})x_5& \cdots & x_n\\ \\ -1& x_1& (\genfrac{}{}{0ex}{}{n-2}{1})x_2& (\genfrac{}{}{0ex}{}{n-2}{2})x_3& (\genfrac{}{}{0ex}{}{n-2}{3})x_4& \cdots & x_{n-1}\\ \\ 0& -1& x_1& (\genfrac{}{}{0ex}{}{n-3}{1})x_2& (\genfrac{}{}{0ex}{}{n-3}{2})x_3& \cdots & x_{n-2}\\ \\ 0& 0& -1& x_1& (\genfrac{}{}{0ex}{}{n-4}{1})x_2& \cdots & x_{n-3}\\ \\ 0& 0& 0& -1& x_1& \cdots & x_{n-4}\\ \\ ⋮& ⋮& ⋮& ⋮& \ddots & \ddots & ⋮\\ \\ 0& 0& 0& 0& \cdots & -1& x_1\end{array}\right]$

Beispiele

Die ersten vollständigen Bell-Polynome lauten:

$\begin{array}{cc}{B}_0=& 1,\\ B_1(x_1)=& x_1,\\ B_2(x_1,x_2)=& x_1^2+x_2,\\ B_3(x_1,x_2,x_3)=& x_1^3+3x_1{x}_2+x_3,\\ B_4(x_1,x_2,x_3,x_4)=& x_1^4+6x_1^2{x}_2+4x_1{x}_3+3x_2^2+x_4,\\ B_5(x_1,x_2,x_3,x_4,x_5)=& x_1^5+10x_1^3{x}_2+15x_1{x}_2^2+10x_1^2{x}_3+10x_2{x}_3+5x_1{x}_4+x_5\\ B_6(x_1,x_2,x_3,x_4,x_5,x_6)=& x_1^6+15x_1^4{x}_2+20x_1^3{x}_3+45x_1^2{x}_2^2+15x_2^3+60x_1{x}_2{x}_3\\ & +15x_1^2{x}_4+10x_3^2+15x_2{x}_4+6x_1{x}_5+x_6,\\ B_7(x_1,x_2,x_3,x_4,x_5,x_6,x_7)=& x_1^7+21x_1^5{x}_2+35x_1^4{x}_3+105x_1^3{x}_2^2+35x_1^3{x}_4\\ & +210x_1^2{x}_2{x}_3+105x_1{x}_2^3+21x_1^2{x}_5+105x_1{x}_2{x}_4\\ & +70x_1{x}_3^2+105x_2^2{x}_3+7x_1{x}_6+21x_2{x}_5+35x_3{x}_4+x_7.\end{array}$

Rekursive Darstellungen

Eine rekursive Definition der Bell-Polynome ist:

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

und

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

$=\sum _{i=1}^{n-k+1}(\genfrac{}{}{0ex}{}{n-1}{i-1})B_{n-i,k-1}(x_1,\dots ,x_{n-i-k+2})x_i$

für

$n\ge 1,k\le n$ .

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

$B_0(x_1,\dots ,x_{n+1})=1$

und

$B_{n+1}(x_1,\dots ,x_{n+1})=\sum _{i=0}^n(\genfrac{}{}{0ex}{}{n}{i})B_{n-i}(x_1,\dots ,x_{n-i})x_{i+1}$

für $n\ge 0$ .

Sie erfüllen auch die folgende rekursive Differentialformel:

$\begin{array}{cc}{B}_n(x_1,\dots ,x_n)=\frac{1}{n-1}[\sum _{i=2}^n& \sum _{j=1}^{i-1}(i-1)(\genfrac{}{}{0ex}{}{i-2}{j-1})x_j{x}_{i-j}\frac{\partial B_{n-1}(x_1,\dots ,x_{n-1})}{\partial x_{i-1}}\\ & +\sum _{i=2}^n\sum _{j=1}^{i-1}\frac{x_{i+1}}{(\genfrac{}{}{0ex}{}{i}{j})}\frac{{\partial }^2{B}_{n-1}(x_1,\dots ,x_{n-1})}{\partial x_j\partial x_{i-j}}\\ & +\sum _{i=2}^n{x}_i\frac{\partial B_{n-1}(x_1,\dots ,x_{n-1})}{\partial x_{i-1}}].\end{array}$

Kombinatorische Bedeutung

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

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

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

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

Die bevorzugte Reihenfolge der Monome im Bell-Polynom ist die lexikographisch aufsteigende mit niedrigstem Rang für $x_1$, also $x_1^2{x}_2=x_1{x}_1{x}_2$ kommt vor $x_1{x}_2$ kommt vor $x_2$.

Beispiele

• $B_{n,1}(x_1,\dots ,x_n)=x_n$ für $n\ge 1$ .
• $B_{n,k}(x_1,\dots ,x_{n-k+1})=0$ für $k>n$ .
• $B_{n,n}(x_1,\dots ,x_{n-k+1})=x_1^n$ für $n\ge 1,k\le n$ .
• Ferner ist

$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 $6x_1{x}_5⟶$) 6 Möglichkeiten gibt, eine Menge mit $n=6$ Elementen zu $k=2$ Partitionen mit 1 und 5 Elementen zu partitionieren,

(Monom $15x_2{x}_4⟶$) 15 Möglichkeiten gibt, eine Menge mit $n=6$ Elementen zu $k=2$ Partitionen mit 2 und 4 Elementen zu partitionieren, und es

(Monom $10x_3^2⟶$) 10 Möglichkeiten gibt, eine Menge mit $n=6$ Elementen zu $k=2$ Partitionen mit 3 und 3 Elementen zu partitionieren.

• Ein weiteres Beispiel ist

$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 $15x_1^2{x}_4⟶$) 15 Möglichkeiten gibt, eine Menge mit $n=6$ Elementen zu $k=3$ Partitionen mit jeweils 1, 1 und 4 Elementen zu partitionieren,

(Monom $60x_1{x}_2{x}_3⟶$) 60 Möglichkeiten gibt, eine Menge mit $n=6$ Elementen zu $k=3$ Partitionen mit jeweils 1, 2 und 3 Elementen zu partitionieren, und es

(Monom $15x_2^3⟶$) 15 Möglichkeiten gibt, eine Menge mit $n=6$ Elementen zu $k=3$ Partitionen mit jeweils 2, 2 und 2 Elementen zu partitionieren.

Eigenschaften

• $B_{n,k}(1!,2!,\dots ,(n-k+1)!)=(\genfrac{}{}{0ex}{}{n}{k})(\genfrac{}{}{0ex}{}{n-1}{k-1})(n-k)!$

Bell-Polynome und Stirling-Zahlen

Der Wert des Bell-Polynoms $B_{n,k}(x_1,x_2,\dots )$, wenn alle $x_i$ gleich 1 sind, ist eine Stirling-Zahl zweiter Art

$B_{n,k}(1,1,\dots )=S(n,k)=\left\{\genfrac{}{}{0ex}{}{n}{k}\right\}$ .

Die Summe

$\sum _{k=1}^n{B}_{n,k}(1,1,1,\dots )=\sum _{k=1}^n\left\{\genfrac{}{}{0ex}{}{n}{k}\right\}$

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

Faltungsidentität

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

$(x\diamond y{)}_n=\sum _{j=1}^{n-1}(\genfrac{}{}{0ex}{}{n}{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\diamond }$ der $n$te Term der Folge

$\underset{k\mathrm{F}\mathrm{a}\mathrm{k}\mathrm{t}\mathrm{o}\mathrm{r}\mathrm{e}\mathrm{n}}{\underbrace{x\diamond \cdots \diamond x}}$ ,

dann gilt:

$B_{n,k}(x_1,\dots ,x_{n-k+1})=\frac{x_n^{k\diamond }}{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

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

$\frac{d^n}{d{x}^n}f(g(x))=\sum _{k=0}^n{f}^{(k)}(g(x))B_{n,k}(g^{\prime }(x),g^{″}(x),\dots ,g^{(n-k+1)}(x)).$

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

$f(x)=\sum _{n=1}^{\mathrm{\infty }}\frac{a_n}{n!}{x}^n\mathrm{u}\mathrm{n}\mathrm{d}g(x)=\sum _{n=1}^{\mathrm{\infty }}\frac{b_n}{n!}{x}^n.$

Dann

$g(f(x))=\sum _{n=1}^{\mathrm{\infty }}\frac{\sum _{k=1}^n{b}_k{B}_{n,k}(a_1,\dots ,a_{n-k+1})}{n!}{x}^n.$

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

$\exp \left(\sum _{n=1}^{\mathrm{\infty }}\frac{a_n}{n!}{x}^n\right)=\sum _{n=0}^{\mathrm{\infty }}\frac{B_n(a_1,\dots ,a_n)}{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 $n$te Moment einer Wahrscheinlichkeitsverteilung, deren erste $n$ Kumulanten ${\kappa }_1,\dots ,{\kappa }_n$ sind. Anders ausgedrückt ist das $n$te Moment das $n$te vollständige Bell-Polynom ausgewertet an den $n$ ersten Kumulanten.

Darstellung von Polynomfolgen mit binomialer Eigenschaft

Für eine beliebige (skalare) Folge :$a_1,a_2,a_3,\dots$ 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(\genfrac{}{}{0ex}{}{n}{k})p_k(x)p_{n-k}(y)$

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

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

$h(x)=\sum _{n=1}^{\mathrm{\infty }}\frac{a_n}{n!}{x}^n$

ergibt sich für alle $n$

$h^{-1}(p_n^{\prime }(x))=n{p}_{n-1}(x)$

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

Literatur

• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur