Kombinatorische Beweisprinzipien

Gutes YT Video https://youtu.be/kWPj-Q5e9Lo

Einige Grundszenarien zum ziehen von Elementen :

Beispiele für Kombinationen beim ziehen von Elementen auf verschiedenen Arten

• Ziehen mit Zurücklegen geordnet :

• Ziehen mit Zurücklegen ungeordnet :

• Ziehen ohne Zurücklegen geordnet :

• Ziehen ohne Zurücklegen ungeordnet :

• Geordnet : (1,2) und (2,1) zählen als 2 verschiedene Elemente

• Ungeordnet : (1,2) und (2,1) zählen als 1 Element

Anzahl der Elemente für verschiedene Szenarien

herleitung von Ziehen ohne zurücklegen, geordnet

Analyse ziehen ohne zurückleiten II

Kombinatorische Beweisprinzipien

Die Summenregel und ein Beispiel

Falls S sich aufteilen lässt, in m disjunkte(also jeweils komplett verschiedene) Mengen, dann ist die Kardinalität der Menge dieselbe, wie die Kardinalitäten der einzelnen disjunkten Mengen summiert.

Disjunkte Mengen , sind Mengen, deren Schnittmenge leer ist, also bestehen sie aus komplett verschiedenen Elementen. Kardinalität bezeichnet die Anzahl der verschiedenen Elemente in einer Menge, ein relevanter Begriff für die Kombinatorik.

Die Produktregel und ein Beispiel

Falls die Anzahl aller Elemente durch das kartesische Produkt definiert ist, dann ist die Menge aller Elemente, dass Produkt aller einzelnen Elemente.

Gleichheitsregel und Beispiel

Gleichheitsregel: Wenn sich eine Menge S mithilfe einer bijektiven Funktion auf eine andere Menge T abbilden lässt, dann ist die Kardinalität von S äquivalent zu T . Bijektiv bedeutet, dass jedes Element ein Bild in der anderen Menge hat und jedes Bild durch ein einziges Element abgebildet wird.

Doppeltes Abzählen und Beispiel

Doppeltes Abzählen : Wenn man nur das erste Element der Binären relation zählt ist diese Menge dieselbe als wenn man das zweite Element aus der jeweils jeder Binären Relation zählt. Binäre Relationen : Tupel die aus 2 Elementen bestehen

Schubfachprinzip : Wenn es Y Schubladen gibt und X dinge die ich In Schubladen verschauen möchte, dann gibt es in einer Schublade mindestens X/Y Elemente, im Durchschnitt sogar X/y Unteranderen ist A -> B nicht injektiv

Beispiele für das SChubfachprinzip(Pigeonhole) : Geburtstage: Wenn ich 13 Personen kenne, haben mindestens 2 im selben Monat Geburtstag. Tauben: Wenn ich 10 Tauben habe und 5 Löcher, müssen in einem Loch mindestens 2 Sein (10/5) Tauben: Wenn ich 10 Tauben habe und 2 Löcher, müssen in einem Loch mindestens 5 Sein (10/2) Tauben: Wenn ich 10 Tauben habe und 1 Löcher, müssen in einem Loch mindestens 10 Sein (10/1)