Partitionen

Eine Partition ${\displaystyle P}$ einer Menge ${\displaystyle M}$ beinhaltet paarweise disjunkte 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 _{x\in P}x=M}$

${\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. Dies ist so, weil alle Aussagen mit dem Allquantor über die Elemente der leeren Menge wahr sind (siehe leere Menge).

Multiplikative Partitionen

Sei ${\displaystyle N}$ eine quadratfreie Zahl, so ist ${\displaystyle n=\omega (N)}$, wobei ${\displaystyle \omega$ :\mathbb {N} \rightarrow \mathbb {N} } die Funktion zur Bestimmung der Anzahl der einzigartigen Primfaktoren ist. Dann ist ${\displaystyle B_{n}}$ wiederum 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\times 1=2\times 15=3\times 10=5\times 6=2\times 3\times 5}$

Definition

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

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

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

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

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

Die Richtigkeit dieser Formel kann durch einen Induktionsbeweis nachgewiesen werden:

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

Für n ≥ 0 gilt:

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

Außerdem gilt:

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

Wenn gilt:

${\displaystyle f(n+1)=\sum _{m=0}^{n}{\binom {n}{m}}f(m)}$ und ${\displaystyle f(0)=1}$

Dann gilt:

${\displaystyle f(n)=B_{n}}$

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

Erzeugende Funktionen

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 so:

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

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

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

Kongruenzsätze

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

${\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,

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

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).}$