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.
