Bellsche Zahl

Die Bellsche Zahl, Bellzahl oder Exponentialzahl ${\displaystyle B_{n}}$ ist die Anzahl der Partitionen einer ${\displaystyle n}$-elementigen Menge. Benannt ist sie nach dem Mathematiker Eric Temple Bell. Die Folge ${\displaystyle B_{0},B_{1},B_{2},B_{3},\ldots }$ beginnt mit

${\displaystyle 1,1,2,5,15,52,203,877,4140,21147,115975,678570,\ldots }$ (Folge A000110 in OEIS)

Bedeutung

Partitionen

Eine Partition ${\displaystyle P}$ einer Menge ${\displaystyle M}$ ist eine Menge nichtleerer, paarweise disjunkter Teilmengen von ${\displaystyle M}$, sodass jedes Element aus ${\displaystyle M}$ in genau einer Menge aus ${\displaystyle P}$ vorkommt. Für alle natürlichen Zahlen einschließlich der Null ${\displaystyle n\in \mathbb {N} _{0}}$ bezeichnet nun die Bellsche Zahl ${\displaystyle B_{n}}$ die Anzahl ${\displaystyle \left|Q\right|}$ der möglichen verschiedenen Partitionen einer Menge mit der Mächtigkeit ${\displaystyle n}$, wobei ${\displaystyle Q}$ die Menge aller möglichen Partitionen darstellt. Formal:

${\displaystyle \left|M\right|=n}$

${\displaystyle \forall P\in Q:\bigcup _{a\in P}a=M}$

${\displaystyle \forall P\in Q:\forall a\in P:a\neq \emptyset }$

${\displaystyle \forall P\in Q:\forall a,b\in P:(a\neq b\Longrightarrow a\cap b=\emptyset )}$

${\displaystyle B_{n}:=\left|Q\right|}$

Die Bellsche Zahl mit dem Index 0, ${\displaystyle B_{0}}$, – also die Anzahl der Partitionen der leeren Menge ${\displaystyle \emptyset }$ – ist 1, weil die einzige Partition der leeren Menge wieder die leere Menge selbst ist, ${\displaystyle Q(\emptyset )=\{P_{1}\}=\{\emptyset \}}$. Dies ist so, weil alle Aussagen mit dem Allquantor über die Elemente der leeren Menge wahr sind (siehe leere Menge).

Multiplikative Partitionen

Sei ${\displaystyle N}$ eine quadratfreie Zahl, ${\displaystyle \omega :\mathbb {N} \rightarrow \mathbb {N} }$ die Funktion zur Bestimmung der Anzahl der einzigartigen Primfaktoren und ${\displaystyle n=\omega (N)}$.

Dann ist ${\displaystyle B_{n}}$ die Anzahl der unterschiedlichen multiplikativen Partitionen von ${\displaystyle N}$.

Sei zum Beispiel ${\displaystyle N=30}$, so ist ${\displaystyle n=\omega (30)=3}$ (da 30 aus den drei Primfaktoren 2, 3 und 5 besteht) und ${\displaystyle B_{3}=5}$ ist damit die Anzahl der multiplikativen Partitionen. Diese lauten:

${\displaystyle 30=2\times 15=3\times 10=5\times 6=2\times 3\times 5}$

Eigenschaften

Definition

Für die Bellschen Zahlen gilt diese Rekursionsformel:

${\displaystyle B_{n+1}=\sum _{k=0}^{n}{{n \choose k}B_{k}}}$

Die Dobińskische Formel (Dobiński 1877)^[1]

${\displaystyle B_{n}={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {k^{n}}{k!}}}$

erlaubt die explizite Definition der Bellschen Zahlen für alle n ≥ 0. Sie wurde nach dem polnischen Mathematiker Donald Gabriel Dobiński^[2] benannt.

Ihre Äquivalenz zur obigen Rekursionsformel lässt sich durch vollständige Induktion beweisen:

Sei

${\displaystyle f(n)={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {k^{n}}{k!}}}$ .

Dann gilt:

${\displaystyle f(0)={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {1}{k!}}=1}$

sowie für n ≥ 0:

