0 Daumen
1,9k Aufrufe

Aufgabe:

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

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

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

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

Avatar von

1 Antwort

0 Daumen

Antwort mit KI erzeugt

Anzahl der surjektiven Funktionen using STIRLING-Zahlen zweiter Art

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

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

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

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

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

Die nn-te BELL-Zahl BnB_{n}

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

Bn=k=0n1(n1k)Bk 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 nn-elementigen Menge, z.B. ein spezielles Element xx. Es gibt BkB_{k} Möglichkeiten, die restlichen kk Elemente zu partitionieren. Das Element xx kann zu jeder dieser existierenden Partitionen kk hinzugefügt werden oder eine neue Partition nur mit xx bilden. Die Anzahl der Wege, n1n-1 Elemente in kk Partitionen zu teilen und dann xx hinzuzufügen, ist genau (n1k)\binom{n-1}{k}, da wir kk Partitionen aus den n1n-1 Elementen auswählen, zu denen xx hinzukommt. Wenn wir über alle möglichen kk von 0 bis n1n-1 summieren, erhalten wir die Gesamtzahl der Partitionen, also BnB_{n}.

Differenzen zwischen den Elementen einer Menge

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

Ein anderes Problem?

Stell deine Frage