„Bellsche Zahl“ – Versionsunterschied

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

→ Hauptartikel: Partition (Mengenlehre)

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

→ Hauptartikel: Multiplikative Partition

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:

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\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}\$.
5. $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. 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.