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∣=2n 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
2n-elementige Menge in 2 nicht-leere Teilmengen zu teilen. Diese Anzahl ist durch die Stirling-Zahl zweiter Art
S(2n,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!⋅S(2n,2).
Wieso gilt nm=k=0∑mSm,k⋅nk für n,m∈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
nk das fallende Faktoriell, das definiert ist als
n⋅(n−1)⋅(n−2)⋅...⋅(n−k+1), und
Sm,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 (
Sm,k) und für jede Aufteilung dann die Anzahl der möglichen Zuordnungen zu den
n Elementen zählt (
nk).
Die n-te BELL-Zahl Bn
Die
n-te Bell-Zahl
Bn 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
Bn=k=0∑n−1(kn−1)Bk
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
Bk 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
(kn−1), 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
Bn.
Differenzen zwischen den Elementen einer Menge
Zuletzt, um zu ermitteln, wie groß
n mindestens sein muss, um sicherzustellen, dass eine Differenz
ai−aj (mit
i>j) mindestens doppelt vorkommt, nutzen wir das Schubfachprinzip (Pigeonhole Principle). Bei einer Menge von
n Elementen aus der Menge
{0,1,…,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.