${\displaystyle f(n+1)={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {k^{n+1}}{k!}}={\frac {1}{e}}\sum _{k=1}^{\infty }{\frac {k^{n+1}}{k!}}={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {(k+1)^{n+1}}{(k+1)!}}={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {(k+1)^{n}}{k!}}=}$

${\displaystyle ={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {1}{k!}}\sum _{m=0}^{n}{\binom {n}{m}}k^{m}=\sum _{m=0}^{n}{\binom {n}{m}}{\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {k^{m}}{k!}}=\sum _{m=0}^{n}{\binom {n}{m}}f(m)}$

Aus

${\displaystyle f(0)=1}$ und

${\displaystyle \forall n\in \mathbb {N} _{0}:f(n+1)=\sum _{m=0}^{n}{\binom {n}{m}}f(m)}$ folgt schließlich:

${\displaystyle \forall n\in \mathbb {N} _{0}:f(n)=B_{n}}$

Somit ist ${\displaystyle B_{n}}$ auch das ${\displaystyle n}$-te Moment einer Poisson-Verteilung mit Erwartungswert 1.

Erzeugende Funktionen

Die erzeugende Funktion der Bellzahlen ist wie folgt darstellbar:

${\displaystyle \sum _{n=0}^{\infty }B_{n}\,x^{n}={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {1}{k!\,(1-kx)}}}$

Die exponentiell erzeugende Funktion lautet:

${\displaystyle \sum _{n=0}^{\infty }{\frac {B_{n}}{n!}}\,x^{n}=e^{e^{x}-1}}$

Dies folgt aus der genannten Dobiński-Formel:

${\displaystyle \sum _{n=0}^{\infty }{\frac {B_{n}}{n!}}x^{n}=\sum _{n=0}^{\infty }{\frac {1}{n!}}{\biggl [}{\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {k^{n}}{k!}}{\biggr ]}x^{n}={\frac {1}{e}}\sum _{n=0}^{\infty }\sum _{k=0}^{\infty }{\frac {k^{n}}{k!n!}}x^{n}={\frac {1}{e}}\sum _{k=0}^{\infty }\sum _{n=0}^{\infty }{\frac {k^{n}}{k!n!}}x^{n}={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {1}{k!}}\sum _{n=0}^{\infty }{\frac {(kx)^{n}}{n!}}=}$

${\displaystyle ={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {1}{k!}}\exp(kx)={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {1}{k!}}\exp(x)^{k}={\frac {1}{e}}\exp[\exp(x)]=\exp[\exp(x)-1]}$

Kongruenzsätze

Die Bellschen Zahlen genügen der Kongruenz (Touchard 1933)^[3]

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

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

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

Es wird vermutet, dass ${\displaystyle 1+p+\dots +p^{p-1}}$ die kleinste Periode von ${\displaystyle B_{n}\ ({\text{mod }}p)}$ ist.^[5][6] Für Primzahlen ${\displaystyle p>2}$ ist

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

für ${\displaystyle p=2}$ gilt die Kongruenz ${\displaystyle ({\text{mod }}p^{k})}$.^[7]

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

${\displaystyle B_{n}=\sum _{k=0}^{n}S(n,k).}$

Asymptotik

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

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

mit der Lambert-W-Funktion ${\displaystyle W}$.

Bellsches Dreieck

Die Bellschen Zahlen lassen sich intuitiv durch das Bellsche Dreieck erzeugen, welches – wie das Pascalsche Dreieck – aus natürlichen Zahlen besteht und pro Zeile ein Element bzw. eine Spalte mehr besitzt. Das Bellsche Dreieck wird gelegentlich auch Aitkens array (nach Alexander Aitken) oder Peirce-Dreieck (nach Charles Sanders Peirce) genannt.

Es wird nach den folgenden Regeln konstruiert:

