{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Kombinatorik\n",
    "\n",
    "Kombinatorik brauchen wir, um ein Verständnis für die Frage zu entwickeln: Wie viele Möglichkeiten gibt es, auf die Mengenelemente, Wörter, Zuordnungen, Kugeln aus Urnen, $\\dots$ kombiniert werden können? "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Grundlegende Aufgabentypen\n",
    "\n",
    "Es gibt 4 verschiedene Aufgabentypen, für die immer die selbe Formel angewendet werden kann:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Folie Aufgabentypen](Folien/07/slide-04.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Beim Zurücklegen stellt man sich die Frage: Kann ich ein Element mehrfach verwenden? Bei Wetten zu Pferderennen macht es zum Beispiel keinen Sinn, zu wetten, dass ein einziges Pferd die 3 ersten Plätze belegt. Es macht auch einen Unterschied, ob man die drei ersten Pferde in der Reihenfolge (Hector-Wendy-Blitz) oder (Blitz-Wendy-Hector) tippt.\n",
    "Genauso kann beim Lotto jede Kugel höchstens ein mal gezogen werden. Deshalb findet hier kein Zurücklegen statt. Die Reihenfolge ist aber egal, die Kugeln werden nach der Ziehung in aufsteigender Reihenfolge sortiert.\n",
    "\n",
    "Beim Toto (11er Wette) geht es darum, 11 Spielen ihr Ergebnis (Heim gewinnt, Heim verliert, unentschieden) zuzuordnen. Natürlich können an einem Spieltag mehrere Spiele unentschieden ausgehen oder von der Heimmannschaft gewonnen werden. Deshalb ist das eine Aufgabe \"mit Zurücklegen\". Die Reihenfolge ist auch wichtig. Schließlich macht es einen Unterschied, ob man z.B. nur das erste Spiel auf dem Tippschein mit \"unentschieden\" bewertet oder nur das letzte.\n",
    "Die Zuordnung des Eisbechers beruht auf der Annahme, dass ein Eisbecher mehrmals die selbe Sorte enthalten kann (2 Kugeln Schoko, 1 Kugel Nuss) und die Reihenfolge der Kugeln im Hörnchen/Becher egal ist. Was lernen wir daraus? Für statistische Modellierungen müssen wir oft vereinfachende Annahmen machen. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Aufgabentyp 1 : *mit* Zurücklegen, *mit* Beachtung der Reihenfolge \n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Folie 6](Folien/07/slide-06.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wie kommt man auf die Formel?\n",
    "$n$ ist die Zahl der Ergebnisse, die wir wetten können: Heimsieg (S), Heimniederlage (N), Unentschieden (U). \n",
    "$k$ ist die Zahl der Spiele, die wir tippen.\n",
    "Wenn wir 1 Spiel tippen, gibt es natürlich 3 mögliche Kombinationen $(S,N,U)$. Also $n^k=3^1=3$.\n",
    "\n",
    "Bei zwei Spielen gibt es $3^2=9$ Möglichkeiten: $\\{(S,S),(S,N),(S,U),(N,S),(N,N),(N,U),(U,S),(U,N),(U,U)\\}$\n",
    "\n",
    "Was ist also mit der Definition auf der Folie gemeint? Wir wählen für eine geordnete Folge von n Spielen jeweils eins der k möglichen Ergebnisse der Spiele aus.\n",
    "\n",
    "Man kann die Kombinationen auch als Menge totaler Funktionen auffassen. Sei $M$ die Menge der Spiele, also im Beispiel $|M|=11$. Sei $E=\\{S,N,U\\}$ die Menge der Ergebnisse. Wie viele totale Funktionen $f : M \\to E$ gibt es? Was ist also $|E^M|$? Richtig: $3^{11}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Aufgabentyp 2: *ohne* Zurücklegen, *mit* Beachtung der Reihenfolge"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Definition Fakultät**: $n!$ beschreibt das Produkt aller Zahlen $1,2,3,\\dots,n$. Per Konvention gilt $0!=1$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Folie 5](Folien/07/slide-08.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Folie 6](Folien/07/slide-10.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Als n! bezeichnet man also das Produkt aller natürlicher Zahlen, die $\\leq n$ sind. Die Fakultätsfunktion wächst stark: \n",
    "$3!=1*2*3=6\\\\4!=1*2*3*4=3!*4=24,\\\\ 5!=120\\\\ 10!=3628800\\\\50! \\approx 3.04*10^{64}$ \n",
    "\n",
    "Es gibt also 120 Möglichkeiten, die Elemente einer Menge mit Mächtigkeit 5 zu ordnen, und die Anzahl der Sortierungen (Permutationen) einer Menge mit 50 Elementen ist eine natürliche Zahl mit über 60 Stellen.\n",
    "\n",
    "<font color = red>  **Für die Knobler:** Warum ist eine <u>Permutation</u>, also eine mögliche Sortierung, eine bijektive Abbildung einer endlichen Menge auf sich selbst? </font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Beispiel von der Folie: Die ersten 3 Plätze beim Pferderennen:** Angenommen, jedes der 10 Pferde kann theoretisch gewinnen (kein Pferd ist gedopt oder von vornherein stark über/unterlegen). Dann gibt es 10 mögliche Anwärter auf den ersten Platz. Wenn ein Pferd den 1. Platz belegt, belegt eins der $10-1=9$ anderen Pferde den zweiten Platz. Eins der 8 übrigen Pferde wird danach den dritten Platz erhalten. \n",
    "\n",
    "Warum kann man $10*9*8$ zusammenkürzen wie auf der Folie? Gehen wir die Umformung \"rückwärts\" durch.\n",
    "\n",
    "$10!=10*9*8*7*6*5*4*3*2*1\\\\\n",
    "(10-3)!=7!=7*6*5*4*3*2*1$\n",
    "\n",
    "Also gilt\n",
    "$\\frac{10!}{(10-3)!}=\\frac{10*9*8*7*6*5*4*3*2*1}{7*6*5*4*3*2*1}$ Die Zahlen, die sowohl im Zähler als auch im Nenner stehen, kürzen sich weg. Übrig bleibt $10*9*8$. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Aufgabentyp 3: *ohne* Zurücklegen *ohne* Beachtung der Reihenfolge"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Folie 7](Folien/07/slide-12.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Anzahl der Lösungen beim Lotto\n",
    "\n",
    "Lotto funktioniert folgender Maßen: Wir wählen $k=6$ Kugeln aus einem Topf mit $n=49$ Kugeln aus, ohne die Reihenfolge der ausgewählten Kugeln zu beachten.\n",
    "\n",
    "Nimm den Kasten aus Folie 6 oben: Es gibt also $\\frac{49!}{(49-6)!}=10\\:068\\:347\\:520$ Möglichkeiten, 6 Kugeln aus den 49 auszuwählen. Ähnlich wie in dem Pferdewettenbeispiel kann man das ausschreiben: $\\frac{49!}{(49-6)!}=49*48*47*46*45*44$. \n",
    "\n",
    "Jetzt beachten wir beim Lotto aber die Reihenfolge, in der die Kugeln gezogen wurden: Die Ziehung $(2,5,7,9,3,11)$ wäre eine andere als die Ziehung $(2,3,5,9,11,7)$. Bei der Berechnung mit Reihenfolge gibt es also immer mehr Kombinationen als bei der Berechnung ohne Reihenfolge! Irgendwie müssen wir also herausrechnen, dass die Ergebnisse mit unterschiedlichen Reihenfolgen zum selben Endergebnis \"zusammenfallen\". In der oben errechneten Anzahl mit Berücksichtigung der Reihenfolge gibt es also immer 720 mögliche Folgen, die gleich sind, wenn die Reihenfolge nicht berücksichtigt wird. Deswegen teilen wir durch die Anzahl möglicher Permutationen: Wie wir oben gesehen haben, gibt es $6!=6*5*4*3*2*1=720$ Möglichkeiten, die 6 gezogenen zu ordnen. Das ist also die Zahl von möglichen Reihenfolgen, in denen die 6 aus 49 gezogen werden können.\n",
    "\n",
    "Das Endergebnis ist also: $\\frac{49!}{(49-6)!}:6!=\\frac{49!}{(49-6)!-6!}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Binomialkoeffizient\n",
    "\n",
    "Weil diese Art der Berechnung in der Kombinatorik so häufig vorkommt, gibt es einen festen Begriff dafür: $\\binom{n}{k}$ heißt Binomialkoeffizient, man spricht \"n über k\". [Hier](07_BinKoEff.ipynb) steht, wie man den Binomialkoeffizenten in Python oder im Browser berechnet. \n",
    "\n",
    "Zusatztipp: Es gilt übrigens für alle $n,k \\in \\mathbb{N}$: $\\binom{n}{k}=\\binom{n}{n-k}$. Zur Übung kann man sich das mit kleinen Werten für $n$ und $k$ ausformulieren und anschaulich machen."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Das Beispiel Skathände\n",
    "\n",
    "funktioniert genauso wie das Lotto-Beispiel. Hier fragt man sich folgendes: Gegeben ein Kartenspiel mit $n=32$ Karten, wie viele Möglichkeiten habe ich, $k=10$ Karten auszuwählen?\n",
    "\n",
    "Es gibt $\\frac{32!}{32-10!}=32*31*30*29*\\dots*23$ Möglichkeiten, 10 Karten aus einem 32er-Stapel unter Berücksichtigung der Reihenfolge zu ziehen. Die Reihenfolge auf der Hand ist aber egal. Deshalb teilen wir durch die Anzahl der Möglichkeiten, auf die das Kartenblatt geordnet werden könnte: $10!$. Das Ergebnis passt in die Formel: $\\binom{32}{10}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Hier ist die Herleitung noch einmal allgemein formuliert:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Folie 8](Folien/07/slide-16.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Aufgabentyp 4:  *mit* Zurücklegen *ohne* Reihenfolge"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Folie 9](Folien/07/slide-18.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Zusammenfassung:\n",
    "\n",
    "![Folie 11](Folien/07/slide-25.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Selbsttest für Kombinatorik](./07_Kombinatorik_Selbsttest.ipynb)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "celltoolbar": "Raw Cell Format",
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}