Bell-Polynom

Im mathematischen Teilgebiet der Kombinatorik bezeichnen die Bell-Polynome, benannt nach Eric Temple Bell, folgende dreieckige Anordnung von Polynomen

<math>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}} </math> , wobei die Summe über alle Sequenzen <math>j_1, j_2, \dots , j_{n-k+1}</math> von nicht-negativen ganzen Zahlen <math>j_i </math> gebildet wird, so dass

<math>j_1+j_2+j_3+\cdots = k </math>       und       <math> 1\,j_1\;+\;2\,j_2\;+\;3\,j_3\;+\cdots=n </math> .

Das Bell-Polynom <math>B_{n,k}(x_1,x_2,\dots,x_{n-k+1})</math> ist ein Polynom in den Variablen {{#if:trim|<math>x_1,x_2,\dots,x_{n-k+1}</math>.}} Seine Koeffizienten sind ganze Zahlen.

Vollständige Bell-Polynome

Die Summe

<math>B_n(x_1,\dots,x_n)=\sum_{k=1}^n B_{n,k}(x_1,x_2,\dots,x_{n-k+1})</math>

wird manchmal als <math>n</math>tes vollständiges Bell-Polynom bezeichnet. Zur besseren Abgrenzung gegenüber den vollständigen Bell-Polynomen, werden die oben definierten Polynome <math>B_{n,k}</math> auch manchmal als unvollständige oder partielle Bell-Polynome bezeichnet.

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

<math>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}</math>

Beispiele

Die ersten vollständigen Bell-Polynome lauten:

<math>

\begin{align} 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 + 6 x_1^2 x_2 + 4 x_1 x_3 + 3 x_2^2 + x_4, \\[8pt] B_5(x_1,x_2,x_3,x_4,x_5) = {} & x_1^5 + 10 x_1^3 x_2 + 15 x_1 x_2^2 + 10 x_1^2 x_3 + 10 x_2 x_3 + 5 x_1 x_4 + x_5 \\[8pt] B_6(x_1,x_2,x_3,x_4,x_5,x_6) = {} & x_1^6 + 15 x_1^4 x_2 + 20 x_1^3 x_3 + 45 x_1^2 x_2^2 + 15 x_2^3 + 60 x_1 x_2 x_3 \\ & {} + 15 x_1^2 x_4 + 10 x_3^2 + 15 x_2 x_4 + 6 x_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 + 21 x_1^5 x_2 + 35 x_1^4 x_3 + 105 x_1^3 x_2^2 + 35 x_1^3 x_4 \\ & {} + 210 x_1^2 x_2 x_3 + 105 x_1 x_2^3 + 21 x_1^2 x_5 + 105 x_1 x_2 x_4 \\ & {} + 70 x_1 x_3^2 + 105 x_2^2 x_3 + 7 x_1 x_6 + 21 x_2 x_5 + 35 x_3 x_4 + x_7. \end{align}</math>

Rekursive Darstellungen

Eine rekursive Definition der Bell-Polynome ist:

<math>B_{0,0}() </math>	<math>= 1 </math> ,
<math>B_{n,0}(x_1,\dots,x_{n+1}) </math>	<math>= 0 </math>	für	<math> n \geq 1 </math> ,
<math>B_{n,k}(x_1,\dots,x_{n-k+1}) </math>	<math>= 0 </math>	für	<math> n \geq 0, k > n </math>

und

<math>B_{n,k}(x_1,\dots,x_{n-k+1}) </math>

<math>= \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 </math>

für

<math> n \geq 1, k \leq n </math> .

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

<math>B_0 (x_1, \ldots, x_{n+1}) = 1</math>

und

<math> 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}</math>

für <math> n \geq 0 </math> .

