Diskrete Strukturen (Mitschrift) (Nebe): Abzählende Kombinatorik

Aus Infostudium Wiki

Wechseln zu: Navigation, Suche
Back.png Zurück zu Inhaltsverzeichnis Book.png Hoch zu Inhaltsverzeichnis Forward.png Vor zu Graphentheorie


Inhaltsverzeichnis

1) Ziehen von Elementen aus einer Menge

Wie viele Möglichkeiten gibt es, k Objekte aus einer Menge von n Objekten zu "ziehen"?

Diese Frage muss man präzisieren, z.B. aus M = 1,2,3 sollen 2 Elemente gezogen werden:

geordnet
mit Zurücklegen -- S(3,2) (1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)
ohne Zurücklegen -- S0(3,2) (1,2),(1,3),(2,1),(2,3),(3,1),(3,2)
ungeordnet
mit Zurücklegen -- M(3,2) 1,1',1,2',1,3',2,2',2,3',3,3'
ohne Zurücklegen -- M0(3,2) 1,2',1,3',2,3'

Wobei Angaben in geschweiften Klammern mit Apostroph (also {\dots}') Multimengen sind, d.h. Mengen, bei denen Elemente mehrfach vorkommen können. Die S(x,x) und M(x,x) Bezeichnungen werden gleich definiert; siehe auch letzte Tabelle vor (1.2)

(1.1) Definition

Sei k,n \in \mathbb{N} = {0,1,2,\dots}
Merke für diese Vorlesung: \mathbb{N} beinhaltet 0


  1. S(n,k) = \lbrace (a_{1},\dots,a_{k})\ |\ a_{i} \in \lbrace 1,\dots,n\rbrace für i=1,\dots,k\rbrace (Menge aller Folgen, S = "Sequence")
  2. S_{0}(n,k) = \lbrace (a_{1},\dots,a_{k}) \in S(n,k)\ |\ a_{i} \neq a_{j} \mbox{ für } i\neq j \rbrace (injektive Folge)
  3. M_{0}(n,k) = \lbrace M \subseteq \lbrace 1,\dots,n\rbrace \ |\ |M| = k \rbrace ("k-elementige Teilmenge")
  4. M(n,k) = \lbrace f:\lbrace 1,\dots,n\rbrace \to \mathbb{N} \ |\ \sum_{i=1}^{n}{f(i)}=k \rbrace

Beispiel

Sei f eine Abbildung f:\lbrace 1,2,3\rbrace \to \mathbb{N} , so ergibt sich folgende Abbildungstabelle:

1 2 3 bijekt. Abb.
2 0 0 {1,1}'
1 1 0 {1,2}'
\vdots \vdots \vdots \vdots
0 0 2 {3,3}'

Oder für \lbrace 1,1,2,4\rbrace' \in M(4,4) :

1 2 3 4
2 1 0 1

Bemerkung

a) S(n,k) ist die Menge aller Folgen der Länge k mit Einträgen aus \lbrace 1,\dots,n\rbrace (mit Wiederholung, Anordnung ist relevant)
b) S0(n,k) ist die Menge der Folgen der Länge k mit Einträgen aus \lbrace 1,\dots,n\rbrace ohne Wiederholung.

Seien

\mathcal{F}(n,k) :=\lbrace f:\lbrace 1,\dots,k\rbrace \to \lbrace 1,\dots,n\rbrace\rbrace (\mathcal{F} = Menge der Abbildungen)

\mathcal{F}_{0}(n,k):= \lbrace f:\lbrace 1,\dots,k\rbrace \to \lbrace 1,\dots,n\rbrace\rbrace (f injektiv)

\mathcal{F}(n,k) \to S(n,k) f \mapsto (f(1),\dots,f(k)) ist Bijektion mit \mathcal{F}_{0}(n,k) \to S_{0}(n,k)

c)

Die Potenzmenge = \bigcup_{k=0}^{n} M_{0}(n,k) = Pot(\lbrace 1,\dots,n\rbrace) ist Menge aller Teilmengen von \lbrace1,\dots,n\rbrace .

