www.wikidata.de-de.nina.az

Bellsche Zahl Die Bellzahl oder Exponentialzahl B n displaystyle B n ist die Anzahl der Partitionen einer n displaystyle

Bellsche Zahl

Die Bellsche Zahl, Bellzahl oder Exponentialzahl ist die Anzahl der Partitionen einer -elementigen Menge. Benannt ist sie nach dem Mathematiker Eric Temple Bell. Die Folge beginnt mit

Bedeutung Bearbeiten

Partitionen Bearbeiten

Eine Partition einer Menge beinhaltet paarweise disjunkte Teilmengen von , sodass jedes Element aus in genau einer Menge aus vorkommt. Für alle natürlichen Zahlen einschließlich der Null bezeichnet nun die Bellsche Zahl die Anzahl der möglichen verschiedenen Partitionen einer Menge mit der Mächtigkeit , wobei die Menge aller möglichen Partitionen darstellt. Formal:

Die Bellsche Zahl mit dem Index 0, , – also die Anzahl der Partitionen der leeren Menge – ist 1, weil die einzige Partition der leeren Menge wieder die leere Menge selbst ist. Dies ist so, weil alle Aussagen mit dem Allquantor über die Elemente der leeren Menge wahr sind (siehe leere Menge).

Multiplikative Partitionen Bearbeiten

Sei eine quadratfreie Zahl, die Funktion zur Bestimmung der Anzahl der einzigartigen Primfaktoren und .

Dann ist die Anzahl der unterschiedlichen multiplikativen Partitionen von .

Sei zum Beispiel , so ist (da 30 aus den drei Primfaktoren 2, 3 und 5 besteht) und ist damit die Anzahl der multiplikativen Partitionen. Diese lauten:

Eigenschaften Bearbeiten

Definition Bearbeiten

Für die Bellschen Zahlen ist diese Rekursionsformel gültig:

Die Dobińskische Formel (Dobiński 1877) dient zur Definition der Bellschen Zahlen für alle Zahlen n ≥ 0:

Diese Formel wurde nach dem polnischen Mathematiker Donald Gabriel Dobiński benannt.

Die Richtigkeit dieser Formel kann durch einen Induktionsbeweis nachgewiesen werden:

Für n ≥ 0 gilt:

Außerdem gilt:

Wenn gilt:

Dann gilt:

Somit ist auch das -te Moment einer Poisson-Verteilung mit Erwartungswert 1.

Erzeugende Funktionen Bearbeiten

Die erzeugende Funktion der Bellzahlen ist wie folgt darstellbar:

Die exponentiell erzeugende Funktion lautet so:

Diese Tatsache kann mit der genannten Dobiński-Formel bewiesen werden:

Kongruenzsätze Bearbeiten

Die Bellschen Zahlen genügen der Kongruenz (Touchard 1933)

für natürliche Zahlen und Primzahlen , insbesondere und und, nach Iteration,

Es wird vermutet, dass die kleinste Periode von ist. Für Primzahlen ist

für gilt die Kongruenz .

Da die Stirling-Zahl zweiter Art die Anzahl der -Partitionen einer -elementigen Menge ist, gilt

Asymptotik Bearbeiten

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

mit der Lambert-W-Funktion .

Bellsches Dreieck Bearbeiten

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

Die ersten sechs Zeilen, erzeugt nach diesen Regeln, sehen wie folgt aus:

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 -ten Zeile links die Zahl und rechts die Zahl 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:

(Folge A051130 in OEIS) (Folge A051131 in OEIS)
2 2
3 5
7 877
13 27644437
42 35742549198872617291353508656626642567
55 359334085968622831041960188598043661065388726959079837

Die nächste Bellsche Primzahl ist , die etwa entspricht. Sie ist auch die aktuell größte bekannte Bellsche Primzahl (Stand: 5. August 2018). Im Jahre 2002 zeigte Phil Carmody, 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 im Jahre 2004, dass es sich bei um eine Primzahl handelt. Gleichzeitig schloss er weitere Bellsche Primzahlen bis zu einer Grenze von aus, welche später von Eric Weisstein auf angehoben wurde.

