Kombinatorik

Anzahl Elemente in einer Menge

Für die Anzahl der Elemente einer Menge $A$ schreibe kurz: $n=\char93 A=\textrm{card}\left(A\right)$ (bzw. $n=\left\vert A\right\vert$)

Fakultät und Binomialkoeffizient

Wir schreiben für die Zahl $n$ dessen Fakultät mit $n!$. Wir definieren $0!=1$ und $\left(n+1\right)!=\left(n+1\right)n!=1*2*\ldots*\left(n+1\right)$.

Der Binomialkoeffizient $\left({{n\atop k}}\right)=\frac{n!}{k!\left(n-k\right)!}$, lies $n$ über $k$, ist definiert für alle $0\leq k\leq n$.

• ergibt im gesamten Definitionsbereich natürliche Zahlen
• $n!=\prod_{i=1}^{n}i$
• $\left({{n\atop k}}\right)+\left({{n\atop k+1}}\right)=\left({{n+1\atop k+1}}\right)$ für $0\leq k<n$
• $\sum_{k=0}^{n}\left({{n\atop k}}\right)=2^{n}$
• $\left({{n\atop k}}\right)=\left({{n\atop n-k}}\right)$
• $2^{n}\le n!$ für $n>3$
• $n!\le n^{n}$

Summen / Produktsymbol

Sind $a_{i},a_{i+1},\ldots,a_{n}$ Elemente eines Ringes. Dann setze das Summensymbol wie folgt:

$$\sum_{l=i}^{n}a_{l}=a_{i}+a_{i+1}+\ldots+a_{n}$$

Sind sie sogar Elemente eines kommutativen Ringes setzen wir das Produktsymbol wie folgt:

$$\prod_{l=i}^{n}a_{l}=a_{i}*a_{i+1}*\ldots*a_{n}$$

• Diese Zeichen binden ähnlich wie das Integralzeichen solange, wie nur Multiplikationen vorgenommen werden.
• $n!=\prod_{k=1}^{n}k$

Eigenschaften von Teilmengen

Sei $X$ eine $n$-elementige endliche Menge. Dann besitzt $X$ genau $2^{n}$ Teilmengen. Darunter sind genau $\left({{n\atop k}}\right)$ $k$-elementige Teilmengen.

Binomische Formel

Sind $a,b$ Elemente eines kommutativen Ringes, so gilt:

$$\left(a+b\right)^{n}=\sum_{k=0}^{n}\left({{n\atop k}}\right)a^{n-k}b^{k}$$

Geometische Summe

Sei $K$ ein Körper, $q\in K$ und $q\neq1$. Dann gilt:

$$\sum_{k=0}^{n}q^{k}=\frac{1-q^{n+1}}{1-q}$$

Wichtige Summen / Reihen

• $$\sum_{k=1}^{n}k=\frac{n\left(n+1\right)}{2}$$

• $$\sum_{k=1}^{n}k^{2}=\frac{n\left(n+1\right)\left(2n+1\right)}{6}$$

• $$\sum_{k=1}^{n}\frac{1}{k\left(k+1\right)}=\frac{n}{n+1}=1-\frac{1}{n+1}$$

Fast alle

Eine Aussage gilt für fast alle natürlichen Zahlen, wenn sie nur endlich viele Ausnahmen hat.