1. Die erste Zeile hat nur ein Element: Die Eins: ${\displaystyle \ x_{1,1}=1\ }$.
2. Jede folgende Zeile hat jeweils ein Element mehr als die vorherige Zeile, d. h. die ${\displaystyle n}$-te Zeile hat ${\displaystyle n}$ Elemente.
3. Das jeweils erste Element jeder Zeile hat den gleichen Wert wie das letzte Element der vorherigen Zeile: ${\displaystyle \ x_{k+1,1}=x_{k,k}\ }$.
4. Das ${\displaystyle k}$-te Elemente der n. Zeile (für ${\displaystyle 1<k\leq n}$) ist gleich der Summe des links stehenden ${\displaystyle (k-1)}$-ten Elements derselben Zeile und des ${\displaystyle (k-1)}$-ten Elements der vorherigen Zeile (also jene mit der Nummer ${\displaystyle n-1}$): ${\displaystyle \ x_{k,n}=x_{k,n-1}+x_{k-1,n-1}\ }$.
5. ${\displaystyle B_{n}}$ ist nun das ${\displaystyle n}$-te Element aus der ${\displaystyle n}$-ten Zeile ${\displaystyle {\underline {x_{n,n}}}}$ (bzw. das erste Element aus der ${\displaystyle n+1}$-ten Zeile ${\displaystyle x_{n+1,1}}$).

Die ersten sechs Zeilen, erzeugt nach diesen Regeln, sehen wie folgt aus:

1
1	2
2	3	5
5	7	10	15
15	20	27	37	52
052	067	087	114	151	203
203	…

Wegen des dritten Schritts sind die Bellschen Zahlen sowohl auf der linken als auch auf der rechten Kante des Dreiecks zu sehen, lediglich mit dem Unterschied, dass in der ${\displaystyle n}$-ten Zeile links die Zahl ${\displaystyle B_{n-1}}$ und rechts die Zahl ${\displaystyle B_{n}}$ steht.

Bellsche Primzahlen

Im Jahre 1978 formulierte Martin Gardner die Frage, ob unendlich viele Bellsche Zahlen auch Primzahlen sind. Die ersten Bellschen Primzahlen sind:

${\displaystyle n}$ (Folge A051130 in OEIS)	${\displaystyle B_{n}}$ (Folge A051131 in OEIS)
2	2
3	5
7	877
13	27644437
42	35742549198872617291353508656626642567
55	359334085968622831041960188598043661065388726959079837

Die nächste Bellsche Primzahl ist ${\displaystyle B_{2841}}$, die etwa ${\displaystyle 9{,}30740105\times 10^{6538}}$ beträgt.^[8] Sie ist auch die aktuell größte bekannte Bellsche Primzahl (Stand: 5. August 2018). Im Jahre 2002 zeigte Phil Carmody zunächst, dass es sich bei dieser Zahl wahrscheinlich um eine Primzahl (eine sogenannte PRP-Zahl) handelt, sie also entweder tatsächlich eine echte Primzahl oder eine Pseudoprimzahl ist. Nach einer 17-monatigen Berechnung mit Marcel Martins Programm „Primo“, welches mit einem Verfahren mit elliptischen Kurven arbeitet, bewies Ignacio Larrosa Cañestro schließlich im Jahre 2004, dass es sich bei ${\displaystyle B_{2841}}$ um eine Primzahl handelt. Gleichzeitig schloss er weitere Bellsche Primzahlen bis zu einer Grenze von ${\displaystyle B_{6000}}$ aus, welche später von Eric Weisstein auf ${\displaystyle B_{30447}}$ angehoben wurde.

Einzelnachweise

1. ↑ G. Dobiński: Summirung der Reihe ${\displaystyle \textstyle \sum {\frac {n^{m}}{n!}}}$ für ${\displaystyle m=1,2,3,4,5,\ldots }$, Grunert-Archiv 61, 1877, S. 333–336
2. ↑ YYiki: G. Dobínski. Abgerufen am 7. September 2021. 
3. ↑ 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)
4. ↑ Marshall Hall: Arithmetic properties of a partition function, Bulletin of the AMS 40, 1934, S. 387 (englisch; nur Abstract)
5. ↑ 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)
6. ↑ 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)
7. ↑ 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)
8. ↑ 93074010508593618333...(6499 other digits)...83885253703080601131 auf Prime Pages. Abgerufen am 5. August 2018.

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. In 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.