Hallo Welt für Fortgeschrittene

Kombinatorik

Sebastian Endres

2016-07-04

Definition Kombinatorik

• Teilgebiet der diskreten Mathematik
• Anzahl der Anordnungen einer Auswahl von Objekten

Motivation

Wie viele verschiedene 9x9 Sudokus gibt es?

Wie viele Arten gibt es, ein "Haus vom Nikolaus" zu zeichnen?

Möglichkeiten simulieren? → langsam

⇒ Anzahlen ausrechnen

Permutation

Anordnung von allen $n$ Elementen einer Menge $\Omega$
($|\Omega| = n$) in bestimmter Reihenfolge

Man unterscheidet:

• ohne Wiederholung
• mit Wiederholung

ohne Wiederholung: Permutation ist bijektive Abbildung einer Menge $\Omega$ auf sich selbst

Permutation ohne Wiederholung

• $n$ aus $n$ Elementen
• ohne Zurücklegen
• Reihenfolge unterscheidbar

$$n!$$

Beispiel

Wie viele Möglichkeiten gibt es, 15 Hallo Welt Vorträge auf 15 Termine zu verteilen?

$15! = 1307674368000$

Permutation mit Wiederholung

• $n$ Elemente
• $r$ Gruppen mit jeweils
  $k_i$ ununterscheidbaren Elemente

$$\frac{n!}{\prod_i^{r}(k_i!)}$$

Beispiel

Wie viele Möglichkeiten gibt es, 15 Hallo Welt Vorträge auf 10 Termine zu verteilen, wobei an 5 Terminen 2 Vorträge gehalten werden?

$\frac{n!}{\prod_i^{r}(k_i!)} = \frac{15!}{(2!)^5 \cdot (1!)^5} = 40864824000$

Vorsicht:

$n$ maliges Ziehen mit Zurücklegen aus einer Menge mit $n$ Elementen mit Beachtung der Reihenfolge

ist nicht Permutation mit Wiederholung

Variation

Spezialform der Permutation

Anordnung von $k$ Elementen einer Menge $\Omega$
($|\Omega| = n$) in bestimmter Reihenfolge

$k \le n$

Man unterscheidet:

• mit Wiederholung (Zurücklegen)
• ohne Wiederholung (Zurücklegen)

Variation ohne Wiederholung

• $k$ aus $n$ Elementen
• ohne Zurücklegen
• Reihenfolge unterscheidbar

$$\frac{n!}{(n-k)!}$$

Beispiel

Wie viele Möglichkeiten gibt es, aus 10 leichten Aufgaben 3 für die nächsten 3 Contests auszuwählen, wobei es nur eine pro Contest gibt?

$$\frac{10!}{(10-3)!} = \frac{10!}{7!} = 10 \cdot 9 \cdot 8 = 720$$

Variation mit Wiederholung

• $k$ aus $n$ Elementen
• mit Zurücklegen
• Reihenfolge unterscheidbar

$$n^{k}$$

Beispiel

Wie viele Möglichkeiten gibt es, aus 10 leichten Aufgaben 3 für die nächsten 3 Contests auszuwählen, wobei es nur eine pro Contest gibt aber gleiche Aufgaben öfters verwendet werden dürfen?

$$10^{3} = 10 \cdot 10 \cdot 10 = 1000$$

Kombination

Teilmenge von $k$ Elementen einer Menge $\Omega$
($|\Omega| = n$)

Man unterscheidet:

• mit Wiederholung
• ohne Wiederholung

$|K| \le |V|$

Kombination ohne Wiederholung

• $k$ aus $n$ Elementen
• ohne Zurücklegen
• Reihenfolge nicht unterscheidbar

$$\binom{n}{k} := \frac{n!}{k! \cdot (n - k)!}$$

Beispiel

Wie viele Möglichkeiten gibt es, 2 Leute aus der 2. Reihe aus zu wählen?

• $n = 3; k = 2 \rightarrow 3 $
• $n = 4; k = 2 \rightarrow 6 $
• $n = 5; k = 2 \rightarrow 10$
• $n = 6; k = 2 \rightarrow 15$
• $n = 7; k = 2 \rightarrow 21$
• $n = 8; k = 2 \rightarrow 28$

Kombination mit Wiederholung

• $k$ aus $n$ Elementen
• mit Zurücklegen
• Reihenfolge nicht unterscheidbar

$$f_n^{k} = \binom{n+k-1}{k} := \frac{(n+k-1)!}{k! \cdot (n - 1)!}$$

Beispiel

