Themenbuch
Kombinatorik
Strukturen zählen statt Fälle verlieren – vom Baumdiagramm zur Olympiade
Ein freundlicher Weg vom präzisen Zählobjekt über Summen- und Produktregel bis zu olympiadetauglichen Zählbeweisen.
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
- 1Zählobjekte und systematische Listen
Fundament
- 2Summenregel und Produktregel
baut auf den vorherigen Ideen auf
- 3Fakultät und Permutationen
baut auf den vorherigen Ideen auf
- 4Gleiche Elemente und Anordnungsbedingungen
baut auf den vorherigen Ideen auf
- 5Ungeordnete Auswahlen und Binomialkoeffizienten
baut auf den vorherigen Ideen auf
- 6Pascal-Regel und Teilmengenstrukturen
baut auf den vorherigen Ideen auf
- 7Inzidenzen und doppeltes Zählen
baut auf den vorherigen Ideen auf
- 8Bijektionen, Gitterwege und Trennstriche
baut auf den vorherigen Ideen auf
- 9Ergänzungszählung und genaue Fälle
baut auf den vorherigen Ideen auf
- 10Inklusion–Exklusion und Fixpunkte
baut auf den vorherigen Ideen auf
- 11Rekursionen und Zustandsmodelle
baut auf den vorherigen Ideen auf
- 12Strukturierte Gitterwege und Catalan-Zahlen
baut auf den vorherigen Ideen auf
- 13Parität, Restklassen und gewichtete Zählungen
baut auf den vorherigen Ideen auf
- 14Schubfach, Invarianten und Extremalprinzip
baut auf den vorherigen Ideen auf
- 15Strategiewahl und Beweiswerkstatt
baut auf den vorherigen Ideen auf
- 16Kombinatorik-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. Ergebnis beschreiben: Formuliere ein einzelnes vollständiges Ergebnis als Tupel, Menge, Wort oder Weg.
- 2. Gleichheit klären: Entscheide, wann zwei Beschreibungen dasselbe Ergebnis meinen.
- 3. Bedingungen notieren: Markiere verbotene Wiederholungen, führende Nullen und weitere Einschränkungen.
- 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. Ordnung wählen: Sortiere nach erster Stelle, kleinstem Element oder erstem Schritt.
- 2. Gruppe abschließen: Liste alle Fortsetzungen eines festen Anfangs auf.
- 3. Weitergehen: Wechsle erst danach zum nächsten Anfang.
- 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. Stufen bestimmen: Lege fest, welche Entscheidung Zeile, Spalte oder Baumstufe bildet.
- 2. Möglichkeiten eintragen: Beschrifte jede Zeile, Spalte oder Kante eindeutig.
- 3. Bedingungen anwenden: Markiere ungültige Zellen oder beende verbotene Zweige.
- 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. Fälle definieren: Formuliere Fälle mit eindeutigen Grenzen.
- 2. Disjunktheit prüfen: Zeige, dass kein Ergebnis in zwei Fällen liegt.
- 3. Vollständigkeit prüfen: Zeige, dass jedes erlaubte Ergebnis einen Fall trifft.
- 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. Stufen festlegen: Zerlege jedes Ergebnis in eine eindeutige Folge von Entscheidungen.
- 2. Möglichkeiten zählen: Bestimme die Anzahl pro Stufe unter Beachtung früherer Entscheidungen.
- 3. Multiplizieren: Multipliziere die Stufenanzahlen entlang eines vollständigen Weges.
- 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. Vertauschungstest: Frage, ob das Vertauschen zweier gewählter Elemente das Ergebnis ändert.
- 2. Wiederholungstest: Prüfe, ob ein Element mehrfach verwendet werden darf.
- 3. Sonderplätze prüfen: Beachte etwa führende Nullen oder eine letzte gerade Ziffer.
- 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 verschiedene Elemente entstehen lineare Anordnungen.
Warum funktioniert sie?
Für verschiedene Elemente entstehen lineare Anordnungen.
Erkennungssignale
- Alle vorhandenen Elemente werden genau einmal verwendet.
- Jeder Platz und jede Reihenfolge ist unterscheidbar.
Vorgehen
- 1. Ersten Platz wählen: Für den ersten Platz gibt es Möglichkeiten.
- 2. Anzahlen reduzieren: Ohne Wiederholung bleiben danach Möglichkeiten.
- 3. Produkt bilden: Multipliziere die Stufenanzahlen zur Fakultät .
- 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 geordnete Plätze aus verschiedenen Elementen ohne Wiederholung gibt es Möglichkeiten.
Warum funktioniert sie?
Für geordnete Plätze aus verschiedenen Elementen ohne Wiederholung gibt es 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. Geordnete Plätze nennen: Lege die verschiedenen Rollen oder Positionen fest.
- 2. Ersten Platz besetzen: Wähle eines von Elementen.
- 3. Ohne Wiederholung fortsetzen: Für jeden weiteren Platz bleibt ein Element weniger.
- 4. Abbrechendes Produkt: Multipliziere genau 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 vor steht.
- Die Vertauschung von und ändert keine andere Bedingung.
Vorgehen
- 1. Alle Anordnungen zählen: Ignoriere zunächst die relative Reihenfolgebedingung.
- 2. Paarbildung definieren: Vertausche in jeder Anordnung genau die beiden betrachteten Elemente.
- 3. Klassen vergleichen: In jedem Paar steht einmal vor und einmal vor .
- 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 Elementen Gruppen von gleichen Elementen, werden die markierten Anordnungen durch geteilt.
Warum funktioniert sie?
Sind unter Elementen Gruppen von gleichen Elementen, werden die markierten Anordnungen durch geteilt.
Erkennungssignale
- Buchstaben oder Objekte kommen mehrfach identisch vor.
- Das Vertauschen gleicher Exemplare erzeugt kein neues sichtbares Ergebnis.
Vorgehen
- 1. Vorübergehend markieren: Behandle gleiche Exemplare zunächst als unterscheidbar und zähle .
- 2. Unsichtbare Vertauschungen zählen: Eine Gruppe von gleichen Elementen wurde intern -fach gezählt.
- 3. Für jede Gruppe teilen: Dividiere durch das Produkt aller internen Fakultäten.
- 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. Bedingung übersetzen: Entscheide zwischen Block für Nähe und Lücken für Trennung.
- 2. Äußere Einheiten anordnen: Zähle Block oder Grundelemente als Einheiten.
- 3. Innere Möglichkeiten zählen: Berücksichtige Blockreihenfolgen oder die Auswahl der Lücken.
- 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 Kreis-Anordnungen.
Warum funktioniert sie?
Bei Sitzordnungen ohne ausgezeichneten Startplatz gelten Rotationen als gleich; durch Fixieren einer Person bleiben Kreis-Anordnungen.
Erkennungssignale
- Die Plätze liegen an einem runden Tisch.
- Nur Nachbarschaften und zyklische Reihenfolge, nicht die absolute Position, sind wichtig.
Vorgehen
- 1. Gleichheit klären: Prüfe, dass gedrehte Sitzpläne als gleich gelten, Spiegelungen aber verschieden bleiben.
- 2. Eine Person fixieren: Setze eine ausgewählte Person auf einen gedachten Referenzplatz.
- 3. Rest linear anordnen: Ordne die übrigen Personen relativ zu ihr.
- 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 -elementigen Teilmengen einer -elementigen Menge ist .
Warum funktioniert sie?
Die Zahl der -elementigen Teilmengen einer -elementigen Menge ist .
Erkennungssignale
- Es wird ein Team, Ausschuss oder eine Teilmenge fester Größe gewählt.
- Innerhalb der Auswahl gibt es keine Rollen.
Vorgehen
- 1. Modell prüfen: Kläre, dass genau verschiedene Elemente aus gewählt werden und die Reihenfolge unwichtig ist.
- 2. Kleinen Parameter wählen: Nutze gegebenenfalls .
- 3. Produkt kürzen: Berechne mit Faktoren im Zähler und im Nenner.
- 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 -Tupel und teile durch , weil jedes ungeordnete Team in genau Reihenfolgen erscheint.
Warum funktioniert sie?
Zähle zunächst geordnete -Tupel und teile durch , weil jedes ungeordnete Team in genau Reihenfolgen erscheint.
Erkennungssignale
- Die geordnete Auswahl ist leicht zu zählen.
- Jede Gruppe besitzt gleich viele interne Reihenfolgen.
Vorgehen
- 1. Geordnet zählen: Bestimme .
- 2. Mehrfachheit bestimmen: Jede -Gruppe wird durch ihre Reihenfolgen beschrieben.
- 3. Teilen: Dividiere die geordnete Anzahl durch .
- 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 -Auswahl bestimmt eindeutig ihre Ergänzung mit Elementen; daher gilt .
Warum funktioniert sie?
Jede -Auswahl bestimmt eindeutig ihre Ergänzung mit Elementen; daher gilt .
Erkennungssignale
- Es ist deutlich kürzer, die ausgeschlossenen statt der gewählten Elemente festzulegen.
- Die beiden Auswahlgrößen und treten symmetrisch auf.
Vorgehen
- 1. Grundmenge nennen: Fixiere die Menge aller Elemente.
- 2. Ergänzung bilden: Ordne jeder Auswahl die Menge der nicht gewählten Elemente zu.
- 3. Umkehrbarkeit zeigen: Aus der Ergänzung lässt sich die ursprüngliche Auswahl eindeutig zurückgewinnen.
- 4. Kleinere Seite zählen: Verwende den günstigeren der Parameter und .
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 -Auswahlen danach, ob ein festes Element enthalten ist: .
Warum funktioniert sie?
Teile alle -Auswahlen danach, ob ein festes Element enthalten ist: .
Erkennungssignale
- Ein bestimmtes Element kann enthalten oder nicht enthalten sein.
- Benachbarte Binomialkoeffizienten sollen addiert werden.
Vorgehen
- 1. Element fixieren: Wähle ein bestimmtes Element der Grundmenge.
- 2. Enthalten-Fall: Ist gewählt, fehlen noch aus .
- 3. Nicht-enthalten-Fall: Ist nicht gewählt, werden alle aus den übrigen gewählt.
- 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. Pflicht aufnehmen: Reduziere Auswahlgröße und verfügbare Menge um jedes bereits gewählte Element.
- 2. Verbotenes entfernen: Entferne ausgeschlossene Elemente nur aus der verfügbaren Menge.
- 3. Verbleibende Auswahl zählen: Verwende den passenden Binomialkoeffizienten.
- 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 Binärwörter bijektiv allen Teilmengen.
Warum funktioniert sie?
Für jedes Element entscheidet ein Bit über enthalten oder nicht enthalten; dadurch entsprechen die 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. Elemente ordnen: Gib den Elementen feste Positionen.
- 2. Bits setzen: Schreibe 1 für enthalten und 0 für nicht enthalten.
- 3. Bijektion prüfen: Jede Teilmenge liefert genau ein Wort und jedes Wort genau eine Teilmenge.
- 4. Bedingung übersetzen: Eine Auswahlgröße bedeutet genau 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. Objektmenge definieren: Lege exakt fest, welche Paare, Markierungen oder Strukturen gezählt werden.
- 2. Erste Beschreibung: Zähle nach einem natürlichen ersten Merkmal.
- 3. Zweite Beschreibung: Gruppiere dieselben Objekte anders oder kodiere sie um.
- 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. Objektmenge definieren: Lege exakt fest, welche Paare, Markierungen oder Strukturen gezählt werden.
- 2. Erste Beschreibung: Zähle nach einem natürlichen ersten Merkmal.
- 3. Zweite Beschreibung: Gruppiere dieselben Objekte anders oder kodiere sie um.
- 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. Objektmenge definieren: Lege exakt fest, welche Paare, Markierungen oder Strukturen gezählt werden.
- 2. Erste Beschreibung: Zähle nach einem natürlichen ersten Merkmal.
- 3. Zweite Beschreibung: Gruppiere dieselben Objekte anders oder kodiere sie um.
- 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. Objektmenge definieren: Lege exakt fest, welche Paare, Markierungen oder Strukturen gezählt werden.
- 2. Erste Beschreibung: Zähle nach einem natürlichen ersten Merkmal.
- 3. Zweite Beschreibung: Gruppiere dieselben Objekte anders oder kodiere sie um.
- 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. Objektmenge definieren: Lege exakt fest, welche Paare, Markierungen oder Strukturen gezählt werden.
- 2. Erste Beschreibung: Zähle nach einem natürlichen ersten Merkmal.
- 3. Zweite Beschreibung: Gruppiere dieselben Objekte anders oder kodiere sie um.
- 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. Grundmenge definieren: Zähle alle Objekte ohne die schwierige Bedingung.
- 2. Gegenereignis formulieren: Negiere die Bedingung logisch korrekt.
- 3. Gegenmenge zählen: Zähle jedes verbotene Objekt genau einmal.
- 4. Subtrahieren: Berechne 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. Zählparameter wählen: Bestimme, welche Anzahl die Fälle unterscheidet.
- 2. Zulässige Werte auflisten: Nenne jeden möglichen Wert im Definitionsbereich.
- 3. Jeden Fall zählen: Multipliziere unabhängige Auswahlen innerhalb des Falls.
- 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 die Einzelmengen addieren und ihre doppelt gezählte Schnittmenge einmal abziehen.
Warum funktioniert sie?
Bei 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. Mengen definieren: Formuliere die beiden Eigenschaften als Mengen und .
- 2. Einzelmengen zählen: Bestimme und .
- 3. Schnitt zählen: Bestimme die Objekte mit beiden Eigenschaften.
- 4. Korrigieren: Verwende .
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. Einzelmengen addieren: Beginne mit .
- 2. Paarschnitte abziehen: Subtrahiere die drei paarweisen Überschneidungen.
- 3. Dreifachschnitt prüfen: Er wurde dreimal addiert und dreimal abgezogen.
- 4. Einmal hinzufügen: Addiere .
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. Fehlermengen definieren: enthält alle Anordnungen mit Verstoß an Position .
- 2. Schnitte zählen: Bei festgelegten Fixpunkten bleiben Anordnungen.
- 3. Vereinigung berechnen: Nutze die alternierende Inklusion–Exklusion-Summe.
- 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. Alle Zuordnungen: Bei Klassen und Objekten gibt es Funktionen.
- 2. Fehlende Klasse definieren: Für jede Zielklasse bilde die Menge der Zuordnungen, die sie nicht benutzen.
- 3. Überschneidungen korrigieren: Nutze Ein- und Ausschluss für mehrere fehlende Klassen.
- 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. Zustand definieren: Lege fest, was zählt.
- 2. Letzten Schritt klassifizieren: Nenne alle möglichen letzten Baueinheiten.
- 3. Kleinere Zustände zuordnen: Entferne die letzte Einheit und identifiziere den verbleibenden Zustand.
- 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. Fehlende Information finden: Frage, warum allein die Fortsetzungen nicht bestimmt.
- 2. Teilzustände definieren: Trenne etwa nach letztem Symbol oder Belegungsart.
- 3. Übergänge schreiben: Leite für jeden Zustand erlaubte Vorgänger her.
- 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. Basiszeile eintragen: Beginne mit allen Anfangswerten.
- 2. Reihenfolge festlegen: Berechne nur Zustände, deren Vorgänger bereits bekannt sind.
- 3. Übergang anwenden: Trage jeden neuen Wert aus gespeicherten Vorgängern ein.
- 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 Rechts- und Aufwärtsschritten ist durch die Positionen einer Schrittart bestimmt und wird mit gezählt.
Warum funktioniert sie?
Ein Weg mit Rechts- und Aufwärtsschritten ist durch die Positionen einer Schrittart bestimmt und wird mit gezählt.
Erkennungssignale
- Nur monotone Rechts- und Aufwärtsschritte sind erlaubt.
- Start und Ziel legen die Zahl beider Schrittarten fest.
Vorgehen
- 1. Schrittzahlen bestimmen: Berechne horizontale und vertikale Koordinatendifferenz.
- 2. Wort kodieren: Schreibe jeden Weg als Wort aus R und O.
- 3. Positionen wählen: Wähle die Positionen einer Symbolart.
- 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. Teilziele bestimmen: Zerlege Start–Punkt und Punkt–Ziel.
- 2. Teilwege zählen: Nutze für beide Abschnitte Binomialkoeffizienten.
- 3. Multiplizieren: Jedes Paar von Teilwegen erzeugt genau einen Gesamtweg durch den Punkt.
- 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. Alle Wege zählen: Ignoriere zunächst die Diagonalbedingung.
- 2. Ersten Verstoß markieren: Bestimme den ersten Schritt über die Grenze.
- 3. Anfangsstück spiegeln: Vertausche bis zum ersten Verstoß die beiden Schrittarten.
- 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. Beiträge markieren: Ordne jeden wählbaren Baustein als gerade oder ungerade ein.
- 2. Zulässige Muster bestimmen: Notiere, wie viele ungerade Beiträge die Zielparität erzeugen.
- 3. Muster getrennt zählen: Zähle jedes zulässige Muster mit Produkt- und Auswahlregel.
- 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 gruppieren und genau die Restmuster kombinieren, deren Summe den verlangten Rest besitzt.
Warum funktioniert sie?
Zahlen nach ihren Resten modulo 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. Modul wählen: Verwende den Divisor aus der Zielbedingung.
- 2. Restklassen zählen: Bestimme die Größe jeder vorkommenden Restklasse.
- 3. Zulässige Restmuster finden: Liste ungeordnet und vollständig alle Restkombinationen mit dem Zielrest.
- 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. Paare definieren: Markiere ein Objekt zusammen mit einem darin enthaltenen Beitrag.
- 2. Nach Objekten zählen: Jedes Objekt liefert so viele Paare wie sein Gewicht.
- 3. Nach Beiträgen zählen: Fixiere ein Grundelement und zähle alle Objekte, die es enthalten.
- 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. Objekte bestimmen: Lege fest, was verteilt wird.
- 2. Schubfächer entwerfen: Wähle Klassen, deren gemeinsame Belegung die Zielaussage erzwingt.
- 3. Anzahlen vergleichen: Zeige, dass mehr Objekte als Schubfächer vorhanden sind.
- 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. Zählgröße vermuten: Teste Anzahlen, Differenzen, Paritäten oder Reste.
- 2. Jeden Zug prüfen: Beweise, dass sich die Größe nie oder nur um ein Vielfaches von ändert.
- 3. Startwert berechnen: Bestimme die Invariantenklasse des Anfangszustands.
- 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. Extremgröße wählen: Bestimme die relevante Ordnung oder Anzahl.
- 2. Extremobjekt fixieren: Wähle ein Objekt mit maximalem oder minimalem Wert.
- 3. Nachbarschaft untersuchen: Nutze, dass kein Objekt die Extremgröße über- oder unterschreiten kann.
- 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. Zählobjekt definieren: Formuliere genau, was ein Ergebnis ist.
- 2. Entscheidungsfragen klären: Prüfe Reihenfolge, Wiederholung, Gleichheit und Bedingungen.
- 3. Hauptstruktur wählen: Entscheide zwischen Fällen, Auswahl, Anordnung, Bijektion, Rekursion oder Existenzargument.
- 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. Abdeckung prüfen: Erreicht die Konstruktion jedes zulässige Objekt?
- 2. Mehrfachheit prüfen: Wie oft wird dasselbe Objekt erzeugt?
- 3. Fallgrenzen prüfen: Sind die Fälle disjunkt und alle Randfälle enthalten?
- 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. Sichten: Markiere Zählobjekt, Hauptbedingung und vermutete Methode.
- 2. Sichere Punkte schreiben: Schließe klare Aufgaben zuerst vollständig ab.
- 3. Sackgassen begrenzen: Wechsle nach einem festen Zeitfenster und notiere den Ansatz.
- 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