Zum Inhalt springen

Bellsche Zahl

aus Wikipedia, der freien Enzyklopädie
Dies ist die aktuelle Version dieser Seite, zuletzt bearbeitet am 14. März 2025 um 10:02 Uhr durch imported>Wfstb.
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)

Die Bellsche Zahl, Bellzahl oder Exponentialzahl <math>B_n</math> ist die Anzahl der Partitionen einer <math>n</math>-elementigen Menge. Benannt ist sie nach dem Mathematiker Eric Temple Bell. Die Folge <math>B_0,B_1,B_2,B_3,\ldots</math> beginnt mit

<math>1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, \ldots</math> (Folge A000110 in OEIS)

Bedeutung

Partitionen

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

<math>\left | M \right |= n</math>
<math>\forall P \in Q: \bigcup_{a \in P}a=M</math>
<math>\forall P \in Q: \forall a \in P: a \ne \emptyset</math>
<math>\forall P \in Q: \forall a,b \in P: (a\neq b \Longrightarrow a \cap b = \emptyset)</math>
<math>B_n := \left | Q \right |</math>

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

Multiplikative Partitionen

Sei <math>N</math> eine quadratfreie Zahl, <math>\omega : \mathbb{N} \rightarrow \mathbb{N}</math> die Funktion zur Bestimmung der Anzahl der einzigartigen Primfaktoren und <math>n=\omega(N)</math>.

Dann ist <math>B_n</math> die Anzahl der unterschiedlichen multiplikativen Partitionen von <math>N</math>.

Sei zum Beispiel <math>N=30</math>, so ist <math>n=\omega(30)=3</math> (da 30 aus den drei Primfaktoren 2, 3 und 5 besteht) und <math>B_3=5</math> ist damit die Anzahl der multiplikativen Partitionen. Diese lauten:

<math>30=2\times 15=3\times 10=5\times 6=2\times 3\times 5</math>

Eigenschaften

Definition

Für die Bellschen Zahlen gilt diese Rekursionsformel:

<math>B_{n+1} = \sum_{k=0}^{n}{{n \choose k}B_k}</math>

Die Dobińskische Formel (Dobiński 1877)<ref>G. Dobiński: Summirung der Reihe <math>\textstyle \sum\frac{n^m}{n!}</math> für <math>m = 1, 2, 3, 4, 5, \ldots</math>, Grunert-Archiv 61, 1877, S. 333–336</ref>

<math>B_n = \frac{1}{e} \sum_{k=0}^{\infty} \frac{k^n}{k!}</math>

erlaubt die explizite Definition der Bellschen Zahlen für alle n ≥ 0. Sie wurde nach dem polnischen Mathematiker Donald Gabriel Dobiński<ref>YYiki: G. Dobínski. Abgerufen am 7. September 2021.</ref> benannt.

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

Sei

<math>f(n) = \frac{1}{e} \sum_{k=0}^{\infty} \frac{k^n}{k!}</math> .

Dann gilt:

<math>f(0) = \frac{1}{e} \sum_{k=0}^{\infty} \frac{1}{k!} = 1</math>

sowie für n ≥ 0:

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

Aus

<math>f(0) = 1 </math> und

<math>\forall n \in \N_0: f(n+1) = \sum_{m=0}^{n} \binom{n}{m} f(m) </math> folgt schließlich:

<math>\forall n \in \N_0: f(n) = B_{n}</math>

Somit ist <math>B_n</math> auch das <math>n</math>-te Moment einer Poisson-Verteilung mit Erwartungswert 1.

Erzeugende Funktionen

Die erzeugende Funktion der Bellzahlen ist wie folgt darstellbar:

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

Die exponentiell erzeugende Funktion lautet:

<math>\sum_{n=0}^{\infty} \frac{B_n}{n!}\,x^n = e^{e^x-1}</math>

Dies folgt aus der genannten Dobiński-Formel:

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

Kongruenzsätze

Die Bellschen Zahlen genügen der Kongruenz (Touchard 1933)<ref>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)</ref>

<math>B_{p^k + n} \equiv k\,B_n + B_{n+1} \ (\text{mod }p)</math>

für natürliche Zahlen <math>k</math> und Primzahlen <math>p</math>, insbesondere <math>B_{p^k} \equiv k + 1 \ (\text{mod }p)</math> und <math>B_p \equiv 2 \ (\text{mod }p)</math> und, nach Iteration,<ref>Marshall Hall: Arithmetic properties of a partition function, Bulletin of the AMS 40, 1934, S. 387 (englisch; nur Abstract)</ref>

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

Es wird vermutet, dass <math>1 + p + \dots + p^{p-1}</math> die kleinste Periode von <math>B_n \ (\text{mod }p)</math> ist.<ref>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)</ref><ref>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)</ref> Für Primzahlen <math>p > 2</math> ist

<math>B_{p^{k+1} n} \equiv B_{p^k n + 1} \ (\text{mod }p^{k+1}),</math>

für <math>p = 2</math> gilt die Kongruenz <math>(\text{mod }p^k)</math>.<ref>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)</ref>

Da die Stirling-Zahl <math>S(n, k)</math> zweiter Art die Anzahl der <math>k</math>-Partitionen einer <math>n</math>-elementigen Menge ist, gilt

<math>B_n = \sum_{k=0}^n S(n,k).</math>

Asymptotik

Für die Bellzahlen sind verschiedene asymptotische Formeln bekannt, etwa

<math>B_n \sim n^{-1/2}\ \bigl(\lambda(n)\bigr)^{n + 1/2}\ e^{\lambda(n) - n - 1}</math>     mit     <math>\lambda(n) = e^{W(n)} = \frac{n}{W(n)}</math>

mit der Lambert-W-Funktion <math>W</math>.

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

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 <math>n</math>-ten Zeile links die Zahl <math>B_{n-1}</math> und rechts die Zahl <math>B_n</math> steht.

Bellsche Primzahlen

Im Jahre 1978 formulierte Martin Gardner die Frage, ob unendlich viele Bellsche Zahlen auch Primzahlen sind. Die ersten Bellschen Primzahlen sind:

<math>n</math> (Folge A051130 in OEIS) <math>B_n</math> (Folge A051131 in OEIS)
2 2
3 5
7 877
13 27644437
42 35742549198872617291353508656626642567
55 359334085968622831041960188598043661065388726959079837

Die nächste Bellsche Primzahl ist <math>B_{2841}</math>, die etwa <math>9{,}30740105 \times 10^{6538}</math> beträgt.<ref>93074010508593618333...(6499 other digits)...83885253703080601131 auf Prime Pages. Abgerufen am 5. August 2018.</ref> 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 <math>B_{2841}</math> um eine Primzahl handelt. Gleichzeitig schloss er weitere Bellsche Primzahlen bis zu einer Grenze von <math>B_{6000}</math> aus, welche später von Eric Weisstein auf <math>B_{30447}</math> angehoben wurde.

Einzelnachweise

<references />

Literatur

Weblinks

Abgerufen von „https://wiki-de.moshellshocker.dns64.de/index.php?title=Bellsche_Zahl&oldid=346950“