Beispiel: Pot(\lbrace 1,2,3\rbrace) = \lbrace \begin{matrix} \underbrace{\emptyset} \\ {M_{0}(3,0)} \end{matrix},\begin{matrix} \underbrace{\lbrace1\rbrace, \lbrace2\rbrace, \lbrace3\rbrace} \\ {M_{0}(3,1)} \end{matrix},\begin{matrix} \underbrace{\lbrace1,2\rbrace, \lbrace1,3\rbrace, \lbrace2,3\rbrace} \\ {M_{0}(3,2)} \end{matrix},\begin{matrix} \underbrace{\lbrace1,2,3\rbrace} \\ {M_{0}(3,3)} \end{matrix} \rbrace

| Pot({1,2,3}) | = 23 = 8 (Mächtigkeit, Anzahl der enthaltenen Elemente)

Es gilt:

Pot(\lbrace 1,\dots,n\rbrace) \leftrightarrow \mathcal{F}(2,n) (Bijektion)

M \subseteq \lbrace 1,\dots,n\rbrace \mapsto \chi_{n}:\lbrace 1,\dots,n\rbrace \to \lbrace 0,1\rbrace

mit a\mapsto \begin{cases} 0 & a\notin M \\ a & a\in M \end{cases}

χ ist also die charakteristische Funktion, die ein Element auf 0 oder 1 abbildet, wenn es in der Menge enthalten ist (oder nicht).

|Pot(\lbrace 1,\dots,n\rbrace)| = |\mathcal{F}(2,n)| = 2^{n}

d)

f \in M(n,k) repräsentiert eine Multimenge, z.B. M(3,2):

1 2 3
2 0 0 {1,1}'
1 1 0 {1,2}'
1 0 1 {1,3}'
0 1 1 {2,3}'
0 2 0 {2,2}'
0 0 2 {3,3}'

Wir wollten zählen:

geordnet ungeordnet
mit Zurücklegen S(n,k) M(n,k)
ohne Zurücklegen S0(n,k) M0(n,k)

(1.2) Satz ( |S(n,k)|, |S0(n,k)| )

  1. | S(n,k) | = nk
  2. |S_{0}(n,k)|=n \cdot (n-1) \cdot (n-2)\cdot \dots \cdot (n-k+1) = k! \cdot {n \choose k} = \frac{n!}{(n-k)!}


Beweis

a)

(a_{1},\dots,a_{k}) \in S(n,k) Es gibt n Möglichkeiten für a1, dann wird es zurückgelegt, wodurch für a2 wiederum n Möglichkeiten bestehen, usw. bis ak.

Insgesamt: \begin{matrix} \underbrace{n \cdot n \cdot n \cdot \dots n}&=n^{k}\\ {k \mbox{ Faktoren}} \end{matrix} Möglichkeiten

b)

(a_{1},\dots,a_{k}) \in S_{0}(n,k)

Es gibt zuerst n Möglichkeiten für a1.

Weil nicht zurückgelegt wird, bleiben für a2 nur noch n − 1 Möglichkeiten, usw.

Insgesamt: \begin{matrix} \underbrace{n \cdot (n-1) \cdot (n-2) \cdot \dots \cdot (n-k+1)}\\ {k \mbox{ Faktoren}} \end{matrix} Möglichkeiten

(1.3) Definition (Fakultät)

n! = n \cdot (n-1) \cdot (n-2) \dots \cdot 2 \cdot 1

0!: = 1 (neutrales Element der Multiplikation)

Beispiele (Binomialkoeffizient)

{n \choose k} = \frac{n!}{k! (n-k)!} \quad ,n \geq k \in \mathbb{N}

|S_{0}(n,k)| = n \cdot (n-1) \dots (n-k+1) = \frac{n!}{(n-k)!} = k! \cdot {n \choose k}

(1.4) Satz ( |M0(n,k)| )

 |M_{0}(n,k)| = {n \choose k}

Beweis

Sei \varphi: S_{0}(n,k) \to M_{0}(n,k) mit \varphi((a_{1},\dots,a_{k})) = \lbrace a_{1},\dots,a_{k}\rbrace ( \varphi ist im Allgemeinen nicht injektiv, aber surjektiv)

