# 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)
    $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 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)
    $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+\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. 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}\ {\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 12 235 571015 1520273752 052067087114151203 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. 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.