Zum Inhalt springen

Themenbuch

Kombinatorik

Strukturen zählen statt Fälle verlieren – vom Baumdiagramm zur Olympiade

VeröffentlichtVersion 1.1.0ca. 365 Seiten

Ein freundlicher Weg vom präzisen Zählobjekt über Summen- und Produktregel bis zu olympiadetauglichen Zählbeweisen.

GrundlagenAufbauFortgeschrittenOlympiade

Was du lernst

  • Endliche Strukturen vollständig und ohne Doppelzählung erfassen.
  • Zählregeln, Symmetrien und Bijektionen begründet einsetzen.
  • Kombinatorische Identitäten durch Zählen beweisen.
  • Olympiadeaufgaben mit mehreren Zählmethoden strategisch lösen.

Rahmen

Lernzeit
31 Std. 36 Min.
Voraussetzungen
Sicherer Umgang mit natürlichen Zahlen · Grundlegende algebraische Umformungen · Bereitschaft, Vollständigkeit und Eindeutigkeit zu begründen

Im Buch suchen

Finde Kapitel, Lernziele und Methoden.

Inhaltsverzeichnis

Lernkarte

  1. 1
  2. 2
    Summenregel und Produktregel

    baut auf den vorherigen Ideen auf

  3. 3
    Fakultät und Permutationen

    baut auf den vorherigen Ideen auf

  4. 4
    Gleiche Elemente und Anordnungsbedingungen

    baut auf den vorherigen Ideen auf

  5. 5
    Ungeordnete Auswahlen und Binomialkoeffizienten

    baut auf den vorherigen Ideen auf

  6. 6
    Pascal-Regel und Teilmengenstrukturen

    baut auf den vorherigen Ideen auf

  7. 7
    Inzidenzen und doppeltes Zählen

    baut auf den vorherigen Ideen auf

  8. 8
    Bijektionen, Gitterwege und Trennstriche

    baut auf den vorherigen Ideen auf

  9. 9
    Ergänzungszählung und genaue Fälle

    baut auf den vorherigen Ideen auf

  10. 10
    Inklusion–Exklusion und Fixpunkte

    baut auf den vorherigen Ideen auf

  11. 11
    Rekursionen und Zustandsmodelle

    baut auf den vorherigen Ideen auf

  12. 12
    Strukturierte Gitterwege und Catalan-Zahlen

    baut auf den vorherigen Ideen auf

  13. 13
    Parität, Restklassen und gewichtete Zählungen

    baut auf den vorherigen Ideen auf

  14. 14
    Schubfach, Invarianten und Extremalprinzip

    baut auf den vorherigen Ideen auf

  15. 15
    Strategiewahl und Beweiswerkstatt

    baut auf den vorherigen Ideen auf

  16. 16
    Kombinatorik-Olympiade: Generalprobe

    baut auf den vorherigen Ideen auf

Zentrale Methoden

Das Zählobjekt präzise definieren

Vor jeder Rechnung festlegen, wann zwei Ergebnisse gleich oder verschieden sind und welche Bedingungen sie erfüllen müssen.

Warum funktioniert sie?

Vor jeder Rechnung festlegen, wann zwei Ergebnisse gleich oder verschieden sind und welche Bedingungen sie erfüllen müssen.

Erkennungssignale

  • Die Aufgabe verwendet Wörter wie Auswahl, Anordnung, Weg, Code oder Team.
  • Es ist unklar, ob Reihenfolge oder Wiederholung eine Rolle spielt.

Vorgehen

  1. 1. Ergebnis beschreiben: Formuliere ein einzelnes vollständiges Ergebnis als Tupel, Menge, Wort oder Weg.
  2. 2. Gleichheit klären: Entscheide, wann zwei Beschreibungen dasselbe Ergebnis meinen.
  3. 3. Bedingungen notieren: Markiere verbotene Wiederholungen, führende Nullen und weitere Einschränkungen.
  4. 4. Erst dann zählen: Wähle eine Darstellung oder Zählregel passend zum definierten Objekt.

Geeignet

  • eine endliche Ergebnismenge vollständig und ohne Doppelzählung erfasst werden soll

Reicht nicht

  • nur ein einzelnes Ergebnis konstruiert und nicht die Anzahl aller Möglichkeiten gesucht wird
Eine systematische Liste erstellen

Kleine Ergebnismengen nach einem festen ersten Merkmal ordnen und innerhalb jeder Gruppe vollständig fortsetzen.

Warum funktioniert sie?

Kleine Ergebnismengen nach einem festen ersten Merkmal ordnen und innerhalb jeder Gruppe vollständig fortsetzen.

Erkennungssignale

  • Die Anzahl ist klein genug zum Auflisten.
  • Eine vollständige Liste soll zugleich als Beweis dienen.

Vorgehen

  1. 1. Ordnung wählen: Sortiere nach erster Stelle, kleinstem Element oder erstem Schritt.
  2. 2. Gruppe abschließen: Liste alle Fortsetzungen eines festen Anfangs auf.
  3. 3. Weitergehen: Wechsle erst danach zum nächsten Anfang.
  4. 4. Vollständigkeit begründen: Erkläre, warum jeder erlaubte Anfang und jede Fortsetzung erfasst wurde.

Geeignet

  • eine endliche Ergebnismenge vollständig und ohne Doppelzählung erfasst werden soll

Reicht nicht

  • nur ein einzelnes Ergebnis konstruiert und nicht die Anzahl aller Möglichkeiten gesucht wird
Tabelle oder Baumdiagramm wählen

Zwei gleichartige Entscheidungen in einer Tabelle und abhängige mehrstufige Entscheidungen in einem Baum darstellen.

Warum funktioniert sie?

Zwei gleichartige Entscheidungen in einer Tabelle und abhängige mehrstufige Entscheidungen in einem Baum darstellen.

Erkennungssignale

  • Zwei Merkmale werden kombiniert oder mehrere Entscheidungen folgen nacheinander.
  • Bedingungen sollen sichtbar gestrichen oder Zweige abgeschnitten werden.

Vorgehen

  1. 1. Stufen bestimmen: Lege fest, welche Entscheidung Zeile, Spalte oder Baumstufe bildet.
  2. 2. Möglichkeiten eintragen: Beschrifte jede Zeile, Spalte oder Kante eindeutig.
  3. 3. Bedingungen anwenden: Markiere ungültige Zellen oder beende verbotene Zweige.
  4. 4. Endergebnisse zählen: Zähle gültige Zellen oder vollständige Wurzel-Blatt-Wege.

Geeignet

  • eine endliche Ergebnismenge vollständig und ohne Doppelzählung erfasst werden soll

Reicht nicht

  • nur ein einzelnes Ergebnis konstruiert und nicht die Anzahl aller Möglichkeiten gesucht wird
Die Summenregel anwenden

Anzahlen disjunkter Fälle addieren, wenn jedes Ergebnis in genau einen Fall gehört.

Warum funktioniert sie?

Anzahlen disjunkter Fälle addieren, wenn jedes Ergebnis in genau einen Fall gehört.

Erkennungssignale

  • Ein Ergebnis entsteht entweder auf die eine oder auf die andere Weise.
  • Eine Bedingung legt natürliche, nicht überlappende Fälle nahe.

