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)
