imported>Wfstb am 14. März 2025 um 10:02 Uhr

2025-03-14T10:02:11Z

Neue Seite

Die '''Bellsche Zahl''', '''Bellzahl''' oder '''Exponentialzahl''' <math>B_n</math> ist die Anzahl der [[Partition (Mengenlehre)|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> ({{OEIS|A000110}})

== Bedeutung ==

=== Partitionen ===
{{Hauptartikel|Partition (Mengenlehre)}}
Eine Partition <math>P</math> einer Menge <math>M</math> ist eine Menge [[Nichtleere Menge|nichtleerer]], [[paarweise disjunkt]]er [[Teilmenge]]n von <math>M</math>, sodass jedes Element aus <math>M</math> in genau einer Menge aus <math>P</math> vorkommt. Für alle [[Natürliche Zahl|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 (Mathematik)|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 [[Leere Menge|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 [[Aussage (Logik)|Aussagen]] mit dem [[Allquantor]] über die Elemente der leeren Menge wahr sind (siehe [[leere Menge]]).

=== Multiplikative Partitionen ===
{{Hauptartikel|Multiplikative Partition}}
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 [[Multiplikative Partition|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 [[Rekursion]]sformel:
: <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: ''[http://www.archive.org/stream/archivdermathem88unkngoog#page/n346/mode/1up 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>{{Internetquelle |url=https://yyiki.org/wiki/Person/G.%20Dob%C3%ADnski/ |titel=YYiki: G. Dobínski |abruf=2021-09-07}}</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 (Stochastik)|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 (Zahlentheorie)|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 [[Primzahl]]en <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 (Mathematiker)|Marshall Hall]]: ''[http://www.ams.org/journals/bull/1934-40-05/S0002-9904-1934-05853-1/home.html 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 [[Periodizität (Mathematik)|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 Montgomery (Mathematiker)|Peter L. Montgomery]], Sangil Nahm, [[Samuel Wagstaff|Samuel S. Wagstaff]]: ''[http://www.cs.purdue.edu/homes/ssw/mcom2340.pdf 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 Robert (Mathematiker)|Alain M. Robert]]: ''[http://projecteuclid.org/euclid.bbms/1105554416 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 [[Pascalsches Dreieck|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: <math>\ x_{1,1} = 1\ </math>.
# 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.
# 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>.
# 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>.
# <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:
:{| class="wikitable hintergrundfarbe-basis" style="text-align:right; font-weight:500;"
|style="background:#FFD0D0"| 1
|- style="background:#D0FFFF"
|style="background:#D0FFD0"| 1 ||2
|- style="background:#D0FFFF"
|style="background:#D0FFD0"| 2 || 3 ||5
|- style="background:#D0FFFF"
|style="background:#D0FFD0"| 5 || 7 || 10 ||15
|- style="background:#D0FFFF"
|style="background:#D0FFD0"| 15 || 20 || 27 || 37 ||52
|- style="background:#D0FFFF"
|style="background:#D0FFD0"| {{0}}52 || {{0}}67 || {{0}}87 || 114 || 151 ||203
|-
|style="background:#D0FFD0"|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:
{| class="wikitable"
|-
! <math>n</math> ({{OEIS|A051130}}) !! <math>B_n</math> ({{OEIS|A051131}})
|-
| 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>[http://primes.utm.edu/primes/page.php?id=68825 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 [[Elliptische Kurven|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 ==

* [[Eric Temple Bell]]: ''Exponential Numbers'', The American Mathematical Monthly 41, 1934, S. 411–419
* Jacques Touchard: ''[http://books.google.de/books?id=x34z99fCRbsC&pg=PA305 Nombres exponentiels et nombres de Bernoulli]'', Canadian Journal of Mathematics 8, 1956, S. 305–320 (französisch)

== Weblinks ==

* [[Eric Weisstein|Eric W. Weisstein]]: ''[http://mathworld.wolfram.com/BellNumber.html Bell Number]'' und ''[http://mathworld.wolfram.com/DobinskisFormula.html Dobiński’s Formula]''. In [[MathWorld]] (englisch)
* ''[http://functions.wolfram.com/IntegerFunctions/BellB/ Bell numbers]'' bei ''The Wolfram Functions Site'' (englisch; mit Berechnungsmöglichkeit)
* ''[http://dlmf.nist.gov/26.7 Set Partitions: Bell Numbers]'' in der ''NIST Digital Library of Mathematical Functions'' (englisch)
* Peter Luschny: ''[http://oeis.org/wiki/User:Peter_Luschny/SetPartitions Set partitions and Bell numbers]'' (englisch). Eine Zusammenfassung von OEIS-Folgen zu den Bellzahlen im [[OEIS]] Wiki.

[[Kategorie:Ganzzahlmenge]]
[[Kategorie:Primzahl]]
[[Kategorie:Kombinatorik]]

Bellsche Zahl - Versionsgeschichte

imported>Wfstb am 14. März 2025 um 10:02 Uhr