Vorgehen

  1. 1. Fälle definieren: Formuliere Fälle mit eindeutigen Grenzen.
  2. 2. Disjunktheit prüfen: Zeige, dass kein Ergebnis in zwei Fällen liegt.
  3. 3. Vollständigkeit prüfen: Zeige, dass jedes erlaubte Ergebnis einen Fall trifft.
  4. 4. Addieren: Addiere die Fallanzahlen und benenne das gezählte Gesamtobjekt.

Geeignet

  • eine endliche Ergebnismenge vollständig und ohne Doppelzählung erfasst werden soll

Reicht nicht

  • nur ein einzelnes Ergebnis konstruiert und nicht die Anzahl aller Möglichkeiten gesucht wird
Die Produktregel anwenden

Anzahlen aufeinanderfolgender Entscheidungen multiplizieren, wenn jeder vollständige Entscheidungsweg genau ein Ergebnis erzeugt.

Warum funktioniert sie?

Anzahlen aufeinanderfolgender Entscheidungen multiplizieren, wenn jeder vollständige Entscheidungsweg genau ein Ergebnis erzeugt.

Erkennungssignale

  • Ein Ergebnis wird in mehreren aufeinanderfolgenden Schritten aufgebaut.
  • Zu jeder Möglichkeit der ersten Stufe gibt es gleich viele oder kontrolliert zählbare Fortsetzungen.

Vorgehen

  1. 1. Stufen festlegen: Zerlege jedes Ergebnis in eine eindeutige Folge von Entscheidungen.
  2. 2. Möglichkeiten zählen: Bestimme die Anzahl pro Stufe unter Beachtung früherer Entscheidungen.
  3. 3. Multiplizieren: Multipliziere die Stufenanzahlen entlang eines vollständigen Weges.
  4. 4. Eindeutigkeit prüfen: Begründe, dass jeder Weg genau ein Ergebnis und jedes Ergebnis genau einen Weg besitzt.

Geeignet

  • eine endliche Ergebnismenge vollständig und ohne Doppelzählung erfasst werden soll

Reicht nicht

  • nur ein einzelnes Ergebnis konstruiert und nicht die Anzahl aller Möglichkeiten gesucht wird
Reihenfolge und Wiederholung prüfen

Vor dem Zählen vier Varianten unterscheiden: geordnet oder ungeordnet sowie mit oder ohne Wiederholung.

Warum funktioniert sie?

Vor dem Zählen vier Varianten unterscheiden: geordnet oder ungeordnet sowie mit oder ohne Wiederholung.

Erkennungssignale

  • Aus Ziffern, Personen, Farben oder Symbolen werden mehrere Plätze besetzt.
  • Vertauschen könnte dasselbe oder ein neues Ergebnis erzeugen.

Vorgehen

  1. 1. Vertauschungstest: Frage, ob das Vertauschen zweier gewählter Elemente das Ergebnis ändert.
  2. 2. Wiederholungstest: Prüfe, ob ein Element mehrfach verwendet werden darf.
  3. 3. Sonderplätze prüfen: Beachte etwa führende Nullen oder eine letzte gerade Ziffer.
  4. 4. Stufenzahlen anpassen: Reduziere nach einer Wahl die nächste Anzahl nur, wenn Wiederholung verboten ist.

Geeignet

  • eine endliche Ergebnismenge vollständig und ohne Doppelzählung erfasst werden soll

Reicht nicht

  • nur ein einzelnes Ergebnis konstruiert und nicht die Anzahl aller Möglichkeiten gesucht wird
Alle verschiedenen Elemente anordnen

Für nn verschiedene Elemente entstehen n!=n(n1)21n!=n(n-1)\cdots2\cdot1 lineare Anordnungen.

Warum funktioniert sie?

Für nn verschiedene Elemente entstehen n!=n(n1)21n!=n(n-1)\cdots2\cdot1 lineare Anordnungen.

Erkennungssignale

  • Alle vorhandenen Elemente werden genau einmal verwendet.
  • Jeder Platz und jede Reihenfolge ist unterscheidbar.

Vorgehen

  1. 1. Ersten Platz wählen: Für den ersten Platz gibt es nn Möglichkeiten.
  2. 2. Anzahlen reduzieren: Ohne Wiederholung bleiben danach n1,n2,,1n-1,n-2,\ldots,1 Möglichkeiten.
  3. 3. Produkt bilden: Multipliziere die Stufenanzahlen zur Fakultät n!n!.
  4. 4. Modell prüfen: Kontrolliere, dass wirklich alle Elemente verschieden und alle Plätze unterscheidbar sind.

Geeignet

  • verschiedene oder teilweise gleiche Elemente auf unterscheidbare Plätze angeordnet werden

Reicht nicht

  • nur die ausgewählte Gruppe zählt und jede Reihenfolge dasselbe Ergebnis beschreibt
Einige Elemente auswählen und anordnen

Für kk geordnete Plätze aus nn verschiedenen Elementen ohne Wiederholung gibt es n(n1)(nk+1)=n!(nk)!n(n-1)\cdots(n-k+1)=\frac{n!}{(n-k)!} Möglichkeiten.

Warum funktioniert sie?

Für kk geordnete Plätze aus nn verschiedenen Elementen ohne Wiederholung gibt es n(n1)(nk+1)=n!(nk)!n(n-1)\cdots(n-k+1)=\frac{n!}{(n-k)!} Möglichkeiten.

Erkennungssignale

  • Nur ein Teil der Elemente wird verwendet.
  • Die gewählten Rollen oder Plätze sind verschieden, etwa Gold, Silber und Bronze.

Vorgehen

  1. 1. Geordnete Plätze nennen: Lege die kk verschiedenen Rollen oder Positionen fest.
  2. 2. Ersten Platz besetzen: Wähle eines von nn Elementen.
  3. 3. Ohne Wiederholung fortsetzen: Für jeden weiteren Platz bleibt ein Element weniger.
  4. 4. Abbrechendes Produkt: Multipliziere genau kk Faktoren.

Geeignet

  • verschiedene oder teilweise gleiche Elemente auf unterscheidbare Plätze angeordnet werden

Reicht nicht

  • nur die ausgewählte Gruppe zählt und jede Reihenfolge dasselbe Ergebnis beschreibt
Relative Reihenfolgen durch Symmetrie zählen

Vertauscht eine eindeutige Operation zwei gleich große Klassen, besitzt jede Klasse genau die Hälfte aller Anordnungen.

Warum funktioniert sie?

Vertauscht eine eindeutige Operation zwei gleich große Klassen, besitzt jede Klasse genau die Hälfte aller Anordnungen.

Erkennungssignale

  • Gefordert ist nur, dass AA vor BB steht.
  • Die Vertauschung von AA und BB ändert keine andere Bedingung.

Vorgehen

  1. 1. Alle Anordnungen zählen: Ignoriere zunächst die relative Reihenfolgebedingung.
  2. 2. Paarbildung definieren: Vertausche in jeder Anordnung genau die beiden betrachteten Elemente.
  3. 3. Klassen vergleichen: In jedem Paar steht einmal AA vor BB und einmal BB vor AA.
  4. 4. Halbieren: Teile die Gesamtzahl durch 2.

Geeignet

  • verschiedene oder teilweise gleiche Elemente auf unterscheidbare Plätze angeordnet werden

Reicht nicht

  • nur die ausgewählte Gruppe zählt und jede Reihenfolge dasselbe Ergebnis beschreibt
Anordnungen mit gleichen Elementen zählen

Sind unter nn Elementen Gruppen von m1,m2,m_1,m_2,\ldots gleichen Elementen, werden die n!n! markierten Anordnungen durch m1!m2!m_1!m_2!\cdots geteilt.

