Bell-Polynom
# 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   $1\,j_{1}\;+\;2\,j_{2}\;+\;3\,j_{3}\;+\cdots =n$ .

Das Bell-Polynom $B_{n,k}(x_{1},x_{2},\dots ,x_{n-k+1})$ ist ein Polynom in den Variablen $x_{1},x_{2},\dots ,x_{n-k+1}$. 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 {\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}}$

### Beispiele

Die ersten vollständigen Bell-Polynome lauten:

    ${\begin{aligned}B_{0}=&1,\\[8pt]B_{1}(x_{1})=&x_{1},\\[8pt]B_{2}(x_{1},x_{2})=&x_{1}^{2}+x_{2},\\[8pt]B_{3}(x_{1},x_{2},x_{3})=&x_{1}^{3}+3x_{1}x_{2}+x_{3},\\[8pt]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},\\[8pt]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}\\[8pt]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},\\[8pt]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{aligned}}$

## 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\geq 1$ , $B_{n,k}(x_{1},\dots ,x_{n-k+1})$$=0$für$n\geq 0,k>n$

und

    $B_{n,k}(x_{1},\dots ,x_{n-k+1})$$=\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$n\geq 1,k\leq n$ .

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

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

und

    $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 $n\geq 0$ .

Sie erfüllen auch die folgende rekursive Differentialformel:

    ${\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 $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 $n$-elementigen 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 $n=1\,j_{1}\;+\;2\,j_{2}\;+\;3\,j_{3}\;+\cdots$.

| Die Namen (eigentlich: die Nummern) der Unbestimmten | 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 | 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\geq 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\geq 1,k\leq 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 $6\,x_{1}x_{5}\longrightarrow$) 6 Möglichkeiten gibt, eine Menge mit $n=6$ Elementen zu $k=2$ Partitionen mit 1 und 5 Elementen zu partitionieren,
       (Monom $15\,x_{2}x_{4}\longrightarrow$) 15 Möglichkeiten gibt, eine Menge mit $n=6$ Elementen zu $k=2$ Partitionen mit 2 und 4 Elementen zu partitionieren, und es
       (Monom $10\,x_{3}^{2}\longrightarrow$) 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 $15\,x_{1}^{2}x_{4}\longrightarrow$) 15 Möglichkeiten gibt, eine Menge mit $n=6$ Elementen zu $k=3$ Partitionen mit jeweils 1, 1 und 4 Elementen zu partitionieren,
       (Monom $60\,x_{1}x_{2}x_{3}\longrightarrow$) 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 $15\,x_{2}^{3}\longrightarrow$) 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)!)={\binom {n}{k}}{\binom {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\{{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 $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,\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 $1$ und $n-1$ anstelle von $0$ und $n$ sind.

Sei $x_{n}^{k\diamond }$ der $n$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

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 }{\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

    $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}{n \choose k}p_{k}(x)p_{n-k}(y)$

für $n\geq 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}^{\infty }{a_{n} \over n!}x^{n}$

ergibt sich für alle $n$

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

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

