Bellsche Zahl

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

{{#if: Partition (Mengenlehre)|{{#ifexist:Partition (Mengenlehre)|

|{{#if: |{{#ifexist:{{{2}}}|

→ Haupt{{#if:|seite|artikel}}: [[{{{2}}}{{#if: ||{{{titel2}}}}}]]{{#if: |{{#ifexist:{{{3}}}| und [[{{{3}}}{{#if: ||{{{titel3}}}}}]]|}}|}}

|{{#if: |{{#ifexist:{{{3}}}|

→ Haupt{{#if:|seite|artikel}}: [[{{{3}}}{{#if: ||{{{titel3}}}}}]]

|}}|}}|}}|}}|}}|Einbindungsfehler: Die Vorlage Hauptartikel benötigt immer mindestens ein Argument.}}

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

{{#if: Multiplikative Partition|{{#ifexist:Multiplikative Partition|

|{{#if: |{{#ifexist:{{{2}}}|

→ Haupt{{#if:|seite|artikel}}: [[{{{2}}}{{#if: ||{{{titel2}}}}}]]{{#if: |{{#ifexist:{{{3}}}| und [[{{{3}}}{{#if: ||{{{titel3}}}}}]]|}}|}}

|{{#if: |{{#ifexist:{{{3}}}|

→ Haupt{{#if:|seite|artikel}}: [[{{{3}}}{{#if: ||{{{titel3}}}}}]]

|}}|}}|}}|}}|}}|Einbindungsfehler: Die Vorlage Hauptartikel benötigt immer mindestens ein Argument.}}

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>{{#if:|{{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|Vorlage:FormatDate/Wartung/Error}}| |}}}}{{#if:|{{{autor}}}: }}{{#if:|{{#if:YYiki: G. Dobínski|[{{#invoke:Vorlage:Internetquelle|archivURL|1={{#invoke:URLutil|getNormalized|1={{{archiv-url}}}}}}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel=YYiki: G. Dobínski}}]{{#if:| ({{{format}}})}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}|{{#if:https://yyiki.org/wiki/Person/G.%20Dob%C3%ADnski/%7C{{#if:{{#invoke:TemplUtl%7Cfaculty%7C}}%7C{{#invoke:Vorlage:Internetquelle%7CTitelFormat%7Ctitel={{#invoke:WLink%7CgetEscapedTitle%7C1=YYiki: G. Dobínski}}}}|[{{#invoke:URLutil|getNormalized|1=https://yyiki.org/wiki/Person/G.%20Dob%C3%ADnski/}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{#invoke:WLink|getEscapedTitle|1=YYiki: G. Dobínski}}}}]}}{{#if:| ({{{format}}}{{#if:{{#if: 2021-09-07 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}}

          | )
          | {{#if:{{#ifeq:de|de||{{#if:|1}}}}| ; 
              | )}}}}}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}}}{{#if:https://yyiki.org/wiki/Person/G.%20Dob%C3%ADnski/%7C{{#if:{{#invoke:URLutil%7CisResourceURL%7C1=https://yyiki.org/wiki/Person/G.%20Dob%C3%ADnski/}}%7C%7C URL ungültig}}}}{{#if:YYiki: G. Dobínski|{{#if:{{#invoke:WLink|isValidLinktext|1=YYiki: G. Dobínski|lines=0}}|| Linktext ungültig}}}}{{#if: | In: {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{{werk}}}}}}}{{#if: | {{{hrsg}}}{{#if: |,|{{#if: 2021-09-07 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: | {{#if:{{#invoke:DateTime|format|{{{datum}}}|noerror=1}}
            |{{#invoke:DateTime|format|{{{datum}}}|T._Monat JJJJ}}
            |{{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, datum={{{datum}}}|class=Zitationswartung}} }}{{#if: |,|{{#if: 2021-09-07 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: | S. {{{seiten}}}{{#if: |,|{{#if: 2021-09-07 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: {{#invoke:TemplUtl|faculty|}}| {{#if:|{{#if:|archiviert|ehemals}}|{{#if:|Archiviert|Ehemals}}}} {{#if:|vom|im}} Vorlage:Referrer{{#if:{{#invoke:TemplUtl|faculty|}}| (nicht mehr online verfügbar)}}{{#if: | am {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|Vorlage:FormatDate/Wartung/Error}}|{{{archiv-datum}}}{{#if:346950||(?)}}}}}}{{#if: 2021-09-07|;}}}}{{#if: 2021-09-07| {{#if:{{#invoke:TemplUtl|faculty|}}|abgerufen|Abgerufen}} {{#switch: {{#invoke:Str|len| {{#invoke:DateTime|format| 2021-09-07 |ISO|noerror=1}} }}
       |4=im Jahr
       |7=im
       |10=am
       |#default={{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, abruf=2021-09-07|class=Zitationswartung}} }} {{#invoke:DateTime|format|2021-09-07|T._Monat JJJJ}}
    | {{#invoke:TemplUtl|failure|1=Vorlage:Internetquelle | abruf=2026-MM-TT ist Pflichtparameter}} Vorlage:Internetquelle | abruf=2026-MM-TT ist Pflichtparameter}}{{#if:{{#ifeq:de|de||{{#if:|1}}}}|{{#if:{{#if: 2021-09-07 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}}
       |  (
       | {{#if: | |  (}}
       }}{{#ifeq:{{#if:de|de|de}}|de||
          {{#invoke:Multilingual|format|{{{sprache}}}|slang=!|split=[%s,]+|shift=m|separator=, }}}}{{#if: |{{#ifeq:{{#if:de|de|de}}|de||, }}{{{kommentar}}}}})}}{{#if: {{#if: 2021-09-07 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}} }}|{{#if: |: {{
 #if: 
 | „{{
     #ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | Vorlage:Str trim
     | {{#invoke:Vorlage:lang|flat}}
     }}“
 | {{#ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | „Vorlage:Str trim“
     | {{#invoke:Text|quote
         |1={{#if: 
              | {{#invoke:Vorlage:lang|flat}}
              | {{#invoke:Vorlage:lang|flat}} }}
         |2={{#if: {{#invoke:TemplUtl|faculty|}}|de-CH|de}}
         |3=1}} }}

}}{{#if:

   |  (<templatestyles src="Person/styles.css" />{{#if:  | :  }}{{#if:  | , deutsch: „“ }})
   | {{#if: 
       |  ({{#if:  | , deutsch: „“ }})
       | {{#if:  |  (deutsch: „“) }}
 }}

}}{{#if: {{{zitat}}}

   | {{#if: 
       | {{#if: {{{zitat}}}
           | Vorlage:": Text= und 1= gleichzeitig, bzw. Pipe zu viel }} }}
   | Vorlage:": Text= fehlt }}{{#if:  | {{#if: {{#invoke:Text|unstrip|{{{ref}}}}}
             | Vorlage:": Ungültiger Wert: ref=
             | {{{ref}}} }}

}}|.{{#if:{{#invoke:TemplUtl|faculty|}}|{{#if:||{{#ifeq: | JaKeinHinweis |{{#switch:

   |0|=Vorlage:Toter Link/Core{{#if: https://yyiki.org/wiki/Person/G.%20Dob%C3%ADnski/
       | {{#if:  | [1] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   =  @@@
         |preview  = 1
    }}{{#if: https://yyiki.org/wiki/Person/G.%20Dob%C3%ADnski/
      | {{#if:{{#invoke:URLutil|isWebURL|https://yyiki.org/wiki/Person/G.%20Dob%C3%ADnski/}}
          ||  Fehler bei Vorlage:Toter Link: Wert in 'url' ist ungültig.{{#if:  ||  }} 
        }}
      | {{#if: 
           |  Fehler bei Vorlage:Toter Link: 'text' angegeben, aber 'url'' fehlt.{{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             ||  Fehler bei Vorlage:Toter Link: Wert in 'date' ist ungültig.{{#if:  ||  }} 
         }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=   Fehler bei Vorlage:Toter Link: Wert in 'botlauf' ist ungültig.{{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://yyiki.org/wiki/Person/G.%20Dob%C3%ADnski/ Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   =  @@@
         |preview  = 1
       }}{{#if: https://yyiki.org/wiki/Person/G.%20Dob%C3%ADnski/
       | {{#if:{{#invoke:URLutil|isWebURL|https://yyiki.org/wiki/Person/G.%20Dob%C3%ADnski/}}
          ||  Fehler bei Vorlage:Toter Link: Wert in 'url' ist ungültig.{{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             ||  Fehler bei Vorlage:Toter Link: Wert in 'date' ist ungültig.{{#if:  ||  }} 
           }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=   Fehler bei Vorlage:Toter Link: Wert in 'botlauf' ist ungültig.{{#if:  ||  }}
    }}[https://yyiki.org/wiki/Person/G.%20Dob%C3%ADnski/ }}|{{#switch: 
   |0|=Vorlage:Toter Link/Core{{#if: https://yyiki.org/wiki/Person/G.%20Dob%C3%ADnski/
       | {{#if:  | [2] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   =  @@@
         |preview  = 1
    }}{{#if: https://yyiki.org/wiki/Person/G.%20Dob%C3%ADnski/
      | {{#if:{{#invoke:URLutil|isWebURL|https://yyiki.org/wiki/Person/G.%20Dob%C3%ADnski/}}
          ||  Fehler bei Vorlage:Toter Link: Wert in 'url' ist ungültig.{{#if:  ||  }} 
        }}
      | {{#if: 
           |  Fehler bei Vorlage:Toter Link: 'text' angegeben, aber 'url'' fehlt.{{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             ||  Fehler bei Vorlage:Toter Link: Wert in 'date' ist ungültig.{{#if:  ||  }} 
         }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=   Fehler bei Vorlage:Toter Link: Wert in 'botlauf' ist ungültig.{{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://yyiki.org/wiki/Person/G.%20Dob%C3%ADnski/ Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   =  @@@
         |preview  = 1
       }}{{#if: https://yyiki.org/wiki/Person/G.%20Dob%C3%ADnski/
       | {{#if:{{#invoke:URLutil|isWebURL|https://yyiki.org/wiki/Person/G.%20Dob%C3%ADnski/}}
          ||  Fehler bei Vorlage:Toter Link: Wert in 'url' ist ungültig.{{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             ||  Fehler bei Vorlage:Toter Link: Wert in 'date' ist ungültig.{{#if:  ||  }} 
           }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=   Fehler bei Vorlage:Toter Link: Wert in 'botlauf' ist ungültig.{{#if:  ||  }}
    }}[https://yyiki.org/wiki/Person/G.%20Dob%C3%ADnski/ }} }}}}}}}}}}{{#if:|
        {{#invoke:Vorlage:Internetquelle|archivBot|stamp={{{archiv-bot}}}|text={{#if:|Vorlage:Webarchiv/archiv-bot}}

}}}} {{#invoke:TemplatePar|check |all= url= titel= |opt= autor= hrsg= format= sprache= titelerg= werk= seiten= datum= abruf= zugriff= abruf-verborgen= archiv-url= archiv-datum= archiv-bot= kommentar= zitat= AT= CH= offline= |cat= {{#ifeq: 0 | 0 | Wikipedia:Vorlagenfehler/Vorlage:Internetquelle}} |template= Vorlage:Internetquelle |format=0 |preview=1 }}</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 F_p, 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

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:

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:

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

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.