Warum funktioniert sie?

Sind unter nn Elementen Gruppen von m1,m2,m_1,m_2,\ldots gleichen Elementen, werden die n!n! markierten Anordnungen durch m1!m2!m_1!m_2!\cdots geteilt.

Erkennungssignale

  • Buchstaben oder Objekte kommen mehrfach identisch vor.
  • Das Vertauschen gleicher Exemplare erzeugt kein neues sichtbares Ergebnis.

Vorgehen

  1. 1. Vorübergehend markieren: Behandle gleiche Exemplare zunächst als unterscheidbar und zähle n!n!.
  2. 2. Unsichtbare Vertauschungen zählen: Eine Gruppe von mm gleichen Elementen wurde intern m!m!-fach gezählt.
  3. 3. Für jede Gruppe teilen: Dividiere durch das Produkt aller internen Fakultäten.
  4. 4. Kleines Beispiel prüfen: Kontrolliere die Formel an einer kurzen vollständigen Liste.

Geeignet

  • verschiedene oder teilweise gleiche Elemente auf unterscheidbare Plätze angeordnet werden

Reicht nicht

  • nur die ausgewählte Gruppe zählt und jede Reihenfolge dasselbe Ergebnis beschreibt
Blöcke und Lücken für Nachbarschaft nutzen

Elemente, die zusammenstehen müssen, werden als Block behandelt; Elemente, die getrennt bleiben sollen, werden in Lücken einer Grundanordnung gesetzt.

Warum funktioniert sie?

Elemente, die zusammenstehen müssen, werden als Block behandelt; Elemente, die getrennt bleiben sollen, werden in Lücken einer Grundanordnung gesetzt.

Erkennungssignale

  • Bestimmte Personen oder Objekte müssen nebeneinander stehen.
  • Gleiche Typen sollen sich abwechseln oder dürfen nicht benachbart sein.

Vorgehen

  1. 1. Bedingung übersetzen: Entscheide zwischen Block für Nähe und Lücken für Trennung.
  2. 2. Äußere Einheiten anordnen: Zähle Block oder Grundelemente als Einheiten.
  3. 3. Innere Möglichkeiten zählen: Berücksichtige Blockreihenfolgen oder die Auswahl der Lücken.
  4. 4. Produkte verbinden: Multipliziere äußere und innere Entscheidungen und prüfe Eindeutigkeit.

Geeignet

  • verschiedene oder teilweise gleiche Elemente auf unterscheidbare Plätze angeordnet werden

Reicht nicht

  • nur die ausgewählte Gruppe zählt und jede Reihenfolge dasselbe Ergebnis beschreibt
Anordnungen am Kreis zählen

Bei Sitzordnungen ohne ausgezeichneten Startplatz gelten Rotationen als gleich; durch Fixieren einer Person bleiben (n1)!(n-1)! Kreis-Anordnungen.

Warum funktioniert sie?

Bei Sitzordnungen ohne ausgezeichneten Startplatz gelten Rotationen als gleich; durch Fixieren einer Person bleiben (n1)!(n-1)! Kreis-Anordnungen.

Erkennungssignale

  • Die Plätze liegen an einem runden Tisch.
  • Nur Nachbarschaften und zyklische Reihenfolge, nicht die absolute Position, sind wichtig.

Vorgehen

  1. 1. Gleichheit klären: Prüfe, dass gedrehte Sitzpläne als gleich gelten, Spiegelungen aber verschieden bleiben.
  2. 2. Eine Person fixieren: Setze eine ausgewählte Person auf einen gedachten Referenzplatz.
  3. 3. Rest linear anordnen: Ordne die übrigen n1n-1 Personen relativ zu ihr.
  4. 4. Bedingungen integrieren: Nutze bei Nachbarschaften zusätzlich Block- oder Ergänzungszählung.

Geeignet

  • verschiedene oder teilweise gleiche Elemente auf unterscheidbare Plätze angeordnet werden

Reicht nicht

  • nur die ausgewählte Gruppe zählt und jede Reihenfolge dasselbe Ergebnis beschreibt
Eine ungeordnete Auswahl mit dem Binomialkoeffizienten zählen

Die Zahl der kk-elementigen Teilmengen einer nn-elementigen Menge ist (nk)=n!k!(nk)!\binom nk=\frac{n!}{k!(n-k)!}.

Warum funktioniert sie?

Die Zahl der kk-elementigen Teilmengen einer nn-elementigen Menge ist (nk)=n!k!(nk)!\binom nk=\frac{n!}{k!(n-k)!}.

Erkennungssignale

  • Es wird ein Team, Ausschuss oder eine Teilmenge fester Größe gewählt.
  • Innerhalb der Auswahl gibt es keine Rollen.

Vorgehen

  1. 1. Modell prüfen: Kläre, dass genau kk verschiedene Elemente aus nn gewählt werden und die Reihenfolge unwichtig ist.
  2. 2. Kleinen Parameter wählen: Nutze gegebenenfalls (nk)=(nnk)\binom nk=\binom n{n-k}.
  3. 3. Produkt kürzen: Berechne mit kk Faktoren im Zähler und k!k! im Nenner.
  4. 4. Bedingungen prüfen: Kontrolliere Pflicht- und Ausschlusselemente vor dem Einsetzen.

Geeignet

  • eine ungeordnete Auswahl oder eine äquivalente Teilmengenstruktur gezählt wird

Reicht nicht

  • Rollen oder Positionen innerhalb der Auswahl unterscheidbar sind
Geordnete Auswahlen zu Gruppen entordnen

Zähle zunächst geordnete kk-Tupel und teile durch k!k!, weil jedes ungeordnete Team in genau k!k! Reihenfolgen erscheint.

Warum funktioniert sie?

Zähle zunächst geordnete kk-Tupel und teile durch k!k!, weil jedes ungeordnete Team in genau k!k! Reihenfolgen erscheint.

Erkennungssignale

  • Die geordnete Auswahl ist leicht zu zählen.
  • Jede Gruppe besitzt gleich viele interne Reihenfolgen.

Vorgehen

  1. 1. Geordnet zählen: Bestimme n(n1)(nk+1)n(n-1)\cdots(n-k+1).
  2. 2. Mehrfachheit bestimmen: Jede kk-Gruppe wird durch ihre k!k! Reihenfolgen beschrieben.
  3. 3. Teilen: Dividiere die geordnete Anzahl durch k!k!.
  4. 4. Konstante Mehrfachheit begründen: Erkläre, warum wirklich jede Gruppe gleich oft gezählt wurde.

Geeignet

  • eine ungeordnete Auswahl oder eine äquivalente Teilmengenstruktur gezählt wird

Reicht nicht

  • Rollen oder Positionen innerhalb der Auswahl unterscheidbar sind
Ausgewählte und nicht ausgewählte Elemente vertauschen

Jede kk-Auswahl bestimmt eindeutig ihre Ergänzung mit nkn-k Elementen; daher gilt (nk)=(nnk)\binom nk=\binom n{n-k}.

Warum funktioniert sie?

Jede kk-Auswahl bestimmt eindeutig ihre Ergänzung mit nkn-k Elementen; daher gilt (nk)=(nnk)\binom nk=\binom n{n-k}.

Erkennungssignale

  • Es ist deutlich kürzer, die ausgeschlossenen statt der gewählten Elemente festzulegen.
  • Die beiden Auswahlgrößen kk und nkn-k treten symmetrisch auf.