Sie erfüllen auch die folgende rekursive Differentialformel: <ref>{{#invoke:Vorlage:Literatur|f}}{{#if:

       | {{#if: Vorlage:Cite book/ParamBool
               | Vorlage:Toter Link/archivebot
               | Vorlage:Webarchiv/archiv-bot
         }}
  }}{{#invoke:TemplatePar|check
   |all    = title=
   |opt    = vauthors= author= author1= authorlink= author-link= author-link1= author1-link= author2= author3= author4= author5= author6= author7= author8= author9= editor= last= first= last1= first1= last2= first2= last3= first3= last4= first4= last5= first5= last6= first6= last7= first7= last8= first8= last9= first9= last10= first10= last11= first11= last12= first12= last13= first13= last14= first14= last15= first15= others= script-title= trans-title= date= year= volume= issue= number= series= page= pages= at= issn= arxiv= bibcode= doi= pmid= pmc= jstor= oclc= id= url= url-status= format= access-date= archive-date= archive-url= archivebot= offline= location= publisher= language= quote= work= journal= newspaper= magazine= periodical=  name-list-style= url-access= doi-access= display-authors= via= s2cid= mr= type= citeseerx=  accessdate= archivedate= archiveurl= coauthors= month= day= last16= first16= last17= first17= last18= first18= last19= first19= last20= first20= last21= first21= last22= first22= last23= first23= last24= first24= last25= first25= last26= first26= last27= first27= last28= first28= last29= first29= last30= first30= last31= first31=
   |cat      = Wikipedia:Vorlagenfehler/Vorlage:Cite journal
   |errNS    = 0
   |template = Vorlage:Cite journal
   |format   = 
   |preview  = 1
  }}Vorlage:Cite book/URL{{#if:  | Vorlage:Cite book/Meldung }}{{#if:        | Vorlage:Cite book/Meldung }}{{#if: Journal of Computational Biology
     || Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
        | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
     | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
     | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
     | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
       | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
     | Vorlage:Cite book/Meldung
  }}Vorlage:Cite book/Meldung2{{#ifexpr: 0{{#ifeq:Alexeev|^^||+1}}{{#ifeq:^^|^^||+1}}{{#ifeq:^^|^^||+1}}{{#ifeq:^^|^^||+1}} > 1
    | Vorlage:Cite book/Meldung
  }}, sect. 4.2</ref>

<math>

\begin{align} 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{align} </math>

Kombinatorische Bedeutung

Gegeben sei eine nicht-negative ganze Zahl <math>n\in\N_0 </math> als Elementeanzahl der zu partitionierenden Menge.

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

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

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

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

Beispiele

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

<math>B_{6,2}(x_1,x_2,x_3,x_4,x_5)=6x_1x_5+15x_2x_4+10x_3^2</math> ,

da es

(Monom <math>6\,x_1x_5 \longrightarrow</math>) 6 Möglichkeiten gibt, eine Menge mit <math>n=6 </math> Elementen zu <math>k=2 </math> Partitionen mit 1 und 5 Elementen zu partitionieren,

(Monom <math>15\,x_2x_4\longrightarrow</math>) 15 Möglichkeiten gibt, eine Menge mit <math>n=6 </math> Elementen zu <math>k=2 </math> Partitionen mit 2 und 4 Elementen zu partitionieren, und es

(Monom <math>10\,x_3^2\longrightarrow</math>) 10 Möglichkeiten gibt, eine Menge mit <math>n=6 </math> Elementen zu <math>k=2 </math> Partitionen mit 3 und 3 Elementen zu partitionieren.

• Ein weiteres Beispiel ist

<math>B_{6,3}(x_1,x_2,x_3,x_4)=15 x_1^2x_4+60x_1x_2x_3+15x_2^3</math>

da es

(Monom <math>15\,x_1^2x_4\longrightarrow</math>) 15 Möglichkeiten gibt, eine Menge mit <math>n=6 </math> Elementen zu <math>k=3 </math> Partitionen mit jeweils 1, 1 und 4 Elementen zu partitionieren,

(Monom <math>60\,x_1x_2x_3\longrightarrow</math>) 60 Möglichkeiten gibt, eine Menge mit <math>n=6 </math> Elementen zu <math>k=3 </math> Partitionen mit jeweils 1, 2 und 3 Elementen zu partitionieren, und es

(Monom <math>15\,x_2^3\longrightarrow</math>) 15 Möglichkeiten gibt, eine Menge mit <math>n=6 </math> Elementen zu <math>k=3 </math> Partitionen mit jeweils 2, 2 und 2 Elementen zu partitionieren.

Eigenschaften

• <math>B_{n,k}(1!,2!,\dots,(n-k+1)!) = \binom{n}{k}\binom{n-1}{k-1} (n-k)!</math>

Bell-Polynome und Stirling-Zahlen

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

<math>B_{n,k}(1,1,\dots)=S(n,k)=\left\{{n\atop k}\right\} </math> .

Die Summe

<math>\sum_{k=1}^n B_{n,k}(1,1,1,\dots) = \sum_{k=1}^n \left\{{n\atop k}\right\}</math>

entspricht der <math>n</math>ten Bellzahl, welche die Anzahl der möglichen Partitionen einer Menge mit <math>n</math> Elementen beschreibt.

Faltungsidentität

Für Folgen <math>(x_n)_{n = 1,2,\dotsc}</math> und <math>(y_n)_{n = 1,2,\dotsc}</math> lässt sich eine Art Faltung definieren:

<math>(x \diamond y)_n = \sum_{j=1}^{n-1} \binom{n}{j} x_j y_{n-j} </math> ,

wobei die Grenzen der Summe <math>1</math> und <math>n-1</math> anstelle von <math>0</math> und <math>n</math> sind.

Sei <math>x_n^{k\diamond}</math> der <math>n</math>te Term der Folge