Wie viele Folgen (a_{1},\dots,a_{k}) \in S_{0}(n,k) gibt es mit \varphi((a_{1},\dots,a_{k})) = \lbrace a_{1},\dots,a_{k}\rbrace?

Bestimme die Faser
Lineare Algebra I: Faser = Menge aller Urbilder

\begin{matrix} \varphi^{-1}(\lbrace \lbrace a_{1},\dots, a_{k} \rbrace \rbrace) & = & \lbrace(b_{1},\dots,b_{k}) \mid \varphi((b_{1},\dots,b_{k})) = \lbrace b_{1},\dots,b_{k}\rbrace = \lbrace a_{1},\dots,a_{k}\rbrace \rbrace \\ & = & \lbrace a_{\pi(1)},\dots,a_{\pi(k)} \mid \pi : \lbrace 1,\dots,k\rbrace \to \lbrace 1,\dots,k\rbrace \mbox{ bijektiv} \rbrace \end{matrix} |\varphi^{-1}(\lbrace\lbrace a_{1},\dots,a_{k}\rbrace\rbrace)| = |\mathcal{F}_{0}(k,k) = k!|

Es ist S_{0}(n,k) = \bigcup^{\cdot}_{X\in M_{0}(n,k)} \varphi^{-1}(\lbrace X\rbrace)

\Rightarrow \underbrace{|S_{0}(n,k)|}_{= {n \choose k}k!} = \sum_{X \in M_{0}(n,k)} \underbrace{|\varphi^{-1}(\lbrace X\rbrace)|}_{=k!}

= \sum_{X \in M_{0}(n,k)}{k!} = |M_{0}(n,k)| \cdot k!

\Rightarrow |M_{0}(n,k)| = \frac{|S_{0}(n,k)|}{k!} = {n \choose k}


Beispiel

|M_{0}(4,2)| = \frac{4!}{2!(4-2)!} = \frac{4 \cdot 3 \cdot 2 \cdot 1}{2 \cdot 1 \cdot 2 \cdot 1} = \frac{24}{4} = 6

(1.5) Bemerkung (Identitäten für den Binomialkoeffizienten)

Ein weiteres Beispiel kommt in (16.4) vor

{n \choose k} = \frac{n!}{k!(n-k)!}

  1. {n \choose k} = {n \choose n-k}
  2. k \cdot {n \choose k} = n {n-1 \choose k-1}
  3. {n+1 \choose k} = {n \choose k} +{n \choose k-1}
  4. \sum_{k=0}^{n}{{n \choose k}} = 2^{n} = |Pot(1,\dots,n)|


Beweis

  1. direkt durch nachrechnen oder:

M_{0}(n,k) \leftrightarrow M_{0}(n,n-k) X \mapsto \{1,\dots,n\} \setminus X = \{a \in \{1,\dots,n\} | a \notin X\}

  1. direkt durch nachrechnen oder:

k{n \choose k} = |\begin{matrix}\underbrace{\{(a,X) \mid a \in X \in M_{0\}(n,k)}} \\ {A}\end{matrix}|

n{n-1 \choose k-1} = |\begin{matrix}\underbrace{\{(a,Y) \mid Y \subseteq \{1,\dots,n\} \setminus \{a\} \} } \\ {B}\end{matrix}|

Betrachte Bijektion A \to B: (a,X) \mapsto (a,X\setminus\{a\})

\Rightarrow |A| = |B| \Rightarrow k{n \choose k} = n {n-1 \choose k-1}

  1. direkt durch nachrechnen oder:

M_{0}(n+1,k)\to M_{0}(n,k) \cup M_{0}(n,k-1)

X \subseteq \lbrace 1,\dots,n+1\rbrace \mapsto \begin{cases} X \in M_{0}(n,k) & n+1 \notin X \\ X \setminus \{n+1\} \in M_{0}(n,k-1) & n+1 \in X \end{cases} ist Bijektion

\Rightarrow |M_{0}(n+1,k)| = |M_{0}(n,k)|+|M_{0}(n,k-1)|