Vorgehen

  1. 1. Grundmenge nennen: Fixiere die Menge aller nn Elemente.
  2. 2. Ergänzung bilden: Ordne jeder Auswahl die Menge der nicht gewählten Elemente zu.
  3. 3. Umkehrbarkeit zeigen: Aus der Ergänzung lässt sich die ursprüngliche Auswahl eindeutig zurückgewinnen.
  4. 4. Kleinere Seite zählen: Verwende den günstigeren der Parameter kk und nkn-k.

Geeignet

  • eine ungeordnete Auswahl oder eine äquivalente Teilmengenstruktur gezählt wird

Reicht nicht

  • Rollen oder Positionen innerhalb der Auswahl unterscheidbar sind
Die Pascal-Regel durch ein festes Element herleiten

Teile alle kk-Auswahlen danach, ob ein festes Element enthalten ist: (nk)=(n1k1)+(n1k)\binom nk=\binom{n-1}{k-1}+\binom{n-1}k.

Warum funktioniert sie?

Teile alle kk-Auswahlen danach, ob ein festes Element enthalten ist: (nk)=(n1k1)+(n1k)\binom nk=\binom{n-1}{k-1}+\binom{n-1}k.

Erkennungssignale

  • Ein bestimmtes Element kann enthalten oder nicht enthalten sein.
  • Benachbarte Binomialkoeffizienten sollen addiert werden.

Vorgehen

  1. 1. Element fixieren: Wähle ein bestimmtes Element aa der Grundmenge.
  2. 2. Enthalten-Fall: Ist aa gewählt, fehlen noch k1k-1 aus n1n-1.
  3. 3. Nicht-enthalten-Fall: Ist aa nicht gewählt, werden alle kk aus den übrigen n1n-1 gewählt.
  4. 4. Disjunkt addieren: Die beiden Fälle sind disjunkt und vollständig.

Geeignet

  • eine ungeordnete Auswahl oder eine äquivalente Teilmengenstruktur gezählt wird

Reicht nicht

  • Rollen oder Positionen innerhalb der Auswahl unterscheidbar sind
Pflicht- und Ausschlusselemente zuerst behandeln

Pflichtelemente werden vorab aufgenommen und verbotene Elemente aus der Grundmenge entfernt; erst danach wird der verbleibende Binomialkoeffizient gebildet.

Warum funktioniert sie?

Pflichtelemente werden vorab aufgenommen und verbotene Elemente aus der Grundmenge entfernt; erst danach wird der verbleibende Binomialkoeffizient gebildet.

Erkennungssignale

  • Eine bestimmte Person muss oder darf nicht zur Gruppe gehören.
  • Mehrere ausgezeichnete Elemente erzeugen klare Fälle.

Vorgehen

  1. 1. Pflicht aufnehmen: Reduziere Auswahlgröße und verfügbare Menge um jedes bereits gewählte Element.
  2. 2. Verbotenes entfernen: Entferne ausgeschlossene Elemente nur aus der verfügbaren Menge.
  3. 3. Verbleibende Auswahl zählen: Verwende den passenden Binomialkoeffizienten.
  4. 4. Mehrere Fälle addieren: Falls nötig, zerlege nach der Zahl ausgezeichneter gewählter Elemente.

Geeignet

  • eine ungeordnete Auswahl oder eine äquivalente Teilmengenstruktur gezählt wird

Reicht nicht

  • Rollen oder Positionen innerhalb der Auswahl unterscheidbar sind
Teilmengen als Binärwörter kodieren

Für jedes Element entscheidet ein Bit über enthalten oder nicht enthalten; dadurch entsprechen die 2n2^n Binärwörter bijektiv allen Teilmengen.

Warum funktioniert sie?

Für jedes Element entscheidet ein Bit über enthalten oder nicht enthalten; dadurch entsprechen die 2n2^n Binärwörter bijektiv allen Teilmengen.

Erkennungssignale

  • Teilmengen beliebiger Größe werden gezählt.
  • Binärfolgen mit einer festen Zahl von Einsen treten auf.

Vorgehen

  1. 1. Elemente ordnen: Gib den nn Elementen feste Positionen.
  2. 2. Bits setzen: Schreibe 1 für enthalten und 0 für nicht enthalten.
  3. 3. Bijektion prüfen: Jede Teilmenge liefert genau ein Wort und jedes Wort genau eine Teilmenge.
  4. 4. Bedingung übersetzen: Eine Auswahlgröße kk bedeutet genau kk Einsen.

Geeignet

  • eine ungeordnete Auswahl oder eine äquivalente Teilmengenstruktur gezählt wird

Reicht nicht

  • Rollen oder Positionen innerhalb der Auswahl unterscheidbar sind
Inzidenzen doppelt zählen

Paare aus zwei Objektarten einmal nach der linken und einmal nach der rechten Komponente gruppieren.

Warum funktioniert sie?

Paare aus zwei Objektarten einmal nach der linken und einmal nach der rechten Komponente gruppieren.

Erkennungssignale

  • Dieselben Objekte besitzen zwei natürliche Beschreibungen.
  • Eine komplizierte Objektklasse lässt sich eindeutig in eine bekannte übersetzen.

Vorgehen

  1. 1. Objektmenge definieren: Lege exakt fest, welche Paare, Markierungen oder Strukturen gezählt werden.
  2. 2. Erste Beschreibung: Zähle nach einem natürlichen ersten Merkmal.
  3. 3. Zweite Beschreibung: Gruppiere dieselben Objekte anders oder kodiere sie um.
  4. 4. Eindeutigkeit sichern: Begründe Vollständigkeit, Eindeutigkeit und gegebenenfalls die Umkehrabbildung.

Geeignet

  • eine Gleichheit von Anzahlen oder eine strukturelle Identität bewiesen werden soll

Reicht nicht

  • die Zuordnung nicht eindeutig oder nicht umkehrbar ist
Kantenenden und Grade zählen

Jede Kante trägt genau zwei Enden zur Summe aller Grade bei; daher ist die Gradsumme doppelt so groß wie die Kantenzahl.

Warum funktioniert sie?

Jede Kante trägt genau zwei Enden zur Summe aller Grade bei; daher ist die Gradsumme doppelt so groß wie die Kantenzahl.

Erkennungssignale

  • Dieselben Objekte besitzen zwei natürliche Beschreibungen.
  • Eine komplizierte Objektklasse lässt sich eindeutig in eine bekannte übersetzen.

Vorgehen

  1. 1. Objektmenge definieren: Lege exakt fest, welche Paare, Markierungen oder Strukturen gezählt werden.
  2. 2. Erste Beschreibung: Zähle nach einem natürlichen ersten Merkmal.
  3. 3. Zweite Beschreibung: Gruppiere dieselben Objekte anders oder kodiere sie um.
  4. 4. Eindeutigkeit sichern: Begründe Vollständigkeit, Eindeutigkeit und gegebenenfalls die Umkehrabbildung.

Geeignet

  • eine Gleichheit von Anzahlen oder eine strukturelle Identität bewiesen werden soll

Reicht nicht

  • die Zuordnung nicht eindeutig oder nicht umkehrbar ist
Auswahlen mit einem markierten Element zählen

Paare aus Auswahl und ausgezeichnetem Mitglied nach der Auswahl oder nach dem markierten Element gruppieren.

Warum funktioniert sie?

Paare aus Auswahl und ausgezeichnetem Mitglied nach der Auswahl oder nach dem markierten Element gruppieren.