<math>\displaystyle\underbrace{x\diamond\cdots\diamond x}_{k\ \mathrm{Faktoren}}</math> ,

dann gilt:

<math>B_{n,k}(x_1,\dots,x_{n-k+1}) = {x_{n}^{k\diamond} \over k!} </math> .

Die Faltungsidentität kann benutzt werden um einzelne Bell-Polynome zu berechnen. Die Berechnung von <math> B_{4,3}(x_1,x_2) </math> ergibt sich mit

<math> x = ( x_1 \ , \ x_2 \ , \ x_3 \ , \ x_4 \ , \dots ) </math>

<math> x \diamond x = ( 0,\ 2 x_1^2 \ ,\ 6 x_1 x_2 \ , \ 8 x_1 x_3 + 6 x_2^2 \ , \dots ) </math>

<math> x \diamond x \diamond x = ( 0 \ ,\ 0 \ , \ 6 x_1^3 \ , \ 36 x_1^2 x_2 \ , \dots ) </math>

und dementsprechend,

<math> B_{4,3}(x_1,x_2) = \frac{ ( x \diamond x \diamond x)_4 }{3!} = 6 x_1^2 x_2. </math>

Anwendungen

Formel von Faà di Bruno

{{#if: Formel von Faà di Bruno|{{#ifexist:Formel von Faà di Bruno|

→ Haupt{{#if:|seite|artikel}}: [[Formel von Faà di Bruno{{#if: ||{{{titel1}}}}}]]{{#if: |{{#ifexist:{{{2}}}|{{#if: |{{#ifexist:{{{3}}}|, [[{{{2}}}{{#if: ||{{{titel2}}}}}]] und [[{{{3}}}{{#if: ||{{{titel3}}}}}]]| und [[{{{2}}}{{#if: ||{{{titel2}}}}}]]}}| und [[{{{2}}}{{#if: ||{{{titel2}}}}}]]}}|{{#if: |{{#ifexist:| und [[{{{3}}}{{#if: ||{{{titel3}}}}}]]|}}|}}|}}|}}

|{{#if: |{{#ifexist:{{{2}}}|

→ Haupt{{#if:|seite|artikel}}: [[{{{2}}}{{#if: ||{{{titel2}}}}}]]{{#if: |{{#ifexist:{{{3}}}| und [[{{{3}}}{{#if: ||{{{titel3}}}}}]]|}}|}}

|{{#if: |{{#ifexist:{{{3}}}|

→ Haupt{{#if:|seite|artikel}}: [[{{{3}}}{{#if: ||{{{titel3}}}}}]]

|}}|}}|}}|}}|}}|}}

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

<math>{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).</math>

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

<math>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.</math>

Dann

<math>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.</math>

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

<math>\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 </math> .

Momente und Kumulanten

Die Summe

<math>B_n(\kappa_1,\dots,\kappa_n)=\sum_{k=1}^n B_{n,k}(\kappa_1,\dots,\kappa_{n-k+1})</math>

ist das <math>n</math>te Moment einer Wahrscheinlichkeitsverteilung, deren erste <math>n</math> Kumulanten <math>\kappa_1,\dots,\kappa_n</math> sind. Anders ausgedrückt ist das <math>n</math>te Moment das <math>n</math>te vollständige Bell-Polynom ausgewertet an den <math>n</math> ersten Kumulanten.

Darstellung von Polynomfolgen mit binomialer Eigenschaft

Für eine beliebige (skalare) Folge :<math>a_1,a_2,a_3,\dots </math> sei

<math>p_n(x)=\sum_{k=1}^n B_{n,k}(a_1,\dots,a_{n-k+1}) x^k </math> .

Diese Polynomfolge erfüllt die binomiale Eigenschaft, d. h.

<math>p_n(x+y)=\sum_{k=0}^n {n \choose k} p_k(x) p_{n-k}(y)</math>

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

Für die Inverse <math>h^{-1} </math> der Komposition der formalen Potenzreihe

<math>h(x)=\sum_{n=1}^\infty {a_n \over n!} x^n</math>

ergibt sich für alle <math>n</math>

<math>h^{-1}\bigl( p_n^\prime(x) \bigr) = n p_{n-1}(x) </math>

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

Literatur

• {{#invoke:Vorlage:Literatur|f}}
• {{#invoke:Vorlage:Literatur|f}}
• {{#invoke:Vorlage:Literatur|f}}
• {{#invoke:Vorlage:Literatur|f}}
• {{#invoke:Vorlage:Literatur|f}}
• {{#invoke:Vorlage:Literatur|f}}
• {{#invoke:Vorlage:Literatur|f}}
• {{#invoke:Vorlage:Literatur|f}}
• {{#invoke:Vorlage:Literatur|f}}

Einzelnachweise

<references />