Grundlagen der Kombinatorik

Dieses Cheat Sheet bietet einen Überblick über die Grundlagen der Kombinatorik, einschließlich Permutationen, Variationen, Kombinationen und der Mächtigkeit von Mengen. Es ist für Studierende der Informatik, Medieninformatik und Wirtschaftsinformatik konzipiert.

Core Principles

• Permutationen: Anordnung von n unterscheidbaren Objekten (n!).
• Variationen ohne Wiederholung: Auswahl von k Objekten aus n, Reihenfolge wichtig (n! / (n-k)!).
• Variationen mit Wiederholung: Auswahl von k Objekten aus n, Reihenfolge wichtig, mit Wiederholung (n^k).
• Kombinationen ohne Wiederholung: Auswahl von k Objekten aus n, Reihenfolge unwichtig ((n über k)).
• Kombinationen mit Wiederholung: Auswahl von k Objekten aus n, Reihenfolge unwichtig, mit Wiederholung ((n+k-1 über k)).
• Mächtigkeit von Mengen: Anzahl der Elemente in einer Menge.
• Potenzmenge: Menge aller Teilmengen einer Menge (2^n).
• Inklusions-Exklusions-Prinzip: Methode zur Berechnung der Mächtigkeit von Vereinigungen von Mengen.

Action Steps

• Identifiziere, ob Reihenfolge wichtig ist (Variation/Permutation) oder nicht (Kombination).
• Prüfe, ob Objekte mit oder ohne Wiederholung ausgewählt werden können.
• Bestimme die Gesamtzahl der Objekte (n) und die Anzahl der auszuwählenden Objekte (k).
• Wende die entsprechende Formel an.
• Bei Mengenoperationen: Bestimme die Mächtigkeiten der einzelnen Mengen und ihrer Schnittmengen.
• Nutze das Inklusions-Exklusions-Prinzip für komplexe Vereinigungen.

Formulas

• Permutationen: $n!$
• Variationen ohne Wiederholung: $\frac{n!}{(n-k)!}$
• Variationen mit Wiederholung: $n^k$
• Kombinationen ohne Wiederholung: $\binom{n}{k} = \frac{n!}{k!(n-k)!}$
• Kombinationen mit Wiederholung: $\binom{n+k-1}{k}$
• Mächtigkeit der Potenzmenge: $|\mathcal{P}(A)| = 2^{|A|}$
• Mächtigkeit von Vereinigungen (2 Mengen): $|A \cup B| = |A| + |B| - |A \cap B|$
• Mächtigkeit von Vereinigungen (n Mengen): $|\bigcup_{i=1}^{n} A_i| = \sum_{k=1}^{n} (-1)^{k-1} \sum_{1 \le i_1 < \dots < i_k \le n} |A_{i_1} \cap \dots \cap A_{i_k}|$

Key Terms

• Permutation: Anordnung von Objekten, bei der die Reihenfolge eine Rolle spielt.
• Variation: Auswahl von Objekten, bei der die Reihenfolge eine Rolle spielt.
• Kombination: Auswahl von Objekten, bei der die Reihenfolge keine Rolle spielt.
• Mächtigkeit: Die Anzahl der Elemente in einer Menge.
• Potenzmenge: Die Menge aller möglichen Teilmengen einer gegebenen Menge.
• Disjunkt: Mengen, die keine gemeinsamen Elemente haben.
• Bijektiv: Eine Funktion, die sowohl injektiv als auch surjektiv ist; bildet Elemente eindeutig aufeinander ab.
• Derangement: Eine Permutation, bei der kein Element an seiner ursprünglichen Position bleibt.

Real World Examples

• Lotto '6 aus 49': Kombinationen ohne Wiederholung, da die Reihenfolge der gezogenen Zahlen keine Rolle spielt.
• Formel 1 Siegertreppchen (Top 3): Variationen ohne Wiederholung, da die Reihenfolge (1., 2., 3. Platz) wichtig ist.
• Bundesliga-Tippspiel (9 Spiele, 3 Ausgänge pro Spiel): Variationen mit Wiederholung, da jedes Spiel unabhängig ist und 3 mögliche Ausgänge hat.
• Verteilung von Schokoriegeln an Kinder: Kombinationen mit Wiederholung, wenn die Reihenfolge der Verteilung keine Rolle spielt.
• Bildung von Wörtern aus Buchstaben (z.B. MISSISSIPPI): Permutationen mit nicht unterscheidbaren Objekten (Multinomialkoeffizient).
• Tanzveranstaltung (Partner-Neuzuordnung): Derangement-Problem, wenn niemand seinen ursprünglichen Partner wiederbekommt.

Timeline

• Unbekannt: Entwicklung der Kombinatorik als mathematisches Feld.
• 17. Jahrhundert: Entwicklung des Inklusions-Exklusions-Prinzips (Pascal, Fermat).
• 18. Jahrhundert: Beiträge zur Kombinatorik durch Euler (z.B. Mächtigkeit von Mengen, Potenzmenge).
• 19. Jahrhundert: Weitere Formalisierung und Anwendung in verschiedenen Bereichen.
• 20./21. Jahrhundert: Anwendung der Kombinatorik in Informatik, Statistik und vielen anderen Wissenschaften.

People

• Pierre de Fermat: Mathematiker, trug zur Entwicklung der Kombinatorik bei.
• Blaise Pascal: Mathematiker, entwickelte das Inklusions-Exklusions-Prinzip mit.
• Leonhard Euler: Mathematiker, leistete wichtige Beiträge zur Kombinatorik und Mengenlehre.
• Prof. Dr. Stefan Wenhardt: Dozent für Mathematik 1 an der TH Nürnberg.