Erkennungssignale

  • Dieselben Objekte besitzen zwei natürliche Beschreibungen.
  • Eine komplizierte Objektklasse lässt sich eindeutig in eine bekannte übersetzen.

Vorgehen

  1. 1. Objektmenge definieren: Lege exakt fest, welche Paare, Markierungen oder Strukturen gezählt werden.
  2. 2. Erste Beschreibung: Zähle nach einem natürlichen ersten Merkmal.
  3. 3. Zweite Beschreibung: Gruppiere dieselben Objekte anders oder kodiere sie um.
  4. 4. Eindeutigkeit sichern: Begründe Vollständigkeit, Eindeutigkeit und gegebenenfalls die Umkehrabbildung.

Geeignet

  • eine Gleichheit von Anzahlen oder eine strukturelle Identität bewiesen werden soll

Reicht nicht

  • die Zuordnung nicht eindeutig oder nicht umkehrbar ist
Eine explizite Bijektion konstruieren

Jedes Objekt der ersten Menge durch eine eindeutige, umkehrbare Regel in genau ein Objekt der zweiten Menge übersetzen.

Warum funktioniert sie?

Jedes Objekt der ersten Menge durch eine eindeutige, umkehrbare Regel in genau ein Objekt der zweiten Menge übersetzen.

Erkennungssignale

  • Dieselben Objekte besitzen zwei natürliche Beschreibungen.
  • Eine komplizierte Objektklasse lässt sich eindeutig in eine bekannte übersetzen.

Vorgehen

  1. 1. Objektmenge definieren: Lege exakt fest, welche Paare, Markierungen oder Strukturen gezählt werden.
  2. 2. Erste Beschreibung: Zähle nach einem natürlichen ersten Merkmal.
  3. 3. Zweite Beschreibung: Gruppiere dieselben Objekte anders oder kodiere sie um.
  4. 4. Eindeutigkeit sichern: Begründe Vollständigkeit, Eindeutigkeit und gegebenenfalls die Umkehrabbildung.

Geeignet

  • eine Gleichheit von Anzahlen oder eine strukturelle Identität bewiesen werden soll

Reicht nicht

  • die Zuordnung nicht eindeutig oder nicht umkehrbar ist
Summen mit Trennstrichen kodieren

Einheiten als Sterne und Aufteilungen als Trennstriche schreiben, sodass Lösungen einer Summe zu Zeichenfolgen werden.

Warum funktioniert sie?

Einheiten als Sterne und Aufteilungen als Trennstriche schreiben, sodass Lösungen einer Summe zu Zeichenfolgen werden.

Erkennungssignale

  • Dieselben Objekte besitzen zwei natürliche Beschreibungen.
  • Eine komplizierte Objektklasse lässt sich eindeutig in eine bekannte übersetzen.

Vorgehen

  1. 1. Objektmenge definieren: Lege exakt fest, welche Paare, Markierungen oder Strukturen gezählt werden.
  2. 2. Erste Beschreibung: Zähle nach einem natürlichen ersten Merkmal.
  3. 3. Zweite Beschreibung: Gruppiere dieselben Objekte anders oder kodiere sie um.
  4. 4. Eindeutigkeit sichern: Begründe Vollständigkeit, Eindeutigkeit und gegebenenfalls die Umkehrabbildung.

Geeignet

  • eine Gleichheit von Anzahlen oder eine strukturelle Identität bewiesen werden soll

Reicht nicht

  • die Zuordnung nicht eindeutig oder nicht umkehrbar ist
Über die Gegenmenge zählen

Statt alle erlaubten Objekte direkt zu zerlegen, von der leicht zählbaren Grundmenge die eindeutig beschriebene Gegenmenge abziehen.

Warum funktioniert sie?

Statt alle erlaubten Objekte direkt zu zerlegen, von der leicht zählbaren Grundmenge die eindeutig beschriebene Gegenmenge abziehen.

Erkennungssignale

  • Die Formulierung enthält „mindestens ein“, „nicht alle“ oder „mit Wiederholung“.
  • Die verbotene Gegenbedingung ist deutlich einfacher als die erlaubte Bedingung.

Vorgehen

  1. 1. Grundmenge definieren: Zähle alle Objekte ohne die schwierige Bedingung.
  2. 2. Gegenereignis formulieren: Negiere die Bedingung logisch korrekt.
  3. 3. Gegenmenge zählen: Zähle jedes verbotene Objekt genau einmal.
  4. 4. Subtrahieren: Berechne UAc|U|-|A^c| und prüfe die Randfälle.

Geeignet

  • direktes Zählen durch überlappende oder schwer beschreibbare Bedingungen unübersichtlich wird

Reicht nicht

  • die erlaubten Fälle bereits disjunkt und unmittelbar zählbar sind
Mindestens-Bedingungen in genaue Fälle zerlegen

Nach der exakten Zahl ausgezeichneter Elemente in disjunkte Fälle zerlegen und deren Anzahlen addieren.

Warum funktioniert sie?

Nach der exakten Zahl ausgezeichneter Elemente in disjunkte Fälle zerlegen und deren Anzahlen addieren.

Erkennungssignale

  • Die Bedingung lautet „mindestens“, „höchstens“ oder „genau“.
  • Nur wenige mögliche Anzahlen eines ausgezeichneten Typs treten auf.

Vorgehen

  1. 1. Zählparameter wählen: Bestimme, welche Anzahl die Fälle unterscheidet.
  2. 2. Zulässige Werte auflisten: Nenne jeden möglichen Wert im Definitionsbereich.
  3. 3. Jeden Fall zählen: Multipliziere unabhängige Auswahlen innerhalb des Falls.
  4. 4. Disjunkt addieren: Begründe, dass jedes Objekt genau einen Fall trifft.

Geeignet

  • direktes Zählen durch überlappende oder schwer beschreibbare Bedingungen unübersichtlich wird

Reicht nicht

  • die erlaubten Fälle bereits disjunkt und unmittelbar zählbar sind
Zwei überlappende Mengen vereinigen

Bei AB|A\cup B| die Einzelmengen addieren und ihre doppelt gezählte Schnittmenge einmal abziehen.

Warum funktioniert sie?

Bei AB|A\cup B| die Einzelmengen addieren und ihre doppelt gezählte Schnittmenge einmal abziehen.

Erkennungssignale

  • Objekte dürfen Eigenschaft A oder Eigenschaft B oder beide besitzen.
  • Zwei natürliche Fälle überschneiden sich.

Vorgehen

  1. 1. Mengen definieren: Formuliere die beiden Eigenschaften als Mengen AA und BB.
  2. 2. Einzelmengen zählen: Bestimme A|A| und B|B|.
  3. 3. Schnitt zählen: Bestimme die Objekte mit beiden Eigenschaften.
  4. 4. Korrigieren: Verwende AB=A+BAB|A\cup B|=|A|+|B|-|A\cap B|.

Geeignet

  • direktes Zählen durch überlappende oder schwer beschreibbare Bedingungen unübersichtlich wird

Reicht nicht

  • die erlaubten Fälle bereits disjunkt und unmittelbar zählbar sind
Drei überlappende Mengen korrigieren

Einzelmengen addieren, paarweise Schnitte abziehen und den dreifachen Schnitt wieder hinzufügen.

Warum funktioniert sie?

Einzelmengen addieren, paarweise Schnitte abziehen und den dreifachen Schnitt wieder hinzufügen.