Wie viele Möglichkeiten gibt es aus einer Urne mit 3 Kugeln (rot, blau, grün) 2 Kugeln mit Zurücklegen auszuwählen?

$$\binom{3+2-1}{2} = \frac{4!}{2! \cdot 2!} = 6$$

Binomialkoeffizient

• Definition:$$\binom{n}{k} := \frac{n!}{k! \cdot (n - k)!}$$
• Rekursionsfall: $$\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$$
• Basisfälle: $$\binom{n}{n} = \binom{n}{0} = 1; \binom{n}{1} = n$$

Primitive Implementierung:

def binomial_bad(n, k):
    """
    Bad recursive implementation of binomial
    """
    if n == k or k == 0:
        return 1
    elif k == 1:
        return n
    else:
        return binomial(n - 1, k) + binomial(n - 1, k - 1)
            

Großer Aufwand

Bessere Implementierung:

def binomial(n, k):
    """
    Better iterative implementation of binomial
    """
    if k == 0:
        return 1
    elif 2 * k > n:
        return binomial(n, n - k)

    ret = n - k + 1

    for i in range(2, k+1):
        ret *= (n - k + i)
        ret /= i

    return ret
            

$$\mathcal{O}(n)$$

Fibonacci Zahlen

$$f_n := f_{n-1} + f_{n-2}$$

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ...

Implementierung

• Rekursionsfall: $$f_n := f_{n-1} + f_{n-2}$$
• Basisfälle: $$f_0 = 0; f_1 = 1$$

Problem: u.U. sehr Aufwändig

Catalan Zahlen

$$C_n := \frac{1}{n+1} \cdot \binom{2n}{n} = \binom{2n}{n} - \binom{2n}{n+1}$$

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, ...

Implementierung

• Rekursionsfall: $$c_{n+1} := \sum_{k=0}^{n} c_k \cdot c_{n-k}$$
• Basisfall: $$c_0 = 1$$

Iterativ

$\mathcal{O}(n)$ - entrekursiviert - AuD Übung SS2016

def catalan(n):
    """Iterative Catalan calculation"""
    pre = 1
    post = 1
    while n > 0:
        pre *= (4 * (n-1) + 2)
        post *= (n + 1)
        n -= 1
    return pre / post
            

weitere Anwendungen

• Anzahl der Möglichkeiten, ein konvexes n-Eck in Dreiecke zu zerteilen
• Anzahl der Möglichkeiten, wie sich 2n Personen im Kreis paarweise die Hände schütteln können, ohne sich zu überkreuzen
• Anzahl der Möglichkeiten, n Paare von Klammern gültig zu setzen → Code, Tafel
• ...

Stirling Zahlen 1. Art

$$S_{n, k} = \genfrac[]{0pt}{}{n}{k}$$

Anzahl an Möglichkeiten $n$ Elemente in $k$ nicht leere Kreise anzuordnen

Beispiele

$\genfrac[]{0pt}{}{4}{1}$	$\genfrac[]{0pt}{}{3}{2}$

Implementierung

• Rekursionsfall: $$\genfrac[]{0pt}{}{n}{k} := (n-1) \cdot \genfrac[]{0pt}{}{n-1}{k} + \genfrac[]{0pt}{}{n-1}{k-1}$$
• Basisfälle:
• Für $k = n$: $$\genfrac[]{0pt}{}{n}{n} = 1$$
• Für $k = 0 \land n \gt 0$ oder $n \lt k$: $$\genfrac[]{0pt}{}{n}{k} = 0$$

Stirling Zahlen 1. Art - Dreieck

Stirling Zahlen 2. Art

$$\genfrac\{\}{0pt}{}{n}{k}$$

Anzahl an Möglichkeiten, $n$ Elemente in $k$ nicht leere Teilmengen zu teilen

Beispiel

$n = 4; k = 2$

$\genfrac\{\}{0pt}{}{4}{2} = 7$

Implementierung

• Rekursionsfall: $$\genfrac\{\}{0pt}{}{n}{k} := k \cdot \genfrac\{\}{0pt}{}{n-1}{k} + \genfrac\{\}{0pt}{}{n-1}{k-1}$$
• Basisfälle:
  • Für $k = n$: $$\genfrac\{\}{0pt}{}{n}{n} = 1$$
  • Für $k=0 \land n \gt 0$ oder $n \lt k$: $$\genfrac\{\}{0pt}{}{n}{k} = 0$$

Stirling Zahlen 2. Art - Dreieck

Euler Zahlen

$$ E_{n,k} = \genfrac\langle\rangle{0pt}{}{n}{k} $$

