Title: ADM26 / Kombinatorik

Q: Meta-Regel der Kombinatorik:
Welche vier Fragen müssen immer zuerst beantwortet werden, bevor eine Formel gewählt wird?
A: Antwort:
Vor jeder Rechnung müssen folgende Fragen geklärt werden:
- Ist die Reihenfolge relevant?
- Sind Wiederholungen erlaubt?
- Sind die Objekte unterscheidbar?
- Wird direkt gezählt oder über Bijektion / Inklusion / Schubfach argumentiert?

Q: Wann darf die Summenregel verwendet werden und wie lautet sie?
A: Antwort:
Die Summenregel gilt für disjunkte Fälle.
Sind \( A \cap B = \emptyset \), dann gilt: \[|A \cup B| = |A| + |B|\]
Wichtig: Kein Element darf doppelt gezählt werden.

Q: Wann wird die Produktregel angewendet?
A: Wenn ein Objekt durch aufeinanderfolgende Entscheidungen konstruiert wird.
Besteht ein Objekt aus \( k \) Schritten mit jeweils \( a_1, a_2, \dots, a_k \) Möglichkeiten, dann: \[\text{Anzahl} = a_1 \cdot a_2 \cdot \dots \cdot a_k\]
Typisch: Wörter, Folgen, Positionen, „nacheinander wählen“.

Q: Wie viele Wörter der Länge \( k \) gibt es über einem Alphabet der Größe \( n \)?
A: Antwort:
Für jede Position gibt es \( n \) Möglichkeiten.
\[n^k\]

Q: Wie viele Wörter der Länge \( k \) über einem Alphabet der Größe \( n \) haben keine zwei gleichen Symbole nebeneinander?
A: Antwort:
- Erste Position: \( n \) Möglichkeiten
- Jede weitere Position: \( n-1 \) Möglichkeiten
\[n \cdot (n-1)^{k-1}\]

Q: Variation mit Wiederholung:
Wie viele Möglichkeiten gibt es, eine geordnete Auswahl von \( k \) Elementen aus einer Menge mit \( n \) unterscheidbaren Elementen zu treffen, wenn Wiederholungen erlaubt sind?
A: Gegeben:
- Menge mit \( n \) unterscheidbaren Elementen
- Auswahl von genau \( k \) Elementen
- Reihenfolge ist wichtig
- Wiederholung ist erlaubt
Antwort:
\[n^k\] Begründung:
Jede der \( k \) Positionen kann unabhängig mit einem der \( n \) Elemente besetzt werden (Produktregel). Beispiel (Toto / Zahlenlotterie):
Situation:
Beim klassischen Zahlenlotto („Toto“) wählst du für einen Tippschein eine Folge von genau \( k \) Zahlen.
Jede Zahl wird aus einer festen Menge von \( n \) möglichen Zahlen gewählt.
- Die Reihenfolge der Zahlen ist wichtig (erste Zahl ≠ zweite Zahl)
- Wiederholung ist erlaubt (dieselbe Zahl darf mehrfach vorkommen)
Konkretes Beispiel:
Angenommen:
- \( n = 10 \) (Zahlen 0–9)
- \( k = 6 \) (6-stellige Zahlenfolge)
Dann entspricht ein Tipp genau einer 6-stelligen Zahlenfolge wie z. B.
3 7 3 0 9 1
Anzahl der möglichen Tipps:
\[10^6\]
Begründung (Produktregel):
Für jede der \( k = 6 \) Positionen gibt es unabhängig \( n = 10 \) Wahlmöglichkeiten.
\[\underbrace{10 \cdot 10 \cdot 10 \cdot 10 \cdot 10 \cdot 10}_{6\ \text{Positionen}} = 10^6\]
Prüfungs-Merksatz:
Reihenfolge wichtig + Wiederholung erlaubt ⇒ \[n^k\]

Q: Variation ohne Wiederholung:
Wie viele Möglichkeiten gibt es, eine geordnete Auswahl von \( k \) Elementen aus einer Menge mit \( n \) unterscheidbaren Elementen zu treffen, wenn keine Wiederholungen erlaubt sind?
A: Gegeben:
- Menge mit \( n \) unterscheidbaren Elementen
- Auswahl von genau \( k \) Elementen
- Reihenfolge ist wichtig
- Keine Wiederholung erlaubt
Antwort:
\[\frac{n!}{(n-k)!}\] Begründung:
Für die erste Position gibt es \( n \) Möglichkeiten, für die zweite \( n-1 \), usw. bis \( n-k+1 \).

