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,\dots$ beginnt mit

$1,1,2,5,15,52,203,877,4140,21147,115975,678570,\dots$ (Vorlage:OEIS)

Bedeutung

Partitionen

Vorlage:Hauptartikel 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$

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

$\mathrm{\forall }P\in Q:\mathrm{\forall }a\in P:a\ne \mathrm{\varnothing }$

$\mathrm{\forall }P\in Q:\mathrm{\forall }a,b\in P:(a\ne b⟹a\cap b=\mathrm{\varnothing })$

$B_n:=\left|Q\right|$

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

Multiplikative Partitionen

Vorlage:Hauptartikel Sei $N$ eine quadratfreie Zahl, $\omega :\mathbb{N}\to \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(\genfrac{}{}{0ex}{}{n}{k})B_k$

Die Dobińskische Formel (Dobiński 1877)

$B_n=\frac{1}{e}\sum _{k=0}^{\mathrm{\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 benannt.

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

Sei

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

Dann gilt:

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

sowie für n ≥ 0:

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

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

Aus

$f(0)=1$ und

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

$\mathrm{\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}^{\mathrm{\infty }}{B}_n{x}^n=\frac{1}{e}\sum _{k=0}^{\mathrm{\infty }}\frac{1}{k!(1-kx)}$

Die exponentiell erzeugende Funktion lautet:

$\sum _{n=0}^{\mathrm{\infty }}\frac{B_n}{n!}{x}^n=e^{e^x-1}$

Dies folgt aus der genannten Dobiński-Formel:

$\sum _{n=0}^{\mathrm{\infty }}\frac{B_n}{n!}{x}^n=\sum _{n=0}^{\mathrm{\infty }}\frac{1}{n!}\left[\frac{1}{e}\sum _{k=0}^{\mathrm{\infty }}\frac{k^n}{k!}\right]x^n=\frac{1}{e}\sum _{n=0}^{\mathrm{\infty }}\sum _{k=0}^{\mathrm{\infty }}\frac{k^n}{k!n!}{x}^n=\frac{1}{e}\sum _{k=0}^{\mathrm{\infty }}\sum _{n=0}^{\mathrm{\infty }}\frac{k^n}{k!n!}{x}^n=\frac{1}{e}\sum _{k=0}^{\mathrm{\infty }}\frac{1}{k!}\sum _{n=0}^{\mathrm{\infty }}\frac{(kx{)}^n}{n!}=$

$=\frac{1}{e}\sum _{k=0}^{\mathrm{\infty }}\frac{1}{k!}\exp (kx)=\frac{1}{e}\sum _{k=0}^{\mathrm{\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)

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

$B_{1+p+\dots +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. 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)$.

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}(\lambda (n){)}^{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:

1. Die erste Zeile hat nur ein Element: Die Eins: $x_{1,1}=1$.
2. Jede folgende Zeile hat jeweils ein Element mehr als die vorherige Zeile, d. h. die $n$-te Zeile hat $n$ Elemente.
3. Das jeweils erste Element jeder Zeile hat den gleichen Wert wie das letzte Element der vorherigen Zeile: $x_{k+1,1}=x_{k,k}$.
4. Das $k$-te Elemente der n. Zeile (für $1<k\le 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}$.
5. $B_n$ ist nun das $n$-te Element aus der $n$-ten Zeile $\underset{\_}{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
Vorlage:052	Vorlage:067	Vorlage: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$ (Vorlage:OEIS)	$B_n$ (Vorlage: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. 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.

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.