Abzählende Kombinatorik

Aus Infostudium Wiki

Wechseln zu: Navigation, Suche

M = {1,2,3}, 2 Elemente aus M ziehen

geordnet (auf Reih. geachtet) ungeordnet (gefiltert) (nicht auf die Reih. geachtet)
mit Zurücklegen (1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)
S(3,2) 		{1,1}',{1,2}',{1,3}',{2,2}',{2,3}',{3,3}'
M(3,2)
ohne Zurücklegen (1,2),(1,3),(2,1),(2,3),(3,1),(3,2)
S0(3,3) 		{1,2}',{1,3}',{2,3}'
M0(3,3)

Ziehen von k Elementen aus n Elementen.

|S(n,k)| = n^k = n \cdot n \cdot n \cdot n \cdot... Möglichkeiten. Siehe Anzahl beliebiger Abbildungen

|S(n,k)| = \sum_{X \in M_0(n,k)} |\varphi^{-1}(\lbrace x \rbrace)| = \sum_{X \in M_0(n,k)} k! = |M_0(n,k)| \cdot k!

|S_0(n,k)| = n \cdot (n-1) \cdot (n-2) \cdot (n-k+1) \cdot... Möglichkeiten = \frac{n!}{(n-k)!} = k! \cdot {n \choose k}

|M_0(n,k)| = {n \choose k}

|M(n,k)| = {n+k-1 \choose k} = {n+k-1 \choose n-1}

Beispiele:

|M_0(4,2)| = {4 \choose 2} = \frac{4!}{2! \cdot (4-2)!} = \frac{4 \cdot 3 \cdot 2 \cdot 1}{2 \cdot 1 \cdot 2 \cdot 1}

M0(4,2) = {{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}}

f \in M(n,k) repräsentiert eine sogenannte Multimenge, also eine "Menge", die Elemente mehrfach enthalten kann.

Jede n elementige Menge hat genausoviele Teilmengen gerader Ordnung wie ungerader Ordnung.

Vandermonde Identität

{w+m \choose k} = \sum_{l=0}^k {w \choose e}{m \choose k-l}

Die Anzahl der Möglichkeiten k Elemente aus diesen w+m auszuwählen ist die Summe der Anzahl der Möglichkeiten, l Elemente und k-l Elemente auszuwählen.

Tipps für Klausur

  • Bei der Bestimmung des Binomialkoeffizienten: So weit kürzen, soweit es geht. Erspart Zeit beim Rechnen.
Von „http://wiki.infostudium.de/wiki/Abz%C3%A4hlende_Kombinatorik“
Persönliche Werkzeuge