Stirling Zahlen zweiter Art und Anzahl der surjektiven Funktionen, Bell Zahl (Kombinatorik)

Question

Aufgabe:

Drücken Sie die Anzahl der surjektiven Funktionen $f:\{0,1\}^{n} \rightarrow\{0,1\}^{2}$ mit Hilfe der STIRLING-Zahlen zweiter Art aus.

(b) Wieso gilt $n^{m}=\sum \limits_{k=0}^{m} S_{m, k} \cdot n^{\underline{k}}$ für $n, m \in \mathbb{N}_{+} ?$

(c) Die $n$ -te BELL-Zahl $B_{n}$ gibt die Anzahl der Partitionen einer $n$ -elementigen Grundmenge an; mithin gilt $B_{n}=\sum \limits_{k=0}^{n} S_{n, k}$. Zeigen Sie, dass
$B_{n}=\sum \limits_{k=0}^{n-1}\left(\begin{array}{c} n-1 \\ k \end{array}\right) B_{k}$
für $n \geq 1$ gilt.

(j) Betrachten Sie für eine Menge $\left\{a_{1}, \ldots, a_{n}\right\} \subseteq\{0,1, \ldots, m\}$ mit $a_{1}<a_{2}<\cdots<a_{n}$ alle Differenzen $a_{i}-a_{j}$ mit $i>j$. Wie groß muss $n$ mindestens sein, damit eine Differenz garantiert doppelt vorkommt.

Answer 1

Antwort mit KI erzeugt

Anzahl der surjektiven Funktionen using STIRLING-Zahlen zweiter Art

Eine surjektive Funktion von einer $n$-elementigen Menge $A$ auf eine $2$-elementige Menge $B$ bedeutet, dass jedes Element von $B$ mindestens einmal als Bild unter der Funktion auftreten muss. Die Menge $A$ ist hier $\{0,1\}^n$ und $B$ ist $\{0,1\}^2$, also $|A| = 2^n$ und $|B| = 2$.

Die Anzahl der surjektiven Funktionen kann mit den Stirling-Zahlen zweiter Art $S(n,k)$ ausgedrückt werden, die angeben, wie man eine $n$-elementige Menge in $k$ nicht-leere disjunkte Teilmengen (Blocks) aufteilen kann. Da $|B| = 2$, suchen wir die Anzahl der Möglichkeiten, eine $2^n$-elementige Menge in 2 nicht-leere Teilmengen zu teilen. Diese Anzahl ist durch die Stirling-Zahl zweiter Art $S(2^n, 2)$ gegeben. Zusätzlich muss jede Zuordnung noch auf alle möglichen Anordnungen der Elemente in $B$ abgebildet werden. Da $|B|=2$, gibt es $2!$ mögliche Anordnungen. Daher ist die gesuchte Anzahl der surjektiven Funktionen $2! \cdot S(2^n, 2)$.

Wieso gilt $n^{m} = \sum \limits_{k=0}^{m} S_{m, k} \cdot n^{\underline{k}}$ für $n, m \in \mathbb{N}_{+}$?

Diese Identität erklärt, wie man die Anzahl der Funktionen von einer $m$-elementigen Menge auf eine $n$-elementige Menge ausdrücken kann. Hierbei bezeichnet $n^{\underline{k}}$ das fallende Faktoriell, das definiert ist als $n\cdot(n-1)\cdot(n-2)\cdot...\cdot(n-k+1)$, und $S_{m,k}$ sind die Stirling-Zahlen zweiter Art, die die Anzahl der Möglichkeiten beschreiben, eine $m$-elementige Menge in $k$ nicht-leere Teilmengen zu unterteilen.

Die Gleichung sagt aus, dass wenn man alle möglichen Funktionen von einer $m$-elementigen Menge auf eine $n$-elementige Menge zählen möchte, man alle möglichen Aufteilungen der $m$-Menge in $k$ nicht-leere Teilmengen betrachten muss ($S_{m,k}$) und für jede Aufteilung dann die Anzahl der möglichen Zuordnungen zu den $n$ Elementen zählt ($n^{\underline{k}}$).

Die $n$-te BELL-Zahl $B_{n}$

Die $n$-te Bell-Zahl $B_{n}$ gibt an, wie viele unterschiedliche Möglichkeiten es gibt, eine $n$-elementige Menge in beliebige, nicht-leere, disjunkte Teilmengen zu unterteilen, sprich die Anzahl der Partitionen der Menge. Die Behauptung, dass

$B_{n}=\sum \limits_{k=0}^{n-1}\binom{n-1}{k} B_{k}$

beruht auf der rekursiven Natur der Bell-Zahlen. Um zu zeigen, dass dies gilt, betrachten wir ein Element der $n$-elementigen Menge, z.B. ein spezielles Element $x$. Es gibt $B_{k}$ Möglichkeiten, die restlichen $k$ Elemente zu partitionieren. Das Element $x$ kann zu jeder dieser existierenden Partitionen $k$ hinzugefügt werden oder eine neue Partition nur mit $x$ bilden. Die Anzahl der Wege, $n-1$ Elemente in $k$ Partitionen zu teilen und dann $x$ hinzuzufügen, ist genau $\binom{n-1}{k}$, da wir $k$ Partitionen aus den $n-1$ Elementen auswählen, zu denen $x$ hinzukommt. Wenn wir über alle möglichen $k$ von 0 bis $n-1$ summieren, erhalten wir die Gesamtzahl der Partitionen, also $B_{n}$.

Differenzen zwischen den Elementen einer Menge

Zuletzt, um zu ermitteln, wie groß $n$ mindestens sein muss, um sicherzustellen, dass eine Differenz $a_i-a_j$ (mit $i>j$) mindestens doppelt vorkommt, nutzen wir das Schubfachprinzip (Pigeonhole Principle). Bei einer Menge von $n$ Elementen aus der Menge $\{0,1,\ldots,m\}$, gibt es maximal $m$ verschiedene Differenzen. Um sicherzustellen, dass mindestens eine Differenz doppelt vorkommt, muss $n$ größer als $m+1$ sein, da im schlimmsten Fall die ersten $m+1$ Elemente alle unterschiedliche Differenzen haben können (man denke an die Zahlen 0 bis $m$). Sobald $n=m+2$, ist man garantiert, dass mindestens eine Differenz mindestens zweimal auftritt wegen des Schubfachprinzips.