Anzahl an möglichen Permutation von $n$ Elementen,
die $k$ absteigende Paare besitzen

Beispiel

Folge: $\{1, 2, 3, 4\}$

Permutationen nach dem Schema $\pi_1 \lt \pi_2 \gt \pi_3 \lt \pi_4$:

$$1324, 1423, 2314, 2413, 3412$$

Permutationen nach dem Schema $\pi_1 \lt \pi_2 \lt \pi_3 \gt \pi_4$:

$$1243, 1342, 2341$$

Permutationen nach dem Schema $\pi_1 \gt \pi_2 \lt \pi_3 \lt \pi_4$:

$$2134, 3124, 4123$$

$$\genfrac\langle\rangle{0pt}{}{4}{2} = 11$$

Implementierung

• Rekursionsfall: $$\genfrac\langle\rangle{0pt}{}{n}{k} := (k+1) \cdot \genfrac\langle\rangle{0pt}{}{n-1}{k} + (n-k) \cdot \genfrac\langle\rangle{0pt}{}{n-1}{k-1}$$
• Basisfälle:
• Für $k = 0$: $$\genfrac\langle\rangle{0pt}{}{n}{0} = 1$$
• Für $k \gt 0$: $$\genfrac\langle\rangle{0pt}{}{0}{k} = 0$$

Es existieren verschiedene Notationen und Definitionen

Euler Dreieck

Integer Partitionen

$$P(n, n)$$

Anzahl an Möglichkeiten, die Zahl $n$ ($n \in \mathbb{N}$) als Summe von positiven Integern zu schreiben

Partitionsfunktion

$$P(n, k)$$

Anzahl der Möglichkeiten, die Zahl $n$ ($n \in \mathbb{N}$) als Summe von $x \le k$ positiven Integern zu schreiben

Beispiele

• $P(4,2)$:
• $4$
• $3+1$
• $2+2$


• $P(4,4)$:
• $4$
• $3+1$
• $2+2$
• $2+1+1$
• $1+1+1+1$

$P(4,4)$ als Grafik

4	=	3 + 1	=	2 + 2	=	2 + 1 + 1	=	1 + 1 + 1 + 1

Implementierung

• Rekursionsfall: $$P(n,k) = P(n-k,k) + P(n,k-1)$$
• Basisfälle:
• Für $n = 0$: $$P(0, k) = 1$$
• Für $k = 0 \land n \gt 0$: $$P(n,0) = 0$$
• Für $n \lt 0$: $$P(n,k) = 0$$

Beispiele

Beispiel 1 - Katzen spielen mit Wolle

n Katzen sitzen in k Kreisen zusammen und Spielen mit Wolle. Dabei geben sie den Knäul solange herum, bis ihn jede teilnehmende Katze einmal hatte und er wieder bei der ersten Katze ist. In jedem Kreis beginnt jeweils die älteste Katze. Beim Weitergeben halten sie jeweils den Faden fest.

Frage 1: Wie viele Möglichkeiten gibt es, dass sich die Katzen gruppieren?

Antwort 1: Stirling Zahlen 2. Art: $$\genfrac\{\}{0pt}{}{n}{k}$$

Frage 2: Wie viele Wege kann der Knäul nehmen?

Antwort 2: Stirling Zahlen 1. Art: $$\genfrac[]{0pt}{}{n}{k}$$

Grundlagen

Zahlenfolgen 1D

Zahlenfolgen 2D

Binom. Koeff.	Stirling 1. Art	Stirling 2. Art	Euler	Int. Part.
$$\binom{n}{k}$$	$$\genfrac[]{0pt}{}{n}{k}$$	$$\genfrac\{\}{0pt}{}{n}{k}$$	$$\genfrac\langle\rangle{0pt}{}{n}{k}$$	$$P(n,n)$$
Teil- gruppe	Zyklen	k Grup- pen	$k \cdot$ "$\lt$"	Sum- men
$\frac{n!}{k! \cdot \left(n-k\right)!}$				$P(n-k, k) +\\ P(n, k-1)$

Allgemeines

• Mit kleinen Zahlen und Beispielen Formel erarbeiten
• Zahlen wachsen schnell ⇒
• Java: BigInteger
• C++: long long
• Python: 😃
• Oft ist Ergebnis modulo $m$ verlangt ⇒ rechtzeitig Modulo anwenden
• naive Rekursive Implementierungen langsam ⇒
  dynamische Programmierung

Danke fürs Zuhören

Jetzt Fragen fragen

Quellen

Bildverweise