Bellsche Zahl

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

${\displaystyle \left|M\right|=n}$

${\displaystyle \forall P\in Q:\bigcup _{a\in P}a=M}$

${\displaystyle \forall P\in Q:\forall a\in P:a\neq \emptyset }$

${\displaystyle \forall P\in Q:\forall a,b\in P:(a\neq b\Longrightarrow a\cap b=\emptyset )}$

${\displaystyle B_{n}:=\left|Q\right|}$

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

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

Dann ist ${\displaystyle B_{n}}$ die Anzahl der unterschiedlichen multiplikativen Partitionen von ${\displaystyle N}$.

Sei zum Beispiel ${\displaystyle N=30}$, so ist ${\displaystyle n=\omega (30)=3}$ (da 30 aus den drei Primfaktoren 2, 3 und 5 besteht) und ${\displaystyle B_{3}=5}$ ist damit die Anzahl der multiplikativen Partitionen. Diese lauten:

${\displaystyle 30=2\times 15=3\times 10=5\times 6=2\times 3\times 5}$

Für die Bellschen Zahlen gilt diese Rekursionsformel:

${\displaystyle B_{n+1}=\sum _{k=0}^{n}{{n \choose k}B_{k}}}$

Die Dobińskische Formel (Dobiński 1877)[1]

${\displaystyle B_{n}={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {k^{n}}{k!}}}$

erlaubt die explizite Definition der Bellschen Zahlen für alle n ≥ 0. Sie wurde nach dem polnischen Mathematiker Donald Gabriel Dobiński[2] benannt.

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

Sei

${\displaystyle f(n)={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {k^{n}}{k!}}}$ .

Dann gilt:

${\displaystyle f(0)={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {1}{k!}}=1}$

sowie für n ≥ 0:

${\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!}}=}$

${\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)}$

Aus

${\displaystyle f(0)=1}$ und

${\displaystyle \forall n\in \mathbb {N} _{0}:f(n+1)=\sum _{m=0}^{n}{\binom {n}{m}}f(m)}$ folgt schließlich:

${\displaystyle \forall n\in \mathbb {N} _{0}:f(n)=B_{n}}$

Somit ist ${\displaystyle B_{n}}$ auch das ${\displaystyle n}$-te Moment einer Poisson-Verteilung mit Erwartungswert 1.

Die erzeugende Funktion der Bellzahlen ist wie folgt darstellbar:

${\displaystyle \sum _{n=0}^{\infty }B_{n}\,x^{n}={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {1}{k!\,(1-kx)}}}$

Die exponentiell erzeugende Funktion lautet:

${\displaystyle \sum _{n=0}^{\infty }{\frac {B_{n}}{n!}}\,x^{n}=e^{e^{x}-1}}$

Dies folgt aus der genannten Dobiński-Formel:

${\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!}}=}$

${\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]}$

Die Bellschen Zahlen genügen der Kongruenz (Touchard 1933)[3]

${\displaystyle B_{p^{k}+n}\equiv k\,B_{n}+B_{n+1}\ ({\text{mod }}p)}$

für natürliche Zahlen ${\displaystyle k}$ und Primzahlen ${\displaystyle p}$, insbesondere ${\displaystyle B_{p^{k}}\equiv k+1\ ({\text{mod }}p)}$ und ${\displaystyle B_{p}\equiv 2\ ({\text{mod }}p)}$ und, nach Iteration,[4]

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

Es wird vermutet, dass ${\displaystyle 1+p+\dots +p^{p-1}}$ die kleinste Periode von ${\displaystyle B_{n}\ ({\text{mod }}p)}$ ist.[5][6] Für Primzahlen ${\displaystyle p>2}$ ist

${\displaystyle B_{p^{k+1}n}\equiv B_{p^{k}n+1}\ ({\text{mod }}p^{k+1}),}$

für ${\displaystyle p=2}$ gilt die Kongruenz ${\displaystyle ({\text{mod }}p^{k})}$.[7]

Da die Stirling-Zahl ${\displaystyle S(n,k)}$ zweiter Art die Anzahl der ${\displaystyle k}$-Partitionen einer ${\displaystyle n}$-elementigen Menge ist, gilt

${\displaystyle B_{n}=\sum _{k=0}^{n}S(n,k).}$