Bellsche Zahl

Die Bellsche Zahl, Bellzahl oder Exponentialzahl B_n ist die Anzahl der Partitionen einer n-elementigen Menge. Benannt ist sie nach dem Mathematiker Eric Temple Bell. Die Folge B₀, B₁, B₂, B₃, … beginnt mit

1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, … (Folge A000110 in OEIS)

Eigenschaften

Für die Bellschen Zahlen gelten die Rekursionsformel

$B_{n+1} = \sum_{k=0}^{n}{{n \choose k}B_k}$

und die Formel (Dobiński 1877)^[1]

$B_n = \frac{1}{e} \sum_{k=0}^\infty \frac{k^n}{k!}\,,$

somit ist B_n auch das n-te Moment einer Poisson-Verteilung mit Erwartungswert 1.

Die erzeugende Funktion der Bellzahlen ist

$\sum_{n=0}^\infty B_n\,x^n = \frac{1}{e} \sum_{k=0}^\infty \frac{1}{k!\,(1 - k x)}\,,$

die exponentiell erzeugende Funktion ist

$\sum_{n=0}^\infty \frac{B_n}{n!}\,x^n = e^{e^x-1}\,.$

Außerdem genügen die Bellzahlen der Kongruenz (Touchard 1933)^[2]

$B_{p^k + n} \equiv k\,B_n + B_{n+1} \ (\text{mod }p)$

für natürliche Zahlen k und Primzahlen p, insbesondere $B_{p^k} \equiv k + 1 \ (\text{mod }p)$ und $B_p \equiv 2 \ (\text{mod }p)$ und, nach Iteration,^[3]

$B_{1 + p + \ldots + p^{p-1} + n} \equiv B_n \ (\text{mod }p).$

Es wird vermutet, dass 1 + p + ... + p^{p − 1} die kleinste Periode von $B_n \ (\text{mod }p)$ ist.^[4][5] Für Primzahlen p > 2 ist

$B_{p^{k+1} n} \equiv B_{p^k n + 1} \ (\text{mod }p^{k+1}),$

für p = 2 gilt die Kongruenz (mod p^k).^[6]

Da die Stirling-Zahl S(n,k) zweiter Art die Anzahl der k-Partitionen einer n-elementigen Menge ist, gilt

$B_n = \sum_{k=0}^n S(n,k).$

Asymptotik

Für die Bellzahlen sind verschiedene asymptotische Formeln bekannt, etwa

$B_n \sim n^{-1/2}\ \bigl(\lambda(n)\bigr)^{n + 1/2}\ e^{\lambda(n) - n - 1}$     mit     $\lambda(n) = e^{W(n)} = \frac{n}{W(n)}$

mit der Lambert-W-Funktion W.

Einzelnachweise

1. ↑ G. Dobiński: Summirung der Reihe $\scriptstyle\sum\frac{n^m}{n!}$ für m = 1, 2, 3, 4, 5, …, Grunert-Archiv 61, 1877, S. 333–336
2. ↑ Jacques Touchard: Propriétés arithmétiques de certains nombres récurrents, Annales de la Société scientifique de Bruxelles A 53, 1933, S. 21–31 (französisch)
3. ↑ Marshall Hall: Arithmetic properties of a partition function, Bulletin of the AMS 40, 1934, S. 387 (englisch; nur Abstract)
4. ↑ Christian Radoux: Nombres de Bell, modulo p premier, et extensions de degré p de F_p, Comptes rendus hebdomadaires des séances de l’académie des sciences 281 A, 1975, S. 879–882 (französisch)
5. ↑ Peter L. Montgomery, Sangil Nahm, Samuel S. Wagstaff: The period of the Bell numbers modulo a prime (PDF-Datei, 168 kB), Mathematics of computation 79, 2010, S. 1793–1800 (englisch)
6. ↑ Anne Gertsch, Alain M. Robert: Some congruences concerning the Bell numbers, Bulletin of the Belgian Mathematical Society – Simon Stevin 3, 1996, S. 467–475 (englisch)

Literatur

• Eric Temple Bell: Exponential Numbers, The American Mathematical Monthly 41, 1934, S. 411–419
• Jacques Touchard: Nombres exponentiels et nombres de Bernoulli, Canadian Journal of Mathematics 8, 1956, S. 305–320 (französisch)

Weblinks

• Eric W. Weisstein, Bell Number und Dobiński’s Formula. Auf MathWorld. (englisch)
• Bell numbers bei The Wolfram Functions Site (englisch; mit Berechnungsmöglichkeit)
• Set Partitions: Bell Numbers in der NIST Digital Library of Mathematical Functions (englisch)
• Peter Luschny, Set partitions and Bell numbers (englisch). Eine Zusammenfassung von OEIS-Folgen zu den Bellzahlen im OEIS Wiki.