Erkennungssignale

  • Drei Eigenschaften dürfen gleichzeitig auftreten.
  • Paarweise Korrekturen entfernen Objekte im Dreifachschnitt zu oft.

Vorgehen

  1. 1. Einzelmengen addieren: Beginne mit A+B+C|A|+|B|+|C|.
  2. 2. Paarschnitte abziehen: Subtrahiere die drei paarweisen Überschneidungen.
  3. 3. Dreifachschnitt prüfen: Er wurde dreimal addiert und dreimal abgezogen.
  4. 4. Einmal hinzufügen: Addiere ABC|A\cap B\cap C|.

Geeignet

  • direktes Zählen durch überlappende oder schwer beschreibbare Bedingungen unübersichtlich wird

Reicht nicht

  • die erlaubten Fälle bereits disjunkt und unmittelbar zählbar sind
Verbotene Fixpunkte mit Ein- und Ausschluss zählen

Für jede verbotene Position eine Fehlermenge definieren und deren Vereinigungsgröße durch alternierendes Addieren und Subtrahieren bestimmen.

Warum funktioniert sie?

Für jede verbotene Position eine Fehlermenge definieren und deren Vereinigungsgröße durch alternierendes Addieren und Subtrahieren bestimmen.

Erkennungssignale

  • Elemente dürfen nicht auf ihre ursprüngliche oder jeweils verbotene Position.
  • Mehrere Positionsverstöße können gleichzeitig auftreten.

Vorgehen

  1. 1. Fehlermengen definieren: AiA_i enthält alle Anordnungen mit Verstoß an Position ii.
  2. 2. Schnitte zählen: Bei jj festgelegten Fixpunkten bleiben (nj)!(n-j)! Anordnungen.
  3. 3. Vereinigung berechnen: Nutze die alternierende Inklusion–Exklusion-Summe.
  4. 4. Von allen abziehen: Die gesuchten Anordnungen liegen außerhalb aller Fehlermengen.

Geeignet

  • direktes Zählen durch überlappende oder schwer beschreibbare Bedingungen unübersichtlich wird

Reicht nicht

  • die erlaubten Fälle bereits disjunkt und unmittelbar zählbar sind
Nichtleere Klassen über fehlende Klassen zählen

Alle Zuordnungen zählen und diejenigen ausschließen, bei denen mindestens eine Zielklasse leer bleibt.

Warum funktioniert sie?

Alle Zuordnungen zählen und diejenigen ausschließen, bei denen mindestens eine Zielklasse leer bleibt.

Erkennungssignale

  • Jedes Objekt wird einer beschrifteten Klasse zugeordnet.
  • Jede Klasse soll mindestens ein Objekt erhalten.

Vorgehen

  1. 1. Alle Zuordnungen: Bei mm Klassen und nn Objekten gibt es mnm^n Funktionen.
  2. 2. Fehlende Klasse definieren: Für jede Zielklasse bilde die Menge der Zuordnungen, die sie nicht benutzen.
  3. 3. Überschneidungen korrigieren: Nutze Ein- und Ausschluss für mehrere fehlende Klassen.
  4. 4. Surjektionen erhalten: Entferne die Vereinigungsmenge der Fehlfälle.

Geeignet

  • direktes Zählen durch überlappende oder schwer beschreibbare Bedingungen unübersichtlich wird

Reicht nicht

  • die erlaubten Fälle bereits disjunkt und unmittelbar zählbar sind
Nach dem letzten Schritt rekursiv zerlegen

Jedes Objekt nach seiner letzten Baueinheit in disjunkte Fälle teilen und dadurch die Anzahl auf kleinere Größen zurückführen.

Warum funktioniert sie?

Jedes Objekt nach seiner letzten Baueinheit in disjunkte Fälle teilen und dadurch die Anzahl auf kleinere Größen zurückführen.

Erkennungssignale

  • Folgen, Treppen, Pflasterungen oder Wörter werden schrittweise aufgebaut.
  • Der letzte Schritt besitzt nur wenige mögliche Typen.

Vorgehen

  1. 1. Zustand definieren: Lege fest, was ana_n zählt.
  2. 2. Letzten Schritt klassifizieren: Nenne alle möglichen letzten Baueinheiten.
  3. 3. Kleinere Zustände zuordnen: Entferne die letzte Einheit und identifiziere den verbleibenden Zustand.
  4. 4. Anfangswerte ergänzen: Gib genügend Werte an, damit die Folge eindeutig bestimmt ist.

Geeignet

  • große Objekte eindeutig aus kleineren Zuständen aufgebaut oder in Wegschritte kodiert werden können

Reicht nicht

  • die Zerlegung überlappt oder der kleinere Zustand nicht alle nötigen Informationen enthält
Den Rekursionszustand verfeinern

Wenn die Größe allein nicht genügt, zusätzliche Endmerkmale im Zustand speichern, damit zulässige Fortsetzungen eindeutig bestimmt sind.

Warum funktioniert sie?

Wenn die Größe allein nicht genügt, zusätzliche Endmerkmale im Zustand speichern, damit zulässige Fortsetzungen eindeutig bestimmt sind.

Erkennungssignale

  • Die nächste Wahl hängt vom letzten Zeichen oder einer lokalen Bedingung ab.
  • Eine naive Rekursion zählt verbotene Fortsetzungen mit.

Vorgehen

  1. 1. Fehlende Information finden: Frage, warum nn allein die Fortsetzungen nicht bestimmt.
  2. 2. Teilzustände definieren: Trenne etwa nach letztem Symbol oder Belegungsart.
  3. 3. Übergänge schreiben: Leite für jeden Zustand erlaubte Vorgänger her.
  4. 4. Zustände summieren: Führe die Teilanzahlen zur gesuchten Gesamtanzahl zusammen.

Geeignet

  • große Objekte eindeutig aus kleineren Zuständen aufgebaut oder in Wegschritte kodiert werden können

Reicht nicht

  • die Zerlegung überlappt oder der kleinere Zustand nicht alle nötigen Informationen enthält
Eine Rekursion tabellarisch auswerten

Zustände in wachsender Größe berechnen und jeden Wert nur einmal speichern, statt dieselben Teilprobleme wiederholt zu lösen.

Warum funktioniert sie?

Zustände in wachsender Größe berechnen und jeden Wert nur einmal speichern, statt dieselben Teilprobleme wiederholt zu lösen.

Erkennungssignale

  • Viele Teilprobleme überlappen.
  • Eine Rekursionsgleichung soll für einen konkreten Index zuverlässig ausgewertet werden.

Vorgehen

  1. 1. Basiszeile eintragen: Beginne mit allen Anfangswerten.
  2. 2. Reihenfolge festlegen: Berechne nur Zustände, deren Vorgänger bereits bekannt sind.
  3. 3. Übergang anwenden: Trage jeden neuen Wert aus gespeicherten Vorgängern ein.
  4. 4. Plausibilität prüfen: Vergleiche kleine Werte mit einer direkten Liste.

Geeignet

  • große Objekte eindeutig aus kleineren Zuständen aufgebaut oder in Wegschritte kodiert werden können

Reicht nicht

  • die Zerlegung überlappt oder der kleinere Zustand nicht alle nötigen Informationen enthält
Monotone Gitterwege durch Schrittpositionen zählen

Ein Weg mit rr Rechts- und uu Aufwärtsschritten ist durch die Positionen einer Schrittart bestimmt und wird mit (r+ur)\binom{r+u}{r} gezählt.

Warum funktioniert sie?

