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}! \dots j_{n - k + 1}!} {(\frac{x_{1}}{1!})}^{j_{1}} {(\frac{x_{2}}{2!})}^{j_{2}} \dots {(\frac{x_{n - k + 1}}{(n - k + 1)!})}^{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} + \dots = k

und

1 j_{1} + 2 j_{2} + 3 j_{3} + \dots = 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{matrix} 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} & \dots & x_{n} \\ - 1 & x_{1} & (\binom{n - 2}{1}) x_{2} & (\binom{n - 2}{2}) x_{3} & (\binom{n - 2}{3}) x_{4} & \dots & x_{n - 1} \\ 0 & - 1 & x_{1} & (\binom{n - 3}{1}) x_{2} & (\binom{n - 3}{2}) x_{3} & \dots & x_{n - 2} \\ 0 & 0 & - 1 & x_{1} & (\binom{n - 4}{1}) x_{2} & \dots & x_{n - 3} \\ 0 & 0 & 0 & - 1 & x_{1} & \dots & x_{n - 4} \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋱ & ⋱ & ⋮ \\ 0 & 0 & 0 & 0 & \dots & - 1 & x_{1} \end{matrix}]

Beispiele

Die ersten vollständigen Bell-Polynome lauten:

\begin{matrix} 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} + 3 x_{1} x_{2} + x_{3}, \\ 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}, \\ 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} \\ 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}, \\ 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{matrix}

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}, \dots, x_{n + 1}) = 1

und

B_{n + 1} (x_{1}, \dots, x_{n + 1}) = \sum_{i = 0}^{n} (\binom{n}{i}) B_{n - i} (x_{1}, \dots, x_{n - i}) x_{i + 1}

für

n \geq 0

.

Sie erfüllen auch die folgende rekursive Differentialformel:

\begin{matrix} B_{n} (x_{1}, \dots, x_{n}) = \frac{1}{n - 1} [\sum_{i = 2}^{n} & \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}} \\ + \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}} \\ + \sum_{i = 2}^{n} x_{i} \frac{\partial B_{n - 1} (x_{1}, \dots, x_{n - 1})}{\partial x_{i - 1}}] . \end{matrix}

Kombinatorische Bedeutung

Gegeben sei eine nicht-negative ganze Zahl $n \in ℕ_{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}} \dots 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} + \dots = k$ und der Mengengröße $n = 1 j_{1} + 2 j_{2} + 3 j_{3} + \dots$ .

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 \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}) = 6 x_{1} x_{5} + 15 x_{2} x_{4} + 10 x_{3}^{2}

,

da es

(Monom

6 x_{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

15 x_{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

10 x_{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}) = 15 x_{1}^{2} x_{4} + 60 x_{1} x_{2} x_{3} + 15 x_{2}^{3}

da es

(Monom

15 x_{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

60 x_{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

15 x_{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)!) = (\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) = {\binom{n}{k}}

.

Die Summe

\sum_{k = 1}^{n} B_{n, k} (1, 1, 1, \dots) = \sum_{k = 1}^{n} {\binom{n}{k}}

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 ⋄ 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 ⋄}$ der $n$ te Term der Folge

\underset{k F a k t o r e n}{\underset{⏟}{x ⋄ \dots ⋄ x}}

,

dann gilt:

B_{n, k} (x_{1}, \dots, x_{n - k + 1}) = \frac{x_{n}^{k ⋄}}{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 ⋄ x = (0, 2 x_{1}^{2}, 6 x_{1} x_{2}, 8 x_{1} x_{3} + 6 x_{2}^{2}, \dots)

x ⋄ x ⋄ x = (0, 0, 6 x_{1}^{3}, 36 x_{1}^{2} x_{2}, \dots)

und dementsprechend,

B_{4, 3} (x_{1}, x_{2}) = \frac{(x ⋄ x ⋄ x)_{4}}{3!} = 6 x_{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^{'} (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_{0}) = y_{0}$ und $x_{0}$ ist der Entwicklungspunkt von $f$ bzw. $y_{0}$ ist der Entwicklungspunkt von $g$ .

f (x) = \sum_{n = 1}^{\infty} \frac{a_{n}}{n!} (x - x_{0})^{n} u n d g (y) = \sum_{n = 1}^{\infty} \frac{b_{n}}{n!} (y - y_{0})^{n} .

Dann

g (f (x)) = \sum_{n = 1}^{\infty} \frac{\sum_{k = 1}^{n} b_{k} B_{n, k} (a_{1}, \dots, a_{n - k + 1})}{n!} (x - x_{0})^{n} .

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

\exp (\sum_{n = 1}^{\infty} \frac{a_{n}}{n!} x^{n}) = \sum_{n = 0}^{\infty} \frac{B_{n} (a_{1}, \dots, a_{n})}{n!} x^{n}

.

Momente und Kumulanten

Die Summe

B_{n} (κ_{1}, \dots, κ_{n}) = \sum_{k = 1}^{n} B_{n, k} (κ_{1}, \dots, κ_{n - k + 1})

ist das $n$ te Moment einer Wahrscheinlichkeitsverteilung, deren erste $n$ Kumulanten $κ_{1}, \dots, κ_{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} (\binom{n}{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} \frac{a_{n}}{n!} x^{n}

ergibt sich für alle $n$

h^{- 1} ({p_{n}}^{'} (x)) = n p_{n - 1} (x)

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

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 (englisch).
Louis Comtet: Advanced Combinatorics: The Art of Finite and Infinite Expansions. Reidel Publishing Company, Dordrecht, Holland / Boston, U.S. 1974 (englisch).
Steven Roman: The Umbral Calculus. Academic Press, 1984, ISBN 0-08-087430-4 (englisch, 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 (englisch, 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 (englisch).
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 (englisch).
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 (englisch).
Khristo N. Boyadzhiev: Exponential Polynomials, Stirling Numbers, and Evaluation of Some Gamma Integrals. In: Abstract and Applied Analysis. 2009, doi:10.1155/2009/168672 (englisch).
Martin Griffiths: Families of sequences from a class of multinomial sums. In: Journal of Integer Sequences. Band 15, 2012 (englisch, cs.uwaterloo.ca).

Einzelnachweise

↑ 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 (englisch). , sect. 4.2

[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 (englisch). , sect. 4.2