Q: Kombination ohne Wiederholung:
Wie viele Möglichkeiten gibt es, eine ungeordnete Auswahl von \( k \) Elementen aus einer Menge mit \( n \) unterscheidbaren Elementen zu treffen, wenn keine Wiederholungen erlaubt sind?
A: Gegeben:
- Menge mit \( n \) unterscheidbaren Elementen
- Auswahl von genau \( k \) Elementen
- Reihenfolge ist egal
- Keine Wiederholung erlaubt
Antwort:
\[\binom{n}{k}\] Begründung:
Alle Variationen ohne Wiederholung werden gezählt, aber jede Auswahl wird \( k! \)-fach über die Reihenfolge mehrfach gezählt.

Q: Kombination mit Wiederholung:
Wie viele Möglichkeiten gibt es, eine ungeordnete Auswahl von \( k \) Elementen aus einer Menge mit \( n \) unterscheidbaren Elementen zu treffen, wenn Wiederholungen erlaubt sind?
A: Gegeben:
- Menge mit \( n \) unterscheidbaren Elementen
- Auswahl von genau \( k \) Elementen
- Reihenfolge ist egal
- Wiederholung ist erlaubt
Antwort:
\[\binom{n+k-1}{k}\] Begründung:
Entspricht dem Sterne-und-Balken-Modell: Verteilung von \( k \) identischen Objekten auf \( n \) Kategorien. Formel (mit Fakultäten):
Die Anzahl der Möglichkeiten ist \[\binom{n+k-1}{k} = \frac{(n+k-1)!}{k!\,(n-1)!}\]
Intuition:
Wir wählen \( k \) Elemente aus \( n \) Sorten,
- Reihenfolge egal
- Wiederholung erlaubt
Das ist genau der klassische Sterne-und-Balken-Fall.
Anschauliches Beispiel (Sterne-und-Balken):
Gegeben:
- \( n = 3 \) Sorten (z. B. Äpfel A, Birnen B, Orangen C)
- \( k = 5 \) Früchte insgesamt
Frage:
Auf wie viele Arten kann man 5 Früchte auswählen, wenn man von jeder Sorte beliebig viele nehmen darf und die Reihenfolge egal ist?
Sterne-und-Balken-Darstellung:
Wir verteilen 5 identische Sterne auf 3 Kategorien → 2 Balken:
* * | * | * *
Interpretation:
- 2 Äpfel
- 1 Birne
- 2 Orangen
Berechnung:
\[\binom{n+k-1}{k} = \binom{3+5-1}{5} = \binom{7}{5} = \frac{7!}{5!\,2!} = 21\]
Antwort:
Es gibt 21 verschiedene Auswahlen.
Prüfungs-Merksatz (TU Wien):
Reihenfolge egal + Wiederholung erlaubt ⇒ Kombinationen mit Wiederholung
\[\binom{n+k-1}{k} = \frac{(n+k-1)!}{k!\,(n-1)!}\]

Q: Permutation ohne Wiederholung einer Menge:
Wie viele Möglichkeiten gibt es, alle \( n \) unterscheidbaren Elemente einer Menge vollständig anzuordnen, wenn keine Wiederholungen auftreten?
A: Gegeben:
- Menge mit \( n \) unterscheidbaren Elementen
- Alle Elemente werden verwendet
- Reihenfolge ist wichtig
- Keine Wiederholung
Antwort:
\[n!\] Begründung:
Für die erste Position gibt es \( n \), für die zweite \( n-1 \), usw. bis \( 1 \) Möglichkeit.

Q: Permutation mit Wiederholung:
Wie viele verschiedene Anordnungen gibt es von \( k \) Elementen, wenn davon jeweils \( m_1, m_2, \dots, m_r \) identisch sind und \[m_1 + m_2 + \dots + m_r = k\] gilt?
A: Gegeben:
- Insgesamt \( k \) Positionen
- Mehrere identische Elemente
- Reihenfolge ist wichtig
Antwort:
\[\frac{k!}{m_1! \cdot m_2! \cdots m_r!}\] Begründung:
Alle \( k! \) Anordnungen werden gezählt, aber identische Elemente erzeugen Mehrfachzählungen.

