\documentclass[12pt]{article}

\usepackage{ngerman,a4}
\usepackage{amstext}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{stmaryrd}
\usepackage{enumerate}
\usepackage{alltt}
\usepackage[latin1]{inputenc}
%\usepackage{graphicx}

\thispagestyle{empty}

\title{}
\author{}
\date{}

\begin{document}

\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\newcommand{\SetZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\SetQ}{\ensuremath{\mathbb{Q}}}
\newcommand{\SetB}{\ensuremath{\mathbb{B}}}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}
\newcommand{\FLASH}{\ensuremath{\hspace*{\fill}\lightning}}
\newcommand{\OnotO}{\ensuremath{\mathcal{O}}}
\newcommand{\bild}[4]{
	\begin{figure}[htpb]
		\centering
			\includegraphics[width=#1cm]{../#2}\\[0.2cm]
			\caption{#3}
			\label{#4}
	\end{figure}
	}

\noindent §63: ERZEUGENDE FUNKTIONEN \\[0.8cm]
63.1 Motivation \\
Erzeugende Funktionen wirken auf den ersten Blick etwas abstrakt, aber sie sind ein wichtiges Werkzeug, um kombinatorische Probleme systematischer und eleganter zu lösen. Sie sind zudem in verschiedenen anderen Gebieten der Stochastik nützlich. \\[0.5cm]
63.2 Permutationen und Kombinationen \\
Im §62 haben wir geordnete und ungeordnete $k$-elementige Stichproben einer $n$-elementigen Menge betrachtet. Im geordneten Fall nennt man eine solche Stichprobe auch $k$-Permutation, im ungeordneten Fall eine $k$-Kombination. \\[0.5cm]
63.3 Beispiel einer erzeugenden Funktion \\
Nach dem Binomialsatz 19.7 gilt:
$$(x+1)^n = \sum_{k=0}^n {n \choose k} x^k \cdot 1^{n-k} = \sum_{k=0}^n {n \choose k} x^k$$
Der Koeffizient ${n \choose k}$ von $x^k$ beschreibt die Zahl der $k$-Kombinationen einer $n$-elementigen Menge ohne Wiederholungen (vgl. 62.4(c)). \\
In den Koeffizienten der Funtion
$$f(x) = (x+1)^n = {n \choose 0} x^0 + {n \choose 1} x^1 + ... + {n \choose n} x^n$$
stecken somit alle Informationen über dieses kombinatorische Problem. Dies motiviert folgende Definition: \\[0.5cm]
63.4 Def.: \\
Eine Funktion $f$ mit $$f(x) = \sum_{k=0}^n a_k x^k$$ heißt erzeugende Funktion für die Koeffizienten $a_k \; \; (k=0,...,n)$. \\
Lassen sich die Zahlen $a_k$ mit einem kombinatorischen Problem identifizieren, so nennen wir $f$ die erzeugende Funktion für dieses Problem. \\[0.5cm]
63.5 Beispiel: \\
$f(x) = (1+x)^n$ ist die erzeugende Funktion der Kombinationen ohne Wiederholung einer $n$-elementigen Menge. \\
Schubladeninterpretation: \\
Jeder der $n$ Faktoren $(1+x)$ wird als Schublade aufgefasst, in der sich $0$ oder $1$ Element befindet. Wählt man beim Ausmultiplizieren von $(1+x)$ den Faktor $1$, bleibt die Schublade leer. Wählt man $x$, wird sie mit einem Element besetzt. \\
Beispielsweise beschreibt
$$f(x) = (1+x)^3 = 1 + 3x + 3x^2 + x^3$$
alle Kombinationen, 0,1,2 oder 3 Elemente auf 3 Schubladen zu verteilen. Dabei bedeuten die einzelnen Summanden:
\begin{eqnarray*}
	1 & = & 1 \cdot 1 \cdot 1 \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \; \text{1 Möglichkeit bei 0 Elementen} \\
	3x & = & x \cdot 1 \cdot 1 + 1 \cdot x \cdot 1 + 1 \cdot 1 \cdot x \quad \quad \text{3 Möglichkeiten bei 1 Element} \\
	3x^2 & = & x \cdot x \cdot 1 + x \cdot 1 \cdot x + 1 \cdot x \cdot x \quad \quad \text{3 Möglichkeiten bei 2 Elementen} \\
	x^3 & = & x \cdot x \cdot x \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \; \text{1 Möglichkeit bei 3 Elementen}
\end{eqnarray*}
Wie verallgemeinert man dieses Prinzip, wenn die Schubladen mit mehreren Objekten besetzt werden sollen? \\[0.5cm]
63.6 Beispiel \\
Lassen wir pro Schublade bis zu zwei Objekte zu (die sich wiederholen dürfen), lautet der Faktor $(1+x+x^2)$ statt $(1+x)$. \\
Z.B. können wir die Anzahl der Kombinationen mit Wiederholung einer 2-elementigen Menge bestimmen, wenn jedes Element 0-, 1- oder 2-mal ausgewählt werden kann. Erzeugende Funktionen:
\begin{eqnarray*}
	f(x) & = & (1+x+x^2)^2 \\
	& = & (1+x+x^2)(1+x+x^2) \\
	& = & 1 \cdot 1 + 1 \cdot x + 1 \cdot x^2 + x \cdot 1 + x \cdot x + x \cdot x^2 + x^2 \cdot 1 + x^2 \cdot x + x^2 \cdot x^2 \\
	& = & 1 + 2x + 3x^2 + 2x^3 + x^4
\end{eqnarray*}
Es gibt 1 Möglichkeit, 0 Objekte zu wählen. \\
Es gibt 2 Möglichkeiten, 1 Objekte zu wählen. \\
Es gibt 3 Möglichkeiten, 2 Objekte zu wählen. \\
Es gibt 2 Möglichkeiten, 3 Objekte zu wählen. \\
Es gibt 1 Möglichkeit, 4 Objekte zu wählen. \\
Man kann sogar für die unterschiedlichen Elemente verschiedene Beschränkungen einführen: \\[0.5cm]
63.7 Beispiel \\
Bestimme die Kombinationen einer 4-elementigen Menge $\{x_1,...,x_4\}$ mit den folgenden Beschränkungen:
\begin{center}
\begin{tabular}{c|c|c}
	Element & Beschränkung & Polynom \\ \hline
	$x_1$ & 0-, 1- oder 3-mal & $1+x+x^3$ \\ \hline
	$x_2$ & 1- oder 2-mal & $x+x^2$ \\ \hline
	$x_3$ & 1-mal & $x$ \\ \hline
	$x_4$ & 0- oder 4-mal & $1+x^4$
\end{tabular}
\end{center}
erzeugende Funktion:
\begin{eqnarray*}
	f(x) & = & (1+x+x^3) \cdot (x+x^2) \cdot x \cdot (1+x^4) \\
	& = & ... \\
	& = & x^2 + 2x^3 + x^4 + x^5 + 2x^6 + 2x^7 + x^8 + x^9 + x^{10}
\end{eqnarray*}
Es gibt also z.B. zwei 6-Kombinationen. \\
Diese Beispiele motivieren: \\[0.5cm]
63.8 Satz: (Kombinationen mit vorgegebenen Wiederholungen) \\
Die erzeugende Funktion der kombinationen mit Wiederholung aus einer $n$-elementigen Menge $\{x_1,...,x_n\}$, in der $x_i$ in den Anzahlen $v_1^{(i)}, ..., v_{k_i}^{(i)}$ auftreten darf, lautet
$$f(x) = \prod_{i=1}^n \left(x^{v_1^{(i)}} + x^{v_2^{(i)}} + ... + x^{v_{k_i}^{(i)}}\right)$$
Bemerkung: \\
Läßt man beliebige Wiederholungen zu, erhält man mit
$$1 + x + x^2 + x^3 + ... = \sum_{k=0}^\infty x^k = \frac{1}{1-x} \quad \text{(für } |x| < 1 \text{)}$$
den folgenden Satz: \\[0.5cm]
63.9 Satz: (Kombinationen mit beliebigen Wiederholungen) \\
Die erzeugende Funktion der Kombinationen mit beliebigen Wiederholungen von $n$ Elementen lautet:
$$f(x) = \frac{1}{(1-x)^n} = (1+x+x^2+...)^n$$
63.10 Bemerkungen:
\begin{enumerate}[(a)]
	\item Die gesuchten Koeffizienten vor $x^k, k \in \SetN_0$ ergeben sich durch eine formale Potenzreihenentwicklung. Dabei kann man Konvergenzbetrachtungen ignorieren, da man z.B. $|x|<1$ annehmen darf.
	\item Muss jedes Element mindestens $p$-mal auftreten, ergibt sich wegen
	$$x^p + x^{p+1} + x^{p+2} + ... = x^p \sum_{k=0}^\infty x^k = \frac{x^p}{1-x}$$
	die erzeugende Funktion
	$$f(x) = \frac{x^{np}}{(1-x)^n}$$
\end{enumerate}
Bisher haben wir nur Kombinationen betrachtet. Sind erzeugende Funktionen auch bei Permutationen nützlich? \\
Hierzu müssen wir den Begriff der erzeugenden Funktion modifizieren. \\[0.5cm]
63.11 Def.: \\
Eine Funktion $f$ mit $$f(x) = \sum_{k=0}^n a_k \frac{x^k}{k!}$$ heißt exponentiell erzeugende Funktion für die Koeffizienten $a_k$. \\
Bemerkung: \\
Der Name wird motiviert durch die Exponentialreihe
$$e^x = \sum_{k=0}^n \frac{x^k}{k!}$$
63.12 Bedeutung für Permutationen \\
Nach 62.4 (b) gibt es bei einer $n$-elementigen Menge
$$n \cdot (n-1) \cdot ... \cdot (n-k+1) = \frac{n!}{(n-k)!}$$
$k$-Permutationen ohne Wiederholung. Wegen
$$(x+1)^n = \sum_{k=0}^n {n \choose k} x^k = \sum_{k=0}^n \frac{n!}{(n-k)!k!} x^k = \sum_{k=0}^n \frac{n!}{(n-k)!} \cdot \frac{x^k}{k!}$$
sind dies die Koeffizienten der exponentiell erzeugenden Funktion
$$f(x) = (1+x)^n$$
Die exponentiell erzeugende Funktion spielt also bei Permutationen die gleiche Rolle wie die erzeugende Funktion bei Kombinationen. \\
Das Analogon zu Satz 63.8 lautet: \\[0.5cm]
63.13 Satz: (Permutationen mit vorgegebenen Wiederholungen) \\
Die exponentiell erzeugende Funktion der Permutationen mit Wiederholung aus einer $n$-elementigen Menge $\{x_1,...,x_n\}$, in der $x_i$ in den Anzahlen $v_1^{(i)}, ..., v_{k_i}^{(i)}$ auftreten darf, lautet
$$\prod_{i=1}^n \left(\frac{x^{v_1^{(i)}}}{v_1^{(i)}!} + \frac{x^{v_2^{(i)}}}{v_2^{(i)}!} + ... + \frac{x^{v_{k_i}^{(i)}}}{v_{k_i}^{(i)}!} \right)$$
Läßt man beliebige Wiederholungen zu, folgt mit
$$1 + \frac{x}{1!} + \frac{x^2}{2!} + \frac{x^3}{3!} + ... = \sum_{k=0}^\infty \frac{x^k}{k!} = e^x$$
das Analogon zu Satz 63.9: \\[0.5cm]
63.14 Satz: (Permutationen mit beliebigen Wiederholungen) \\
Die exponentiell erzeugende Funktion der Permutationen mit beliebigen Wiederholungen von $n$ Elementen lautet:
$$f(x) = e^{nx} = (e^x)^n = \left(1 + \frac{x}{1!} + \frac{x^2}{2!} + ...\right)^n$$

\end{document}
