Bell-Polynom

Anordnung von Polynomen

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

,

wobei die Summe über alle Sequenzen von nicht-negativen ganzen Zahlen gebildet wird, so dass

      und       .

Das Bell-Polynom ist ein Polynom in den Variablen . Seine Koeffizienten sind ganze Zahlen.

Vollständige Bell-Polynome

Bearbeiten

Die Summe

 

wird manchmal als  tes vollständiges Bell-Polynom bezeichnet. Zur besseren Abgrenzung gegenüber den vollständigen Bell-Polynomen, werden die oben definierten Polynome   auch manchmal als unvollständige oder partielle Bell-Polynome bezeichnet.

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

 

Beispiele

Bearbeiten

Die ersten vollständigen Bell-Polynome lauten:

 

Rekursive Darstellungen

Bearbeiten

Eine rekursive Definition der Bell-Polynome ist:

    ,
    für   ,
    für  

und

    für   .

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

 

und

  für   .

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

 

Kombinatorische Bedeutung

Bearbeiten

Gegeben sei eine nicht-negative ganze Zahl   als Elementeanzahl der zu partitionierenden Menge.

Wird die ganze Zahl (= eine Menge der Größe)   in eine Summe von   Summanden (= Partitionen) zerlegt, in der der Summand (= die Partitionsgröße) 1   mal, die 2   mal und der Summand     mal vorkommt, dann entspricht die Anzahl der möglichen Partitionierungen, die mit einer  -elementigen Menge gebildet werden können, dem den   Partitionsgrößen   zuzuordnenden Koeffizienten des Monoms   im Bell-Polynom.   ist dann das Polynom aus allen Monomen mit dem Totalgrad   und der Mengengröße  .

Die Namen (eigentlich: die Nummern) der Unbestimmten        
fungieren dabei nur als Pfosten zum Anheften der Anzahl        
der Partitionen in der Partitionierung, die genau Summand               Elemente haben sollen,
als Exponent der Potenz  .

Ein Exponent 1 wird normalerweise nicht notiert. Ist der Exponent 0, dann wird die ganze Potenz   unterdrückt. Die größte Partitionsgröße bei   Partitionen ist  , welche Partitionsgröße dann genau   mal vorkommt. Die kleinste Partitionsgröße (= 1) kommt dann in dieser Partitionierung genau   mal vor.

Die bevorzugte Reihenfolge der Monome im Bell-Polynom ist die lexikographisch aufsteigende mit niedrigstem Rang für  , also   kommt vor   kommt vor  .

Beispiele
  •   für   .
  •   für   .
  •   für   .
  • Ferner ist
  ,
da es
(Monom  ) 6 Möglichkeiten gibt, eine Menge mit   Elementen zu   Partitionen mit 1 und 5 Elementen zu partitionieren,
(Monom  ) 15 Möglichkeiten gibt, eine Menge mit   Elementen zu   Partitionen mit 2 und 4 Elementen zu partitionieren, und es
(Monom  ) 10 Möglichkeiten gibt, eine Menge mit   Elementen zu   Partitionen mit 3 und 3 Elementen zu partitionieren.
  • Ein weiteres Beispiel ist
 
da es
(Monom  ) 15 Möglichkeiten gibt, eine Menge mit   Elementen zu   Partitionen mit jeweils 1, 1 und 4 Elementen zu partitionieren,
(Monom  ) 60 Möglichkeiten gibt, eine Menge mit   Elementen zu   Partitionen mit jeweils 1, 2 und 3 Elementen zu partitionieren, und es
(Monom  ) 15 Möglichkeiten gibt, eine Menge mit   Elementen zu   Partitionen mit jeweils 2, 2 und 2 Elementen zu partitionieren.

Eigenschaften

Bearbeiten
  •  

Bell-Polynome und Stirling-Zahlen

Bearbeiten

Der Wert des Bell-Polynoms  , wenn alle   gleich 1 sind, ist eine Stirling-Zahl zweiter Art

  .

Die Summe

 

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

Faltungsidentität

Bearbeiten

Für Folgen   und   lässt sich eine Art Faltung definieren:

  ,

wobei die Grenzen der Summe   und   anstelle von   und   sind.

Sei   der  te Term der Folge

  ,

dann gilt:

  .

Die Faltungsidentität kann benutzt werden um einzelne Bell-Polynome zu berechnen. Die Berechnung von   ergibt sich mit

 
 
 

und dementsprechend,

 

Anwendungen

Bearbeiten

Formel von Faà di Bruno

Bearbeiten

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

 

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

 

Dann

 

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

  .

Momente und Kumulanten

Bearbeiten

Die Summe

 

ist das  te Moment einer Wahrscheinlichkeitsverteilung, deren erste   Kumulanten   sind. Anders ausgedrückt ist das  te Moment das  te vollständige Bell-Polynom ausgewertet an den   ersten Kumulanten.

Darstellung von Polynomfolgen mit binomialer Eigenschaft

Bearbeiten

Für eine beliebige (skalare) Folge :  sei

  .

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

 

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

Für die Inverse   der Komposition der formalen Potenzreihe

 

ergibt sich für alle  

 

mit den obigen Polynomen   mit Koeffizienten in   .

Literatur

Bearbeiten
  • 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

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