next up previous contents index
Next: Permutationen Up: Kombinatorik Previous: Kombinatorik   Contents   Index

Subsections


Elementare Zählprinzipien


Auswahlen

Wir betrachten eine Menge $ M$ mit $ n$ Elementen. Wie viele Auswahlen von $ k$ Elementen aus $ M$ gibt es:

  1. Variationen

    1. mit Wiederholung und mit Berücksichtigung der Reihenfolge

      $\displaystyle n^{k}$

    2. ohne Wiederholung und mit Berücksichtigung der Reihenfolge (speziell für $ k=n$ Permutation)

      $\displaystyle \frac{n!}{\left(n-k\right)!}=\left(\begin{array}{c}
n\\
k\end{array}\right)k!$

  2. Kombinationen

    1. mit Wiederholung und ohne Berücksichtigung der Reihenfolge

      $\displaystyle \left(\begin{array}{c}
n-1+k\\
k\end{array}\right)$

    2. ohne Wiederholung und ohne Berücksichtigung der Reihenfolge

      $\displaystyle \left(\begin{array}{c}
n\\
k\end{array}\right)$


Rechenregeln für Binomialkoeffizienten


Summenregel

$ S=\ \dot{\cup}_{i=1,\ldots,n}\ S_{i}\Rightarrow\left\vert S\right\vert=\sum_{i=1}^{n}\left\vert S_{i}\right\vert$

Man klassifiziere Elemente von $ S$ in sich gegenseitig ausschließende Eigenschaften.


Produktregel

$ S=S_{1}\times\ldots\times S_{n}\Rightarrow\left\vert S\right\vert=\prod_{i=1}^{n}\left\vert S_{i}\right\vert$


Gleichheit

$ S,T$ endliche Mengen. Falls es eine bijektive Abbildung von $ f:S\rightarrow T$ gibt, so gilt $ \left\vert S\right\vert=\left\vert T\right\vert$


Doppeltes Abzählen

$ S,T$ endliche Mengen, $ R\subseteq S\times T$. Für $ a\in S$ bezeichnet $ l\left(a\right)$ die Zahl der Elemente $ b\in T$ mit $ \left(a,b\right)\in R$ und entsprechend für $ b\in T$ sei $ r\left(b\right)$ die Zahl der Elemente $ a\in S$ mit $ \left(a,b\right)\in R$. Dann

$\displaystyle \left\vert R\right\vert=\sum_{a\in S}l\left(a\right)=\sum_{b\in T}r\left(b\right)$


Schubfachprinzip

$ S,T$ endliche Mengen, $ f:S\rightarrow T$ Abbildung. Falls $ \left\vert S\right\vert>\left\vert T\right\vert$, so ist $ f$ nicht injektiv.


next up previous contents index
Next: Permutationen Up: Kombinatorik Previous: Kombinatorik   Contents   Index
Marco Möller 17:26:01 24.10.2005