Ein Weg mit rr Rechts- und uu Aufwärtsschritten ist durch die Positionen einer Schrittart bestimmt und wird mit (r+ur)\binom{r+u}{r} gezählt.

Erkennungssignale

  • Nur monotone Rechts- und Aufwärtsschritte sind erlaubt.
  • Start und Ziel legen die Zahl beider Schrittarten fest.

Vorgehen

  1. 1. Schrittzahlen bestimmen: Berechne horizontale und vertikale Koordinatendifferenz.
  2. 2. Wort kodieren: Schreibe jeden Weg als Wort aus R und O.
  3. 3. Positionen wählen: Wähle die Positionen einer Symbolart.
  4. 4. Nebenbedingungen prüfen: Kontrolliere Hindernisse, Zwischenpunkte oder Diagonalgrenzen separat.

Geeignet

  • große Objekte eindeutig aus kleineren Zuständen aufgebaut oder in Wegschritte kodiert werden können

Reicht nicht

  • die Zerlegung überlappt oder der kleinere Zustand nicht alle nötigen Informationen enthält
Wege durch oder an einem Punkt vorbei zählen

Wege durch einen Zwischenpunkt als Produkt der Teilwege zählen und verbotene Punktwege von allen Wegen abziehen.

Warum funktioniert sie?

Wege durch einen Zwischenpunkt als Produkt der Teilwege zählen und verbotene Punktwege von allen Wegen abziehen.

Erkennungssignale

  • Ein bestimmter Gitterpunkt muss besucht oder vermieden werden.
  • Vor und nach dem Punkt sind monotone Teilwege unabhängig.

Vorgehen

  1. 1. Teilziele bestimmen: Zerlege Start–Punkt und Punkt–Ziel.
  2. 2. Teilwege zählen: Nutze für beide Abschnitte Binomialkoeffizienten.
  3. 3. Multiplizieren: Jedes Paar von Teilwegen erzeugt genau einen Gesamtweg durch den Punkt.
  4. 4. Bei Verbot subtrahieren: Ziehe die Punktwege von allen Wegen ab.

Geeignet

  • große Objekte eindeutig aus kleineren Zuständen aufgebaut oder in Wegschritte kodiert werden können

Reicht nicht

  • die Zerlegung überlappt oder der kleinere Zustand nicht alle nötigen Informationen enthält
Diagonalgrenzen mit dem Spiegelungsprinzip behandeln

Verbotene Wege am ersten Grenzübertritt spiegeln und so bijektiv auf eine leicht zählbare unbeschränkte Wegklasse abbilden.

Warum funktioniert sie?

Verbotene Wege am ersten Grenzübertritt spiegeln und so bijektiv auf eine leicht zählbare unbeschränkte Wegklasse abbilden.

Erkennungssignale

  • Ein Weg darf eine Diagonale nicht überschreiten.
  • Alle unbeschränkten Wege sind leicht mit einem Binomialkoeffizienten zählbar.

Vorgehen

  1. 1. Alle Wege zählen: Ignoriere zunächst die Diagonalbedingung.
  2. 2. Ersten Verstoß markieren: Bestimme den ersten Schritt über die Grenze.
  3. 3. Anfangsstück spiegeln: Vertausche bis zum ersten Verstoß die beiden Schrittarten.
  4. 4. Verbotene abziehen: Nutze die bijektiv gezählte Fehlklasse; daraus folgt die Catalan-Zahl.

Geeignet

  • große Objekte eindeutig aus kleineren Zuständen aufgebaut oder in Wegschritte kodiert werden können

Reicht nicht

  • die Zerlegung überlappt oder der kleinere Zustand nicht alle nötigen Informationen enthält
Nach Parität zählen

Objekte nach geraden und ungeraden Beiträgen zerlegen und nur die Paritätsmuster zählen, die zur Zielsumme passen.

Warum funktioniert sie?

Objekte nach geraden und ungeraden Beiträgen zerlegen und nur die Paritätsmuster zählen, die zur Zielsumme passen.

Erkennungssignale

  • Eine Summe oder Anzahl soll gerade beziehungsweise ungerade sein.
  • Die einzelnen Bausteine besitzen nur zwei relevante Klassen.

Vorgehen

  1. 1. Beiträge markieren: Ordne jeden wählbaren Baustein als gerade oder ungerade ein.
  2. 2. Zulässige Muster bestimmen: Notiere, wie viele ungerade Beiträge die Zielparität erzeugen.
  3. 3. Muster getrennt zählen: Zähle jedes zulässige Muster mit Produkt- und Auswahlregel.
  4. 4. Disjunkte Fälle addieren: Addiere die Paritätsmuster und prüfe kleine Fälle.

Geeignet

  • eine Zählaufgabe zusätzlich eine arithmetische oder strukturelle Bedingung enthält

Reicht nicht

  • die Zusatzbedingung die gewählten Klassen nicht respektiert oder die Fälle überlappen
Mit Restklassen filtern

Zahlen nach ihren Resten modulo mm gruppieren und genau die Restmuster kombinieren, deren Summe den verlangten Rest besitzt.

Warum funktioniert sie?

Zahlen nach ihren Resten modulo mm gruppieren und genau die Restmuster kombinieren, deren Summe den verlangten Rest besitzt.

Erkennungssignale

  • Teilbarkeit einer Summe entscheidet über die Zulässigkeit.
  • Die konkreten Zahlen sind weniger wichtig als ihre Reste.

Vorgehen

  1. 1. Modul wählen: Verwende den Divisor aus der Zielbedingung.
  2. 2. Restklassen zählen: Bestimme die Größe jeder vorkommenden Restklasse.
  3. 3. Zulässige Restmuster finden: Liste ungeordnet und vollständig alle Restkombinationen mit dem Zielrest.
  4. 4. Innerhalb der Klassen wählen: Übersetze jedes Muster in Binomialkoeffizienten oder Produkte.

Geeignet

  • eine Zählaufgabe zusätzlich eine arithmetische oder strukturelle Bedingung enthält

Reicht nicht

  • die Zusatzbedingung die gewählten Klassen nicht respektiert oder die Fälle überlappen
Gewichtete Beiträge doppelt zählen

Eine Gesamtsumme von Beiträgen einmal objektweise und einmal nach den beitragenden Elementen zählen.

Warum funktioniert sie?

Eine Gesamtsumme von Beiträgen einmal objektweise und einmal nach den beitragenden Elementen zählen.

Erkennungssignale

  • Über viele Objekte wird eine Größe wie Kardinalität, Grad oder Häufigkeit summiert.
  • Jedes Grundelement trägt zu gleich vielen Objekten bei.

Vorgehen

  1. 1. Paare definieren: Markiere ein Objekt zusammen mit einem darin enthaltenen Beitrag.
  2. 2. Nach Objekten zählen: Jedes Objekt liefert so viele Paare wie sein Gewicht.
  3. 3. Nach Beiträgen zählen: Fixiere ein Grundelement und zähle alle Objekte, die es enthalten.
  4. 4. Gleichsetzen: Setze beide Zählungen derselben markierten Paare gleich.

Geeignet

  • eine Zählaufgabe zusätzlich eine arithmetische oder strukturelle Bedingung enthält

Reicht nicht

  • die Zusatzbedingung die gewählten Klassen nicht respektiert oder die Fälle überlappen
Schubfächer strukturell wählen

Mehr Objekte als mögliche Klassen erzwingen eine Kollision; entscheidend ist eine Klasseneinteilung, bei der jede Kollision die Behauptung liefert.

