Kombinatorische Beweisprinzipien
Last updated
Last updated
Gutes YT Video https://youtu.be/kWPj-Q5e9Lo
Einige Grundszenarien zum ziehen von Elementen :
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
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.
Falls die Anzahl aller Elemente durch das kartesische Produkt definiert ist, dann ist die Menge aller Elemente, dass Produkt aller einzelnen Elemente.
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 : 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)
