Dein Lernbereich wird geladen
App wird gestartet …
Dein Lernbereich wird geladen
App wird gestartet …
Zählregeln bestimmen die Zahl möglicher Auswahlen; Inklusion–Exklusion korrigiert Mehrfachzählungen bei überlappenden Mengen.
Ansehen kostenlos · Karteikarten oder Multiple-Choice-Test · übernehmen ab Essential
Formel
n,k und Mengenmächtigkeiten sind nichtnegative ganze Anzahlen; keine physikalische Einheit
| Symbol | Bedeutung | Einheit |
|---|---|---|
| Anzahl verschiedener verfügbarer Elemente | Anzahl | |
| Anzahl ausgewählter Elemente, 0≤k≤n | Anzahl | |
| Anzahl ungeordneter Auswahlen ohne Wiederholung | Anzahl | |
| Endliche Mengen, deren Vereinigung gezählt wird | Menge | |
| |A| | Mächtigkeit einer endlichen Menge A | Anzahl |
\binom{n}{k}=\frac{n!}{k!(n-k)!},\quad |A\cup B|=|A|+|B|-|A\cap B|,\quad |\bigcup_i A_i|=\sum_{\emptyset\ne S\subseteq[n]}(-1)^{|S|+1}|\bigcap_{i\in S}A_i|Die Binomialzahl zählt Auswahlen ohne Reihenfolge und ohne Wiederholung. Bei geordneten Auswahlen ist zusätzlich mit k! zu multiplizieren; mit Wiederholung gilt eine andere Zählregel. Für zwei Mengen zieht |A∩B| die doppelt gezählten Elemente einmal ab. Die allgemeine Inklusion–Exklusion wechselt Vorzeichen nach der Anzahl der gleichzeitig geschnittenen Mengen und gilt für jede endliche Mengenfamilie. Das Curriculum führt Zählen, Permutationen/Kombinationen und Inklusion–Exklusion als diskrete Mathematik; der Lehrtext liefert die Gleichungen.
Die Binomialzahl zählt Auswahlen ohne Reihenfolge und ohne Wiederholung. Bei geordneten Auswahlen ist zusätzlich mit k! zu multiplizieren; mit Wiederholung gilt eine andere Zählregel. Für zwei Mengen zieht |A∩B| die doppelt gezählten Elemente einmal ab. Die allgemeine Inklusion–Exklusion wechselt Vorzeichen nach der Anzahl der gleichzeitig geschnittenen Mengen und gilt für jede endliche Mengenfamilie. Das Curriculum führt Zählen, Permutationen/Kombinationen und Inklusion–Exklusion als diskrete Mathematik; der Lehrtext liefert die Gleichungen.
Zählregeln bestimmen die Zahl möglicher Auswahlen; Inklusion–Exklusion korrigiert Mehrfachzählungen bei überlappenden Mengen.
Anzahl ungeordneter Auswahlen
Gilt ohne Wiederholung; k muss zwischen 0 und n liegen.
Erkläre am Beispiel zu Kombinatorische Zählregeln und Inklusion-Exklusion, welche Eingabegrößen zur gesuchten Ausgabe führen.
Das Beispiel verknüpft konkrete Eingaben mit dem Ergebnis.
Zählregeln bestimmen die Zahl möglicher Auswahlen; Inklusion–Exklusion korrigiert Mehrfachzählungen bei überlappenden Mengen.
Gültig ist die Beziehung nur unter den genannten Voraussetzungen.
Wie viele Dreiergruppen lassen sich aus acht Personen bilden, wenn die Reihenfolge egal ist?
binom(8,3)=8!/(3!·5!)=56.
Die Reihenfolge innerhalb einer Gruppe wird nicht gezählt.
Die Beziehung ohne ihre angegebenen Voraussetzungen auf einen anderen Fall übertragen.
Prüfe vor dem Einsetzen den Gültigkeitsbereich: Die Binomialzahl zählt Auswahlen ohne Reihenfolge und ohne Wiederholung. Bei geordneten Auswahlen ist zusätzlich mit k! zu multiplizieren; mit Wiederholung gilt eine andere Zählregel. Für zwei Mengen zieht |A∩B| die.
Formelcluster
Zählregeln bestimmen die Zahl möglicher Auswahlen; Inklusion–Exklusion korrigiert Mehrfachzählungen bei überlappenden Mengen.
In einer Gruppe kennen 12 Personen Python, 9 Java und 5 beide Sprachen: Mindestens eine Sprache kennen 12+9−5=16 Personen. Zusätzlich gibt es binom(8,3)=8·7·6/(3·2·1)=56 Möglichkeiten, 3 von 8 Personen ohne Reihenfolge auszuwählen. Probe: 8·7·6 geordnete Auswahlen werden je durch 3!=6 Reihenfolgen dargestellt; 336/6=56.
Auswahlmöglichkeiten, überlappende Kategorien, kombinatorische Wahrscheinlichkeiten und endliche Suchräume berechnen.
Eine typische Aufgabe Schritt für Schritt: Kombinatorische Zählregeln und Inklusion-Exklusion (C(n,k)=n!/[k!(n−k)!]; |A∪B|=|A|+|B|−|A∩B|).
Aufgabe
Erkläre am Beispiel zu Kombinatorische Zählregeln und Inklusion-Exklusion, welche Eingabegrößen zur gesuchten Ausgabe führen.
Rechenweg
Das Beispiel verknüpft konkrete Eingaben mit dem Ergebnis.
Zählregeln bestimmen die Zahl möglicher Auswahlen; Inklusion–Exklusion korrigiert Mehrfachzählungen bei überlappenden Mengen.
Gültig ist die Beziehung nur unter den genannten Voraussetzungen.
Aufgabe
Wie viele Dreiergruppen lassen sich aus acht Personen bilden, wenn die Reihenfolge egal ist?
Rechenweg
binom(8,3)=8!/(3!·5!)=56.
Die Reihenfolge innerhalb einer Gruppe wird nicht gezählt.
Der Binomialkoeffizient binom(n,k) zählt, wie viele verschiedene k-elementige Teilmengen aus n unterscheidbaren Elementen gebildet werden können. Die Reihenfolge der Auswahl spielt keine Rolle, und jedes Element darf höchstens einmal vorkommen. Deshalb teilt n! durch k! für die Reihenfolgen innerhalb der ausgewählten Gruppe und durch (n−k)! für die übrigen Elemente. Bei n=8 und k=3 ergeben sich 56 Gruppen. Für eine Anordnung von drei ausgewählten Elementen wäre das Ergebnis dagegen 336. Voraussetzung: endliche Mengen; unterscheide Auswahl mit oder ohne Reihenfolge und Wiederholung.
Frage zuerst, ob zwei Ergebnisse als gleich gelten, wenn nur die Reihenfolge ihrer Elemente vertauscht wird. Bei einem Ausschuss aus drei Personen ist {A,B,C} dieselbe Auswahl wie {C,B,A}; der Binomialkoeffizient passt. Bei einem Code oder einer Sitzordnung sind ABC und CBA verschieden. Ohne Wiederholung gibt es dann n!/(n−k)! geordnete Auswahlen; mit Wiederholung sind es n^k. Eine falsche Reihenfolgeannahme kann das Ergebnis um den Faktor k! verändern. Prüfe diese Entscheidung vor jeder weiteren Multiplikation mit möglichen Fallzahlen. Voraussetzung: endliche Mengen; unterscheide Auswahl mit oder ohne Reihenfolge und Wiederholung.
Beim Addieren von |A| und |B| werden Elemente aus A∩B zweimal gezählt: einmal als Mitglied von A und nochmals als Mitglied von B. Durch einmaliges Subtrahieren des Schnitts bleibt jedes Element der Vereinigung genau einmal übrig. Sind A und B disjunkt, ist der Schnitt null und die einfache Summe genügt. Im Beispiel 12 Python-Kundige, 9 Java-Kundige und 5 mit beiden Kenntnissen ergibt sich 12+9−5=16 Personen mit mindestens einer Sprache. Voraussetzung: endliche Mengen; unterscheide Auswahl mit oder ohne Reihenfolge und Wiederholung.
Bei drei Mengen addierst du zunächst die drei Einzelgrößen, ziehst anschließend die drei paarweisen Schnittmengen ab und addierst den gemeinsamen Dreifachschnitt wieder. So wird jede Person genau einmal gezählt, auch wenn sie in zwei oder drei Mengen liegt. Allgemein wechseln die Vorzeichen mit der Größe des Schnittindex: Einzelmengen plus, Zweierschnitte minus, Dreierschnitte plus. Das Verfahren funktioniert für jede endliche Mengenfamilie, kann bei vielen Mengen aber viele Terme enthalten. Bei vier oder fünf Mengen hilft eine systematische Tabelle, die benötigten Schnitte vollständig zu erfassen. Voraussetzung: endliche Mengen; unterscheide Auswahl mit oder ohne Reihenfolge und Wiederholung.
Die Binomialzahl beschreibt, auf wie viele Arten genau k Erfolge in n unterscheidbaren Versuchen angeordnet werden können. Haben alle Folgen mit k Erfolgen dieselbe Wahrscheinlichkeit p^k(1−p)^(n−k), ergibt Multiplikation mit binom(n,k) die Wahrscheinlichkeit P(X=k). Damit braucht die Binomialverteilung unabhängige Versuche mit konstantem Erfolgsparameter p. Die Zählformel allein ist keine Wahrscheinlichkeit: Erst das probabilistische Modell liefert die Gewichte. Bei Ziehen ohne Zurücklegen ist typischerweise die hypergeometrische Verteilung passender. Ein kleines Baumdiagramm kann die gleich wahrscheinlichen Folgen sichtbar machen, ersetzt aber nicht die Unabhängigkeitsannahme. Voraussetzung: endliche Mengen; unterscheide Auswahl mit oder ohne Reihenfolge und Wiederholung.
Quanta-Prüfungsset
Kuratiertes Prüfungsset für "Kombinatorische Zählregeln und Inklusion-Exklusion":
Frage (Vorderseite)
Welche Formel beschreibt Kombinatorische Zählregeln und Inklusion-Exklusion?
Antwort in deinem Set
Frage (Vorderseite)
Wie stellst du C(n,k)=n!/[k!(n−k)!]; |A∪B|=|A|+|B|−|A∩B| nach Anzahl ungeordneter Auswahlen um?
Antwort in deinem Set
Frage (Vorderseite)
Welcher typische Fehler passiert bei C(n,k)=n!/[k!(n−k)!]; |A∪B|=|A|+|B|−|A∩B|?
Antwort in deinem Set
+ 8 weitere Karten: Einheiten, Variablen, Herleitung, Beispiel, Klausuraufgabe
Das Formelset enthält 11 Karten. Nach der Übernahme kannst du sie prüfen und lernen; deine Bewertungen bestimmen die weiteren Wiederholungen.
Die Liste nennt Fachquellen und weiterführende Literatur. Eine Seiten- oder Abschnittsnummer steht dabei, wenn sie Teil der Literaturangabe ist; es handelt sich nicht um wörtliche Zitate.
Erstelle ein kuratiertes FSRS-Prüfungsset für C(n,k)=n!/[k!(n−k)!]; |A∪B|=|A|+|B|−|A∩B|: Formelabruf, Variablen, Herleitung, Umstellung, Beispiel, typische Fehler und Klausurkontext.
Kuratiertes Formelset · LaTeX · FSRS Spaced Repetition · übernehmen ab Essential