\sum_{k=0}^{n}{{n\choose k}} = \sum_{k=0}^{n}{|M_{0}(n,k)|} = \left|\bigcup_{k=0}^{n}{M_{0}(n,k)}\right| = \left|Pot(\lbrace 1,\dots,n\rbrace)\right| \mathcal{F}(2,n) = |S(2,n)| \stackrel{(1.2)}{=} 2^{n}


(1.6) Binomischer Lehrsatz

(x+y)^{n} = \sum_{k=0}^{n}{{n \choose k} x^{k}y^{n-k}}\qquad x,y\in\mathbb{C}


Beweis

(x+y)^{n} = \begin{matrix}\underbrace{(x+y) \cdot (x+y) \cdots (x+y)} \\ {\mbox{n Faktoren} f_{1} \cdots f_{n}}\end{matrix}

Beitrag zu xkyn − k : dazu aus k Faktoren das x auswählen und aus n − k Faktoren das y auswählen:

f_{a_{1}},\dots,f_{a_{k}}

\updownarrow

\lbrace a_{1},\dots,a_{k}\rbrace \subseteq \lbrace 1,\dots,n\rbrace

Koeffizienten von xkyn − k = \sum_{\lbrace a_{1},\dots a_{k}\rbrace \subseteq \lbrace 1,\dots,n\rbrace}{1} = |M_{0}(n,k)|


Folgerung

\sum_{k=0}^{n}{n \choose k} = 2^{n} denn: setze x = y = 1 in (1.6): 2^{n} = (1+1)^{n} = \sum_{k=0}^{n}{{n \choose k}1^{k} 1^{n-k}} = \sum_{k=0}^{n}{{n \choose k}}

(1.7) Folgerung

Jede endliche, n-Elementige Menge hat genauso viele Teilmengen gerader \bindex{Ordnung}, wie ungerader Ordnung. (Ist M eine Menge, so ist | M | die Ordnung von M )

Plausibelmachung

| x | gerade \Leftrightarrow |\begin{matrix}\underbrace{\{1,\dots,n\}\setminus x} \\ {= n-|x|}\end{matrix}| ungerade

Beweis

0 = ((-1)+1)^n \stackrel{(1.6)}{=} \sum_{k=0}^{n}{{n \choose k}(-1)^{k}1^{n-k}}

\Rightarrow \begin{matrix}\underbrace{\sum_{k=0, k gerade}^{n} (n \choose k)} \\ {|\lbrace x \subseteq \lbrace 1,\cdots,n \rbrace \mid |x| gerade \rbrace |}\end{matrix} = \begin{matrix}\underbrace{\sum_{k=0, k ungerade}^{n}{{n \choose k}}} \\ {| \lbrace y \subseteq \lbrace 1,\cdots,n\rbrace \mid |y| ungerade \rbrace |}\end{matrix}


(1.8) Satz (Vandermonde Identität)

{w+m \choose k} = \sum_{l=0}^{k}{{w \choose l}{m \choose k-l}}


Beweis

Hörsaal mit w weiblichen und m männlichen Studenten. Die Anzahl der Möglichkeiten k Studenten aus w + m auszuwählen, ist die Summe der Anzahl der Möglichkeiten, l weibliche und k − l männliche Studenten auszuwählen.


(1.9) Satz ( | M(n,k) | )

|M(n,k)| = {n+k-1\choose k} = {n+k-1\choose n-1}


Beweis

f \in M(n,k) \mbox{ ist } f:\lbrace 1,\dots,n\rbrace \to \mathbb{N} \mbox{, so dass} \sum_{i=1}^{n}{f(i)} = k .


Kodiere f durch \begin{matrix}\underbrace{*\dots *} \\ {f(1)}\end{matrix}|\begin{matrix}\underbrace{*\dots *} \\ {f(2)}\end{matrix}|\begin{matrix}\underbrace{*\dots *} \\ {f(\dots)}\end{matrix}| \begin{matrix}\underbrace{*\dots *} \\ {f(n)}\end{matrix}|

Beispiel

Von „http://wiki.infostudium.de/wiki/Diskrete_Strukturen_(Mitschrift)_(Nebe):_Abz%C3%A4hlende_Kombinatorik“