Kombinatorik - Zusammenfassung PDF

Preview

Summary

Zusammenfassung...

Description

Kombinatorik Kombinatorische Grundprinzipien Summenregel: Die Kardinalität einer disjunkten Vereinigung („

“) endlicher Mengen entspricht genau der Summe

der einzelnen Kardinalitäten:  Will man von Mehreren Teilexperimente, die sich nicht beeinflussen die versch. Ausgänge muss man addieren. Produktregel: Die Kardinalität des kartesischen Produkts endlicher Mengen entspricht genau dem Produkt der einzelnen Kardinalitäten:  Hängen die Experimente zusammen, muss man multiplizieren, um alle Ausgänge zu erhalten Schubfachprinzip: Sei f: X → Y mit 0 < |Y |, |X| < ∞. Dann gilt:  X = Objekte, Y = Schubfächer für die Objekte. Verteilt man alle Objekte auf die Schubfächer, dann hat man mindestens ein Schubfach mit mindestens

Objekten.

Doppeltes Abzählen: In jeder Matrix (Tabelle) ist die Summe der Zeilensummen gleich der Summe der Spaltensummen. Siebformel: Für beliebige (nicht notwendigerweise disjunkte) endliche Mengen A1, . . ., An gilt:

Urnenziehungen n Kugeln, k-mal ziehen

Binomialformel Für n ∈ N0 beliebige a und b gilt: Bsp.: Was ist der Koeffizient von x3y5z4 in (xyz + y + z) 6?

Stirling-Zahlen 2. Art Sn,k gibt die Anzahl der Partitionen einer n-elementigen Menge in k nichtleere Klassen an. Man schreibt o

uch

statt Sn,k .

Sn,k = Sn−1,k−1 + k · Sn−1,k mit S0,0 = 1, Sn,0 = 0 und Sn,n = 1 für alle n ∈ N Stirling-Zahlen 1. Art sn,k gibt die Anzahl der Permutationen in Zyklenschreibweise von n Elementen mit genau k (nichtleeren) Zyklen an. Man schreibt oft auch

statt sn,k .

Zahlpartitionen Pn,k gibt die Anzahl der Partitionen der n-elementigen Multimenge {|1, 1, . . . , 1|} in k nichtleere Klassen an. Intuitiv gibt Pn,k die Anzahl der Möglichkeiten, n als Summe von k Summanden aus N darzustellen

 KOMBINATORIKTABELLE...