Q: Paarbildung:
Wie viele Möglichkeiten gibt es, \( 2n \) unterscheidbare Personen in \( n \) ungeordnete Paare einzuteilen?
A: Antwort:
- \((2n)!\) Anordnungen
- Division durch \(2^n\): Reihenfolge in Paaren egal
- Division durch \(n!\): Reihenfolge der Paare egal
\[\frac{(2n)!}{2^n \cdot n!}\]

Q: Inklusions-Exklusions-Prinzip:
Wie lautet die allgemeine Siebformel für Mengen \( A_1, \dots, A_n \)?
A: Antwort:
\[\left|\bigcup_{i=1}^n A_i\right| = \sum |A_i| - \sum |A_i \cap A_j| + \sum |A_i \cap A_j \cap A_k| - \dots\]
Merksatz: Vorzeichen wechseln!

Q: Typische Signalwörter in Prüfungen:
Welche Begriffe deuten auf welche Methode hin?
- „oder“ → X
- „mindestens“ → X
- „genau einmal“ → X
- „aufeinanderfolgend“ → X
- „ungeordnet“ → X
A: Antwort:
- „oder“ → Inklusion-Exklusion
- „mindestens“ → Schubfachprinzip
- „genau einmal“ → Position wählen
- „aufeinanderfolgend“ → Produktregel
- „ungeordnet“ → Kombination

Q: Schubfachprinzip:
Was garantiert das Schubfachprinzip und wie wird es typischerweise angewendet?
A: Aussage:
Werden \( n \) Objekte auf \( k \) Fächer verteilt, dann enthält mindestens ein Fach \[\left\lceil \frac{n}{k} \right\rceil\] Objekte.
Intuition:
Wenn man die Objekte möglichst gleichmäßig verteilt, bleibt dennoch mindestens ein Fach mit so vielen Objekten übrig.
Typische Anwendung:
Man zeigt die Existenz eines Objekts mit einer bestimmten Eigenschaft, ohne es explizit anzugeben.
Beispiel (prüfungsnah):
Zeige: Unter \( 53 \) Personen gibt es mindestens \( 3 \) Personen mit demselben Anfangsbuchstaben.
Lösungsidee:
- Objekte: Personen (\( n = 53 \))
- Fächer: Anfangsbuchstaben A–Z (\( k = 26 \))
Da \[\left\lceil \frac{53}{26} \right\rceil = 3\] gibt es mindestens einen Buchstaben, der mindestens dreimal vorkommt.
Wichtig:
Das Schubfachprinzip liefert keine exakte Anzahl, sondern eine Existenzgarantie.

Q: Inklusions-Exklusions-Prinzip (Siebformel):
Wie lautet die allgemeine Formel zur Bestimmung der Größe einer Vereinigung von Mengen?
A: Aussage:
Für endliche Mengen \( A_1, \dots, A_n \) gilt: \[\left|\bigcup_{i=1}^n A_i\right| = \sum |A_i| - \sum |A_i \cap A_j| + \sum |A_i \cap A_j \cap A_k| - \dots\]
Idee:
- Einfaches Addieren zählt Elemente mehrfach
- Diese Mehrfachzählungen werden systematisch korrigiert
- Vorzeichen wechseln ab
Merksatz:
Addieren – Subtrahieren – Addieren – …
Beispiel (klassisch in Prüfungen):
Wie viele Zahlen \( \le 60 \) sind durch \( 2 \) oder \( 3 \) oder \( 5 \) teilbar?
Lösung:
- \(|A_2| = 30\)
- \(|A_3| = 20\)
- \(|A_5| = 12\)
- \(|A_2 \cap A_3| = |A_6| = 10\)
- \(|A_2 \cap A_5| = |A_{10}| = 6\)
- \(|A_3 \cap A_5| = |A_{15}| = 4\)
- \(|A_2 \cap A_3 \cap A_5| = |A_{30}| = 2\)
\[30 + 20 + 12 - 10 - 6 - 4 + 2 = 44\] Typischer Einsatz:
- „oder“-Aussagen
- Teilbarkeitsprobleme
- Zählen mit überlappenden Bedingungen

Q: Schubfachprinzip – typisches Prüfungsbeispiel:
Warum existieren unter \( 12 \) ganzen Zahlen zwei mit durch \( 11 \) teilbarer Differenz?
A: Antwort:
- Objekte: die \( 12 \) gegebenen Zahlen
- Fächer: die \( 11 \) Restklassen modulo \( 11 \)
Da \( 12 > 11 \), liegen mindestens zwei Zahlen in derselben Restklasse modulo \( 11 \).
Deren Differenz ist daher durch \( 11 \) teilbar.