Bell-Polynom

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

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

Rekursive Darstellungen

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

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 genauSummand   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

Bell-Polynome und Stirling-Zahlen

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

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

Formel von Faà di Bruno

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

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

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

  • 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