Warum funktioniert sie?

Mehr Objekte als mögliche Klassen erzwingen eine Kollision; entscheidend ist eine Klasseneinteilung, bei der jede Kollision die Behauptung liefert.

Erkennungssignale

  • Eine Existenzbehauptung verlangt zwei Objekte mit einer gemeinsamen Eigenschaft.
  • Es gibt weniger mögliche Reste, Intervalle oder Zustände als Objekte.

Vorgehen

  1. 1. Objekte bestimmen: Lege fest, was verteilt wird.
  2. 2. Schubfächer entwerfen: Wähle Klassen, deren gemeinsame Belegung die Zielaussage erzwingt.
  3. 3. Anzahlen vergleichen: Zeige, dass mehr Objekte als Schubfächer vorhanden sind.
  4. 4. Kollision übersetzen: Formuliere ausdrücklich, warum die beiden Objekte die Behauptung erfüllen.

Geeignet

  • eine Zählaufgabe zusätzlich eine arithmetische oder strukturelle Bedingung enthält

Reicht nicht

  • die Zusatzbedingung die gewählten Klassen nicht respektiert oder die Fälle überlappen
Eine Zählgröße als Invariante nutzen

Eine unter jedem erlaubten Zug unveränderte Zählgröße oder Restklasse finden und Start- mit Zielzustand vergleichen.

Warum funktioniert sie?

Eine unter jedem erlaubten Zug unveränderte Zählgröße oder Restklasse finden und Start- mit Zielzustand vergleichen.

Erkennungssignale

  • Eine Figur wird durch lokale Züge, Färbungen oder Umschaltungen verändert.
  • Gefragt ist, ob ein Zielzustand überhaupt erreichbar oder eine Zerlegung möglich ist.

Vorgehen

  1. 1. Zählgröße vermuten: Teste Anzahlen, Differenzen, Paritäten oder Reste.
  2. 2. Jeden Zug prüfen: Beweise, dass sich die Größe nie oder nur um ein Vielfaches von mm ändert.
  3. 3. Startwert berechnen: Bestimme die Invariantenklasse des Anfangszustands.
  4. 4. Ziel vergleichen: Ein anderer Wert oder Rest macht das Ziel unmöglich.

Geeignet

  • eine Zählaufgabe zusätzlich eine arithmetische oder strukturelle Bedingung enthält

Reicht nicht

  • die Zusatzbedingung die gewählten Klassen nicht respektiert oder die Fälle überlappen
Ein Extremobjekt festhalten

Ein größtes, kleinstes oder randständiges Objekt auswählen, dessen Beziehungen besonders stark eingeschränkt sind.

Warum funktioniert sie?

Ein größtes, kleinstes oder randständiges Objekt auswählen, dessen Beziehungen besonders stark eingeschränkt sind.

Erkennungssignale

  • Eine lokale Struktur soll in jeder endlichen Konfiguration existieren.
  • Ein Objekt mit maximalem oder minimalem Wert hat weniger mögliche Ausweichfälle.

Vorgehen

  1. 1. Extremgröße wählen: Bestimme die relevante Ordnung oder Anzahl.
  2. 2. Extremobjekt fixieren: Wähle ein Objekt mit maximalem oder minimalem Wert.
  3. 3. Nachbarschaft untersuchen: Nutze, dass kein Objekt die Extremgröße über- oder unterschreiten kann.
  4. 4. Struktur erzwingen: Leite durch Zählen oder Schubfachprinzip die verlangte Konfiguration her.

Geeignet

  • eine Zählaufgabe zusätzlich eine arithmetische oder strukturelle Bedingung enthält

Reicht nicht

  • die Zusatzbedingung die gewählten Klassen nicht respektiert oder die Fälle überlappen
Zählsignale diagnostizieren

Objekt, Gleichheit, Reihenfolge, Wiederholung und Nebenbedingungen bestimmen und daraus die passende Methode ableiten.

Warum funktioniert sie?

Objekt, Gleichheit, Reihenfolge, Wiederholung und Nebenbedingungen bestimmen und daraus die passende Methode ableiten.

Erkennungssignale

  • Mehrere Formeln scheinen möglich.
  • Die Schwierigkeit liegt in der Übersetzung des Textes.

Vorgehen

  1. 1. Zählobjekt definieren: Formuliere genau, was ein Ergebnis ist.
  2. 2. Entscheidungsfragen klären: Prüfe Reihenfolge, Wiederholung, Gleichheit und Bedingungen.
  3. 3. Hauptstruktur wählen: Entscheide zwischen Fällen, Auswahl, Anordnung, Bijektion, Rekursion oder Existenzargument.
  4. 4. Kleinfall testen: Prüfe das Modell an einer direkt auflistbaren Instanz.

Geeignet

  • eine gemischte Wettbewerbsaufgabe modelliert, geplant oder kontrolliert werden muss

Reicht nicht

  • das eigentliche Zählobjekt noch nicht präzise definiert ist
Einen Zählbeweis auditieren

Eine Lösung auf vollständige Fälle, eindeutige Erzeugung, korrekte Mehrfachheiten und eine klare Schlussfolgerung prüfen.

Warum funktioniert sie?

Eine Lösung auf vollständige Fälle, eindeutige Erzeugung, korrekte Mehrfachheiten und eine klare Schlussfolgerung prüfen.

Erkennungssignale

  • Ein Faktor oder Korrekturterm bleibt unbegründet.
  • Geordnete Konstruktionen sollen ungeordnete Objekte zählen.

Vorgehen

  1. 1. Abdeckung prüfen: Erreicht die Konstruktion jedes zulässige Objekt?
  2. 2. Mehrfachheit prüfen: Wie oft wird dasselbe Objekt erzeugt?
  3. 3. Fallgrenzen prüfen: Sind die Fälle disjunkt und alle Randfälle enthalten?
  4. 4. Schluss formulieren: Verbinde die Rechnung ausdrücklich mit der Zielaussage.

Geeignet

  • eine gemischte Wettbewerbsaufgabe modelliert, geplant oder kontrolliert werden muss

Reicht nicht

  • das eigentliche Zählobjekt noch nicht präzise definiert ist
Eine Kombinatorik-Generalprobe steuern

Aufgaben sichten, sichere Punkte abschließen, Methodenwechsel bewusst entscheiden und jede Lösung mit einem Zählaudit beenden.

Warum funktioniert sie?

Aufgaben sichten, sichere Punkte abschließen, Methodenwechsel bewusst entscheiden und jede Lösung mit einem Zählaudit beenden.

Erkennungssignale

  • Mehrere Aufgaben müssen in begrenzter Zeit bearbeitet werden.
  • Teilpunkte hängen von Modell und Begründung ab.

Vorgehen

  1. 1. Sichten: Markiere Zählobjekt, Hauptbedingung und vermutete Methode.
  2. 2. Sichere Punkte schreiben: Schließe klare Aufgaben zuerst vollständig ab.
  3. 3. Sackgassen begrenzen: Wechsle nach einem festen Zeitfenster und notiere den Ansatz.
  4. 4. Abgabe auditieren: Kontrolliere Mehrfachheiten, Randfälle, Zahlenwert und Antwortsatz.

Geeignet

  • eine gemischte Wettbewerbsaufgabe modelliert, geplant oder kontrolliert werden muss

Reicht nicht

  • das eigentliche Zählobjekt noch nicht präzise definiert ist