Einzelnachweise Bearbeiten

  1. G. Dobiński: Summirung der Reihe für , Grunert-Archiv 61, 1877, S. 333–336
  2. YYiki: G. Dobínski. Abgerufen am 7. September 2021.
  3. 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)
  4. Marshall Hall: Arithmetic properties of a partition function, Bulletin of the AMS 40, 1934, S. 387 (englisch; nur Abstract)
  5. 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)
  6. 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)
  7. 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)
  8. 93074010508593618333...(6499 other digits)...83885253703080601131 auf Prime Pages. Abgerufen am 5. August 2018.

Literatur Bearbeiten

  • 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 Bearbeiten

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Die Bellsche Zahl Bellzahl oder Exponentialzahl B n displaystyle B n ist die Anzahl der Partitionen einer n displaystyle n elementigen Menge Benannt ist sie nach dem Mathematiker Eric Temple Bell Die Folge B 0 B 1 B 2 B 3 displaystyle B 0 B 1 B 2 B 3 ldots beginnt mit 1 1 2 5 15 52 203 877 4140 21147 115975 678570 displaystyle 1 1 2 5 15 52 203 877 4140 21147 115975 678570 ldots Folge A000110 in OEIS Inhaltsverzeichnis 1 Bedeutung 1 1 Partitionen 1 2 Multiplikative Partitionen 2 Eigenschaften 2 1 Definition 2 2 Erzeugende Funktionen 2 3 Kongruenzsatze 3 Asymptotik 4 Bellsches Dreieck 5 Bellsche Primzahlen 6 Einzelnachweise 7 Literatur 8 WeblinksBedeutung BearbeitenPartitionen Bearbeiten Hauptartikel Partition Mengenlehre Eine Partition P displaystyle P nbsp einer Menge M displaystyle M nbsp beinhaltet paarweise disjunkte Teilmengen von M displaystyle M nbsp sodass jedes Element aus M displaystyle M nbsp in genau einer Menge aus P displaystyle P nbsp vorkommt Fur alle naturlichen Zahlen einschliesslich der Null n N 0 displaystyle n in mathbb N 0 nbsp bezeichnet nun die Bellsche Zahl B n displaystyle B n nbsp die Anzahl Q displaystyle left Q right nbsp der moglichen verschiedenen Partitionen einer Menge mit der Machtigkeit n displaystyle n nbsp wobei Q displaystyle Q nbsp die Menge aller moglichen Partitionen darstellt Formal M n displaystyle left M right n nbsp P Q x P x M displaystyle forall P in Q bigcup x in P x M nbsp P Q a b P a b a b displaystyle forall P in Q forall a b in P a neq b Longrightarrow a cap b emptyset nbsp B n Q displaystyle B n left Q right nbsp Die Bellsche Zahl mit dem Index 0 B 0 displaystyle B 0 nbsp also die Anzahl der Partitionen der leeren Menge displaystyle emptyset nbsp ist 1 weil die einzige Partition der leeren Menge wieder die leere Menge selbst ist Dies ist so weil alle Aussagen mit dem Allquantor uber die Elemente der leeren Menge wahr sind siehe leere Menge Multiplikative Partitionen Bearbeiten Hauptartikel Multiplikative Partition Sei N displaystyle N nbsp eine quadratfreie Zahl w N N displaystyle omega mathbb N rightarrow mathbb N nbsp die Funktion zur Bestimmung der Anzahl der einzigartigen Primfaktoren und n w N displaystyle n omega N nbsp Dann ist B n displaystyle B n nbsp die Anzahl der unterschiedlichen multiplikativen Partitionen von N displaystyle N nbsp Sei zum Beispiel N 30 displaystyle N 30 nbsp so ist n w 30 3 displaystyle n omega 30 3 nbsp da 30 aus den drei Primfaktoren 2 3 und 5 besteht und B 3 5 displaystyle B 3 5 nbsp ist damit die Anzahl der multiplikativen Partitionen Diese lauten 30 2 15 3 10 5 6 2 3 5 displaystyle 30 2 times 15 3 times 10 5 times 6 2 times 3 times 5 nbsp Eigenschaften BearbeitenDefinition Bearbeiten Fur die Bellschen Zahlen ist diese Rekursionsformel gultig B n 1 k 0 n n k B k displaystyle B n 1 sum k 0 n n choose k B k nbsp Die Dobinskische Formel Dobinski 1877 1 dient zur Definition der Bellschen Zahlen fur alle Zahlen n 0 B n 1 e k 0 k n k displaystyle B n frac 1 e sum k 0 infty frac k n k nbsp Diese Formel wurde nach dem polnischen Mathematiker Donald Gabriel Dobinski 2 benannt Die Richtigkeit dieser Formel kann durch einen Induktionsbeweis nachgewiesen werden f n 1 e k 0 k n k displaystyle f n frac 1 e sum k 0 infty frac k n k nbsp Fur n 0 gilt f n 1 1 e k 0 k n 1 k 1 e k 1 k n 1 k 1 e k 0 k 1 n 1 k 1 1 e k 0 k 1 n k displaystyle 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 nbsp 1 e k 0 1 k m 0 n n m k m m 0 n n m 1 e k 0 k m k m 0 n n m f m displaystyle 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 nbsp Ausserdem gilt f 0 1 e k 0 1 k 1 displaystyle f 0 frac 1 e sum k 0 infty frac 1 k 1 nbsp Wenn gilt f n 1 m 0 n n m f m displaystyle f n 1 sum m 0 n binom n m f m nbsp und f 0 1 displaystyle f 0 1 nbsp Dann gilt f n B n displaystyle f n B n nbsp Somit ist B n displaystyle B n nbsp auch das n displaystyle n nbsp te Moment einer Poisson Verteilung mit Erwartungswert 1 Erzeugende Funktionen Bearbeiten Die erzeugende Funktion der Bellzahlen ist wie folgt darstellbar n 0 B n x n 1 e k 0 1 k 1 k x displaystyle sum n 0 infty B n x n frac 1 e sum k 0 infty frac 1 k 1 kx nbsp Die exponentiell erzeugende Funktion lautet so n 0 B n n x n e e x 1 displaystyle sum n 0 infty frac B n n x n e e x 1 nbsp Diese Tatsache kann mit der genannten Dobinski Formel bewiesen werden n 0 B n n x n n 0 1 n 1 e k 0 k n k x n 1 e n 0 k 0 k n k n x n 1 e k 0 n 0 k n k n x n 1 e k 0 1 k n 0 k x n n displaystyle 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 nbsp 1 e k 0 1 k exp k x 1 e k 0 1 k exp x k 1 e exp exp x exp exp x 1 displaystyle 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 nbsp Kongruenzsatze Bearbeiten Die Bellschen Zahlen genugen der Kongruenz Touchard 1933 3 B p k n k B n B n 1 mod p displaystyle B p k n equiv k B n B n 1 text mod p nbsp fur naturliche Zahlen k displaystyle k nbsp und Primzahlen p displaystyle p nbsp insbesondere B p k k 1 mod p displaystyle B p k equiv k 1 text mod p nbsp und B p 2 mod p displaystyle B p equiv 2 text mod p nbsp und nach Iteration 4 B 1 p p p 1 n B n mod p displaystyle B 1 p ldots p p 1 n equiv B n text mod p nbsp Es wird vermutet dass 1 p p p 1 displaystyle 1 p dots p p 1 nbsp die kleinste Periode von B n mod p displaystyle B n text mod p nbsp ist 5 6 Fur Primzahlen p gt 2 displaystyle p gt 2 nbsp ist B p k 1 n B p k n 1 mod p k 1 displaystyle B p k 1 n equiv B p k n 1 text mod p k 1 nbsp fur p 2 displaystyle p 2 nbsp gilt die Kongruenz mod p k displaystyle text mod p k nbsp 7 Da die Stirling Zahl S n k displaystyle S n k nbsp zweiter Art die Anzahl der k displaystyle k nbsp Partitionen einer n displaystyle n nbsp elementigen Menge ist gilt B n k 0 n S n k displaystyle B n sum k 0 n S n k nbsp Asymptotik BearbeitenFur die Bellzahlen sind verschiedene asymptotische Formeln bekannt etwa B n n 1 2 l n n 1 2 e l n n 1 displaystyle B n sim n 1 2 bigl lambda n bigr n 1 2 e lambda n n 1 nbsp mit l n e W n n W n displaystyle lambda n e W n frac n W n nbsp mit der Lambert W Funktion W displaystyle W nbsp Bellsches Dreieck BearbeitenDie 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 Die erste Zeile hat nur ein Element Die Eins x 1 1 1 displaystyle x 1 1 1 nbsp Jede folgende Zeile hat jeweils ein Element mehr als die vorherige Zeile d h die n displaystyle n nbsp te Zeile hat n displaystyle n nbsp 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 displaystyle x k 1 1 x k k nbsp Das k displaystyle k nbsp te Elemente der n Zeile fur 1 lt k n displaystyle 1 lt k leq n nbsp ist gleich der Summe des links stehenden k 1 displaystyle k 1 nbsp ten Elements derselben Zeile und des k 1 displaystyle k 1 nbsp ten Elements der vorherigen Zeile also jene mit der Nummer n 1 displaystyle n 1 nbsp x k n x k n 1 x k 1 n 1 displaystyle x k n x k n 1 x k 1 n 1 nbsp B n displaystyle B n nbsp ist nun das n displaystyle n nbsp te Element aus der n displaystyle n nbsp ten Zeile x n n displaystyle underline x n n nbsp bzw das erste Element aus der n 1 displaystyle n 1 nbsp ten Zeile x n 1 1 displaystyle x n 1 1 nbsp Die ersten sechs Zeilen erzeugt nach diesen Regeln sehen wie folgt aus 11 22 3 55 7 10 1515 20 27 37 5252 0 67 0 87 114 151 203203 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 displaystyle n nbsp ten Zeile links die Zahl B n 1 displaystyle B n 1 nbsp und rechts die Zahl B n displaystyle B n nbsp ist Bellsche Primzahlen BearbeitenIm Jahre 1978 formulierte Martin Gardner die Frage ob unendlich viele Bellsche Zahlen auch Primzahlen sind Die ersten Bellschen Primzahlen sind n displaystyle n nbsp Folge A051130 in OEIS B n displaystyle B n nbsp Folge A051131 in OEIS 2 23 57 87713 2764443742 3574254919887261729135350865662664256755 359334085968622831041960188598043661065388726959079837Die nachste Bellsche Primzahl ist B 2841 displaystyle B 2841 nbsp die etwa 9 307 40105 10 6538 displaystyle 9 30740105 times 10 6538 nbsp entspricht 8 Sie ist auch die aktuell grosste bekannte Bellsche Primzahl Stand 5 August 2018 Im Jahre 2002 zeigte Phil Carmody dass es sich bei dieser Zahl wahrscheinlich um eine Primzahl eine sogenannte PRP Zahl handelt sie also entweder tatsachlich 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 Canestro im Jahre 2004 dass es sich bei B 2841 displaystyle B 2841 nbsp um eine Primzahl handelt Gleichzeitig schloss er weitere Bellsche Primzahlen bis zu einer Grenze von B 6000 displaystyle B 6000 nbsp aus welche spater von Eric Weisstein auf B 30447 displaystyle B 30447 nbsp angehoben wurde Einzelnachweise Bearbeiten G Dobinski Summirung der Reihe n m n displaystyle textstyle sum frac n m n nbsp fur m 1 2 3 4 5 displaystyle m 1 2 3 4 5 ldots nbsp Grunert Archiv 61 1877 S 333 336 YYiki G Dobinski Abgerufen am 7 September 2021 Jacques Touchard Proprietes arithmetiques de certains nombres recurrents Annales de la Societe scientifique de Bruxelles A 53 1933 S 21 31 franzosisch Marshall Hall Arithmetic properties of a partition function Bulletin of the AMS 40 1934 S 387 englisch nur Abstract Christian Radoux Nombres de Bell modulo p premier et extensions de degre p de Fp Comptes rendus hebdomadaires des seances de l academie des sciences 281 A 1975 S 879 882 franzosisch 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 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 93074010508593618333 6499 other digits 83885253703080601131 auf Prime Pages Abgerufen am 5 August 2018 Literatur BearbeitenEric 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 franzosisch Weblinks BearbeitenEric W Weisstein Bell Number und Dobinski s Formula In MathWorld englisch Bell numbers bei The Wolfram Functions Site englisch mit Berechnungsmoglichkeit 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 Abgerufen von https de wikipedia org w index php title Bellsche Zahl amp oldid 239098592