Bellsche Zahl

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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 B0, B1, B2, B3, … beginnt mit

1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, … (Folge A000110 in OEIS)

Bedeutung[Bearbeiten]

Partitionen[Bearbeiten]

Hauptartikel: Partition (Mengenlehre)

Eine Partition P einer Menge M beinhaltet paarweise disjunkte 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 der möglichen verschiedenen Partitionen einer Menge mit der Mächtigkeit n. Formal:

\left | M \right |= n

\forall P \in Q: \bigcup_{x \in P}x=M

\forall P \in Q ~ \forall a,b \in P: 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. Dies weil alle Aussagen mit dem Allquantor über die Elemente der leeren Menge wahr sind (siehe leere Menge).

Multiplikative Partitionen[Bearbeiten]

Hauptartikel: Multiplikative Partition

Sei N eine quadratfreie Zahl, so ist n=\omega(N), wobei \omega : \mathbb{N} \rightarrow \mathbb{N} die Funktion zur Bestimmung der Anzahl der einzigartigen Primfaktoren ist. Dann ist B_n wiederum 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\times 1=2\times 15=3\times 10=5\times 6=2\times 3\times 5

Eigenschaften[Bearbeiten]

Für die Bellschen Zahlen gelten die Rekursionsformel

B_{n+1} = \sum_{k=0}^{n}{{n \choose k}B_k}

und die Formel (Dobiński 1877)[1]

B_n = \frac{1}{e} \sum_{k=0}^\infty \frac{k^n}{k!}\,,

somit ist B_n auch das n-te Moment einer Poisson-Verteilung mit Erwartungswert 1.

Die erzeugende Funktion der Bellzahlen ist

\sum_{n=0}^\infty B_n\,x^n = \frac{1}{e} \sum_{k=0}^\infty \frac{1}{k!\,(1 - k x)}\,,

die exponentiell erzeugende Funktion ist

\sum_{n=0}^\infty \frac{B_n}{n!}\,x^n = e^{e^x-1}\,.

Außerdem genügen die Bellzahlen der Kongruenz (Touchard 1933)[2]

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,[3]

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

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

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[Bearbeiten]

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[Bearbeiten]

BellNumberAnimated.gif

Die Bellschen Zahlen lassen sich intuitiv durch das Bellsche Dreieck erzeugen, welches − wie das Pascalsche Dreieck − aus 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 (1).
  2. Wenn die n-te Zeile (von 1 beginnend) n Elemente hat, so wird eine neue Zeile erzeugt. Dabei ergibt sich die erste Zahl der neuen Zeile aus der letzten Zahl der letzten Zeile.
  3. Die k-te Zahl der Zeile n (für 1 < k \leq n) ergibt sich aus der Summe des (k-1)-ten Elements derselben Zeile und des (k-1)-ten Elements der vorherigen Zeile (also jene mit der Nummer n-1).
  4. B_n ist nun das n-te Element aus der n-ten Zeile.

Die ersten fünf Zeilen − erzeugt nach diesen Regeln − sehen wie folgt aus:

 1
 1   2
 2   3   5
 5   7  10  15
15  20  27  37  52

Wegen des zweiten 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 ist.

Bellsche Primzahlen[Bearbeiten]

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} entspricht [7]. Diese ist auch die aktuell grösste bekannte Bellsche Primzahl. Im Jahre 2002 zeigte Phil Carmody auf, dass es sich bei dieser Zahl wahrscheinlich um eine Primzahl 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 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[Bearbeiten]

  1. G. Dobiński: Summirung der Reihe \scriptstyle\sum\frac{n^m}{n!} für m = 1, 2, 3, 4, 5, …, Grunert-Archiv 61, 1877, S. 333–336
  2. 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)
  3. Marshall Hall: Arithmetic properties of a partition function, Bulletin of the AMS 40, 1934, S. 387 (englisch; nur Abstract)
  4. Christian Radoux: Nombres de Bell, modulo p premier, et extensions de degré p de Fp, Comptes rendus hebdomadaires des séances de l’académie des sciences 281 A, 1975, S. 879–882 (französisch)
  5. 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)
  6. 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)
  7. The Prime Database: "93074010508593618333...(6499 other digits)...83885253703080601131". Abgerufen am 19. Mai 2014.

Literatur[Bearbeiten]

Weblinks[Bearbeiten]