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_{0},B_{1},B_{2},B_{3},\ldots$ beginnt mit

1,1,2,5,15,52,203,877,4140,21147,115975,678570,\ldots

(Folge A000110 in OEIS)

Bedeutung

Partitionen

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

\left|M\right|=n

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

\forall P\in Q:\forall a\in P:a\neq \emptyset

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

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

Die Bellsche Zahl mit dem Index 0, $B_{0}$ , – also die Anzahl der Partitionen der leeren Menge $\emptyset$ – ist 1, weil die einzige Partition der leeren Menge wieder die leere Menge selbst ist, $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 $N$ eine quadratfreie Zahl, $\omega :\mathbb {N} \rightarrow \mathbb {N}$ die Funktion zur Bestimmung der Anzahl der einzigartigen Primfaktoren und $n=\omega (N)$ .

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

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

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:

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

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

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

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

.

Dann gilt:

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

sowie für n ≥ 0:

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!}}=

={\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

f(0)=1

und

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

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

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

Erzeugende Funktionen

Die erzeugende Funktion der Bellzahlen ist wie folgt darstellbar:

\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:

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

Dies folgt aus der genannten Dobiński-Formel:

\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!}}=

={\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]

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,^[4]

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

Es wird vermutet, dass $1+p+\dots +p^{p-1}$ die kleinste Periode von $B_{n}\ ({\text{mod }}p)$ ist.^[5]^[6] 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 $({\text{mod }}p^{k})$ .^[7]

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

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:

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

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

Die nächste Bellsche Primzahl ist $B_{2841}$ , die etwa $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 $B_{2841}$ um eine Primzahl handelt. Gleichzeitig schloss er weitere Bellsche Primzahlen bis zu einer Grenze von $B_{6000}$ aus, welche später von Eric Weisstein auf $B_{30447}$ angehoben wurde.

Einzelnachweise

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

[1] G. Dobiński: Summirung der Reihe $\textstyle \sum {\frac {n^{m}}{n!}}$ für $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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

Fahrer / Team für die Suche eingeben: