\documentclass
[numbers=enddot,12pt,final,onecolumn,notitlepage,german]{scrartcl}%
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[ngerman]{babel}
\usepackage[all,cmtip]{xy}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{comment}
\usepackage{color}
\usepackage[breaklinks=True]{hyperref}
\usepackage[sc]{mathpazo}
\usepackage[T1]{fontenc}
\usepackage{tikz}
\usepackage{needspace}
\usepackage{tabls}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Tuesday, June 28, 2022 12:26:23}
%TCIDATA{SuppressPackageManagement}
%TCIDATA{}
%TCIDATA{}
%TCIDATA{BibliographyScheme=Manual}
%TCIDATA{Language=American English}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\usetikzlibrary{arrows}
\newcounter{exer}
\theoremstyle{definition}
\newtheorem{theo}{Satz}[section]
\newenvironment{theorem}[1][]
{\begin{theo}[#1]\begin{leftbar}}
{\end{leftbar}\end{theo}}
\newtheorem{lem}[theo]{Lemma}
\newenvironment{lemma}[1][]
{\begin{lem}[#1]\begin{leftbar}}
{\end{leftbar}\end{lem}}
\newtheorem{prop}[theo]{Proposition}
\newenvironment{proposition}[1][]
{\begin{prop}[#1]\begin{leftbar}}
{\end{leftbar}\end{prop}}
\newtheorem{defi}[theo]{Definition}
\newenvironment{definition}[1][]
{\begin{defi}[#1]\begin{leftbar}}
{\end{leftbar}\end{defi}}
\newtheorem{remk}[theo]{Bemerkung}
\newenvironment{remark}[1][]
{\begin{remk}[#1]\begin{leftbar}}
{\end{leftbar}\end{remk}}
\newtheorem{coro}[theo]{Folgerung}
\newenvironment{corollary}[1][]
{\begin{coro}[#1]\begin{leftbar}}
{\end{leftbar}\end{coro}}
\newtheorem{conv}[theo]{Konvention}
\newenvironment{convention}[1][]
{\begin{conv}[#1]\begin{leftbar}}
{\end{leftbar}\end{conv}}
\newtheorem{quest}[theo]{Frage}
\newenvironment{question}[1][]
{\begin{quest}[#1]\begin{leftbar}}
{\end{leftbar}\end{quest}}
\newtheorem{warn}[theo]{Warnung}
\newenvironment{conclusion}[1][]
{\begin{warn}[#1]\begin{leftbar}}
{\end{leftbar}\end{warn}}
\newtheorem{conj}[theo]{Vermutung}
\newenvironment{conjecture}[1][]
{\begin{conj}[#1]\begin{leftbar}}
{\end{leftbar}\end{conj}}
\newtheorem{exam}[theo]{Beispiel}
\newenvironment{example}[1][]
{\begin{exam}[#1]\begin{leftbar}}
{\end{leftbar}\end{exam}}
\newtheorem{exmp}[exer]{Aufgabe}
\newenvironment{exercise}[1][]
{\begin{exmp}[#1]\begin{leftbar}}
{\end{leftbar}\end{exmp}}
\newtheorem{aufg}[exer]{Aufgabe}
\newenvironment{aufgabe}[1][]
{\begin{aufg}[#1]\begin{leftbar}}
{\end{leftbar}\end{aufg}}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\newenvironment{fineprint}{\begin{small}}{\end{small}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\newenvironment{convention}[1][Convention]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\newenvironment{question}[1][Question]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\newenvironment{aufgabe}[1][Aufgabe]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\let\cupnonlimits\bigcup
\let\capnonlimits\bigcap
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\renewcommand{\bigcup}{\cupnonlimits\limits}
\renewcommand{\bigcap}{\capnonlimits\limits}
\setlength\tablinesep{3pt}
\setlength\arraylinesep{3pt}
\setlength\extrarulesep{3pt}
\setlength\textheight{22.5cm}
\setlength\textwidth{14.8cm}
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\newcommand{\defn}[1]{{\color{darkred}\emph{#1}}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\KK}{\mathbb{K}}
\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\abs}[1]{\left| #1 \right|}
\newcommand{\tup}[1]{\left( #1 \right)}
\newcommand{\ive}[1]{\left[ #1 \right]}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\newtheoremstyle{plainsl}
{8pt plus 2pt minus 4pt}
{8pt plus 2pt minus 4pt}
{\slshape}
{0pt}
{\bfseries}
{.}
{5pt plus 1pt minus 1pt}
{}
\theoremstyle{plainsl}
\ihead{Aufgabenblatt Alternierende Summen}
\ohead{Seite \thepage}
\cfoot{}
\begin{document}
\title{Alternierende Summen: Aufgaben und L\"{o}sungen}
\author{Darij Grinberg}
\date{\today\ \footnote{Eine aktuelle Version dieses Aufgabenblattes kann auf
\url{https://www.cip.ifi.lmu.de/~grinberg/algebra/aimo2020-altsum-lsg.pdf}
heruntergeladen werden.}}
\maketitle
\begin{abstract}
(Aufgabenblatt f\"{u}r IMO-Training 2020 Deutschland)
\end{abstract}
\tableofcontents
\section*{***}
Dieses Aufgabenblatt handelt von alternierenden (und generell
vorzeichenbehafteten) Summen in der Kombinatorik, und allgemeiner von
Differenzen, K\"{u}rzungen und \textquotedblleft destruktiver
Interferenz\textquotedblright. Die Prototyp-Aufgaben zeigen einige Strategien
auf, die es erm\"{o}glichen, solche Summen zu berechnen oder anzuwenden; in
den sp\"{a}teren Aufgaben kommen diese Strategien dann zum Zug (wobei oft auch
andere L\"{o}sungen existieren).
\section{\label{sec.bas}Basics \"{u}ber Binomialkoeffizienten}
Im Folgenden sei $\mathbb{N}=\left\{ 0,1,2,\ldots\right\} $.
Der Allgemeinheit halber werden wir \"{o}fters mit komplexen Zahlen arbeiten.
Wirklich n\"{o}tig sind sie uns aber nicht; wer mit ihnen unerfahren ist, kann
sie daher durch reelle Zahlen (oder gar durch rationale Zahlen) ersetzt
denken, und dementsprechend immer $\mathbb{R}$ (oder $\mathbb{Q}$) statt
$\mathbb{C}$ lesen.
Wir erinnern uns an die Definition der Binomialkoeffizienten: F\"{u}r alle
$n,k\in\mathbb{C}$ setzt man%
\begin{equation}
\dbinom{n}{k}=%
\begin{cases}
\dfrac{n\left( n-1\right) \left( n-2\right) \cdots\left( n-k+1\right)
}{k!}, & \text{wenn }k\in\mathbb{N};\\
0, & \text{wenn }k\notin\mathbb{N}.
\end{cases}
\label{eq.binom.def}%
\end{equation}
Beispielsweise gilt%
\begin{align*}
\dbinom{n}{0} & =1\ \ \ \ \ \ \ \ \ \ \text{und}\ \ \ \ \ \ \ \ \ \ \dbinom
{n}{1}=n\ \ \ \ \ \ \ \ \ \ \text{und}\\
\dbinom{n}{2} & =\dfrac{n\left( n-1\right) }{2}%
\ \ \ \ \ \ \ \ \ \ \text{und}\ \ \ \ \ \ \ \ \ \ \dbinom{n}{-1}=0
\end{align*}
f\"{u}r alle $n\in\mathbb{C}$. (Man beachte: $\dbinom{1/2}{2}=\dfrac{\left(
1/2\right) \left( 1/2-1\right) }{2}=-\dfrac{1}{8}$ aber $\dbinom{2}{1/2}=0$
wegen $1/2\notin\mathbb{N}$.)
Bekannte Eigenschaften von Binomialkoeffizienten sind\footnote{Beweise, falls
unbekannt, sind \"{U}bungsaufgaben!}:
\begin{itemize}
\item \textbf{(Nullen rechts vom Pascalschen Dreieck)}%
\begin{equation}
\dbinom{n}{k}=0\ \ \ \ \ \ \ \ \ \ \text{f\"{u}r alle }n\in\mathbb{N}\text{
und }k\in\mathbb{C}\text{ mit }k>n. \label{eq.binom.0rechts}%
\end{equation}
(Achtung: Dies gilt nicht f\"{u}r negative oder nicht-ganze $n$.)
\item \textbf{(Rekursion)}
\begin{equation}
\dbinom{n}{k}=\dbinom{n-1}{k-1}+\dbinom{n-1}{k}%
\ \ \ \ \ \ \ \ \ \ \text{f\"{u}r alle }n,k\in\mathbb{C}. \label{eq.binom.rec}%
\end{equation}
\item \textbf{(Minus-eins-Potenzen)}
\begin{equation}
\dbinom{-1}{k}=\left( -1\right) ^{k}\ \ \ \ \ \ \ \ \ \ \text{f\"{u}r alle
}k\in\mathbb{N}\text{.} \label{eq.bas.-1choosek}%
\end{equation}
\item \textbf{(Upper Negation)}
\[
\dbinom{-n}{k}=\left( -1\right) ^{k}\dbinom{n+k-1}{k}%
\ \ \ \ \ \ \ \ \ \ \text{f\"{u}r alle }n\in\mathbb{C}\text{ und }%
k\in\mathbb{Z}.
\]
\item \textbf{(Fakult\"{a}tenformel)}%
\[
\dbinom{n}{k}=\dfrac{n!}{k!\cdot\left( n-k\right) !}%
\ \ \ \ \ \ \ \ \ \ \text{f\"{u}r alle }n,k\in\mathbb{N}\text{ mit }n\geq k.
\]
(Achtung: Die Voraussetzungen $n,k\in\mathbb{N}$ und $n\geq k$ sind wirklich
n\"{o}tig; sonst ist die Formel nicht einmal sinnvoll. Daher ist die Formel
kein Ersatz f\"{u}r (\ref{eq.binom.def}).)
\item \textbf{(Symmetrie)}%
\begin{equation}
\dbinom{n}{k}=\dbinom{n}{n-k}\ \ \ \ \ \ \ \ \ \ \text{f\"{u}r alle }%
n\in\mathbb{N}\text{ und }k\in\mathbb{C}. \label{eq.bas.symmetry}%
\end{equation}
(Achtung: Dies gilt nur f\"{u}r $n\in\mathbb{N}$. Die Missanwendung auf
negative $n$ ist eine h\"{a}ufige Fehlerquelle.)
\item \textbf{(Rechter Rand des Pascalschen Dreiecks)}
\begin{equation}
\dbinom{n}{n}=1\ \ \ \ \ \ \ \ \ \ \text{f\"{u}r alle }n\in\mathbb{N}.
\label{eq.bas.rechter-rand}%
\end{equation}
(Achtung: Im Gegensatz zu $\dbinom{n}{0}=1$ gilt dies nur f\"{u}r
$n\in\mathbb{N}$.)
\item \textbf{(Kombinatorische Interpretation)} Ist $S$ eine $n$-elementige
Menge (mit $n\in\mathbb{N}$), und ist $k\in\mathbb{C}$, dann ist
\[
\dbinom{n}{k}=\left( \text{Anzahl aller }k\text{-elementigen Teilmengen von
}S\right) .
\]
(Achtung: Dies sagt nichts \"{u}ber $\dbinom{n}{k}$ f\"{u}r negatives $n$ aus,
und schon gar nichts \"{u}ber $\dbinom{-1/2}{k}$.)
\item \textbf{(Polynomialit\"{a}t)} F\"{u}r jedes feste $k\in\mathbb{N}$ ist
die Funktion $\dbinom{n}{k}$ (als Funktion von $n$) eine Polynomfunktion vom
Grad $k$. (Aber f\"{u}r festes $n$ ist $\dbinom{n}{k}$ im Allgemeinen keine
Polynomfunktion in $k$.)
\item \textbf{(Ganzzahligkeit)}
\[
\dbinom{n}{k}\in\mathbb{Z}\ \ \ \ \ \ \ \ \ \ \text{f\"{u}r alle }%
n\in\mathbb{Z}\text{ und }k\in\mathbb{C}.
\]
\item \textbf{(Primzahlteilbarkeit, einfachste Form)} Ist $p$ eine Primzahl,
dann ist $p\mid\dbinom{p}{k}$ f\"{u}r alle $k\in\left\{ 1,2,\ldots
,p-1\right\} $.
\item \textbf{(Binomischer Satz)} F\"{u}r alle $x,y\in\mathbb{C}$ und alle
$n\in\mathbb{N}$ gilt
\[
\left( x+y\right) ^{n}=\sum_{k=0}^{n}\dbinom{n}{k}x^{k}y^{n-k}.
\]
(Dies gilt noch allgemeiner, wenn $x$ und $y$ zwei kommutierende Elemente
eines Ringes sind -- z.B. zwei kommutierende $m\times m$-Matrizen.)
\item \textbf{(Hockeystick-Identit\"{a}t)}
\[
\dbinom{0}{k}+\dbinom{1}{k}+\dbinom{2}{k}+\cdots+\dbinom{n}{k}=\dbinom
{n+1}{k+1}\ \ \ \ \ \ \ \ \ \ \text{f\"{u}r alle }n,k\in\mathbb{N}.
\]
(Die ersten $k$ Summanden auf der linken Seite sind $0$ und k\"{o}nnen daher
weggelassen werden.)
\item \textbf{(Fibonacci via Binomialkoeffizienten)}
\[
f_{n+1}=\sum_{k=0}^{n}\dbinom{n-k}{k}\ \ \ \ \ \ \ \ \ \ \text{f\"{u}r alle
ganzen Zahlen }n\geq-1,
\]
wobei $\left( f_{0},f_{1},f_{2},\ldots\right) $ die Fibonaccifolge ist (mit
$f_{0}=0$, $f_{1}=1$ und $f_{n}=f_{n-1}+f_{n-2}$ f\"{u}r alle $n\geq2$). (Auch
hier kann man viele Summanden weglassen, denn $\dbinom{n-k}{k}=0$ f\"{u}r alle
$k$ mit $n/21$ eine feste
ganze Zahl ist). Mangels brauchbarer Information geschieht dies dadurch, dass
jeder B\"{u}rger zuf\"{a}llig (gleichverteilt und unabh\"{a}ngig von den
anderen B\"{u}rgern) einen der $n-1$ anderen B\"{u}rger beschuldigt. Zeige:
Die Wahrscheinlichkeit, dass keine zwei B\"{u}rger sich gegenseitig
beschuldigen, ist%
\[
\sum_{k=0}^{n}\left( -1\right) ^{k}\dfrac{n\left( n-1\right) \cdots\left(
n-2k+1\right) }{\left( n-1\right) ^{2k}\cdot2^{k}\cdot k!}.
\]
\end{aufgabe}
\begin{aufgabe}
\label{aufg.pie-dan}Sei $n\in\mathbb{N}$, und sei $U$ eine endliche Menge.
Seien $A_{1},A_{2},\ldots,A_{n}$ Teilmengen von $U$. Sei $k\in\mathbb{N}$. Sei
$S_{k}$ die Menge aller Elemente von $U$, die in genau $k$ der $n$ Teilmengen
$A_{1},A_{2},\ldots,A_{n}$ enthalten sind. (Mit anderen Worten: Sei
$S_{k}=\left\{ s\in U\ \mid\ \text{die Anzahl aller }i\in\left[ n\right]
\text{ mit }s\in A_{i}\text{ ist }k\right\} $.) Zeige:%
\[
\left\vert S_{k}\right\vert =\sum_{I\subseteq\left[ n\right] }\left(
-1\right) ^{\left\vert I\right\vert -k}\dbinom{\left\vert I\right\vert }%
{k}\left\vert \bigcap_{i\in I}A_{i}\right\vert .
\]
Hierbei ist wieder der \textquotedblleft leere\textquotedblright\ Durchschnitt
$\bigcap_{i\in\varnothing}A_{i}$ als die gesamte Menge $U$ zu verstehen.
\end{aufgabe}
\begin{aufgabe}
\label{aufg.pie-bon}Sei $n\in\mathbb{N}$, und sei $U$ eine endliche Menge.
Seien $A_{1},A_{2},\ldots,A_{n}$ Teilmengen von $U$. Sei $m\in\mathbb{N}$.
\begin{enumerate}
\item[\textbf{(a)}] F\"{u}r jedes $s\in U$ sei $c\left( s\right) $ die
Anzahl aller $i\in\left[ n\right] $ mit $s\in A_{i}$. Zeige:%
\[
\sum_{\substack{I\subseteq\left[ n\right] ;\\\left\vert I\right\vert \leq
m}}\left( -1\right) ^{\left\vert I\right\vert }\left\vert \bigcap_{i\in
I}A_{i}\right\vert =\left( -1\right) ^{m}\sum_{s\in U}\dbinom{c\left(
s\right) -1}{m}.
\]
Hierbei ist der \textquotedblleft leere\textquotedblright\ Durchschnitt
$\bigcap_{i\in\varnothing}A_{i}$ als die gesamte Menge $U$ zu verstehen.
\item[\textbf{(b)}] (\textit{Bonferroni-Ungleichungen}) Folgere, dass
$\sum_{\substack{I\subseteq\left[ n\right] ;\\\left\vert I\right\vert \leq
m}}\left( -1\right) ^{m-\left\vert I\right\vert }\left\vert \bigcap_{i\in
I}A_{i}\right\vert \geq0$ ist, falls $U=A_{1}\cup A_{2}\cup\cdots\cup A_{n}$ gilt.
\end{enumerate}
\end{aufgabe}
\begin{aufgabe}
\label{aufg.pie-dan-bon}Verallgemeinere Aufgabe \ref{aufg.pie-bon}
\textbf{(a)} und Aufgabe \ref{aufg.pie-dan} gleichzeitig zu einer Formel der
Art
\[
\sum_{\substack{I\subseteq\left[ n\right] ;\\\left\vert I\right\vert \leq
m}}\left( -1\right) ^{\left\vert I\right\vert }\dbinom{\left\vert
I\right\vert }{k}\left\vert \bigcap_{i\in I}A_{i}\right\vert =\sum_{s\in
U}\ \ \ \underbrace{\cdots}_{\text{ein Ausdruck mit }c\left( s\right) }.
\]
\end{aufgabe}
\begin{aufgabe}
\label{aufg.pie-max}Sei $n$ eine positive ganze Zahl. Seien $a_{1}%
,a_{2},\ldots,a_{n}$ beliebige $n$ ganze Zahlen.
\begin{enumerate}
\item[\textbf{(a)}] Zeige, dass%
\[
\max\left\{ a_{1},a_{2},\ldots,a_{n}\right\} =\sum_{k=1}^{n}\left(
-1\right) ^{k-1}\sum_{1\leq i_{1}\left( p-1\right) m$ eine ganze Zahl. Seien $a_{1},a_{2},\ldots
,a_{n}$ irgendwelche $n$ Vektoren im $\mathbb{F}_{p}$-Vektorraum
$\mathbb{F}_{p}^{m}$. Man zeige, dass es eine nichtleere Teilmenge $T$ von
$\left[ n\right] $ gibt mit $\sum_{t\in T}a_{t}=0$ (Nullvektor).
[\textbf{Hinweis:} Schreibe jeden Vektor $a_{t}$ als $a_{t}=\left(
a_{t,1},a_{t,2},\ldots,a_{t,m}\right) ^{T}$, und betrachte das Polynom%
\[
P\left( x_{1},x_{2},\ldots,x_{n}\right) =\prod_{j=1}^{m}\left( 1-\left(
\sum_{t=1}^{n}a_{t,j}x_{t}\right) ^{p-1}\right)
\]
\"{u}ber $\mathbb{F}_{p}$.]
\end{aufgabe}
\begin{aufgabe}
\label{aufg.polariz}(\textit{Polarisationsformeln}) Sei $n\in\mathbb{N}$.
Seien $v_{1},v_{2},\ldots,v_{n}\in\mathbb{C}$ sowie $w\in\mathbb{C}$. Zeige:
\begin{enumerate}
\item[\textbf{(a)}] F\"{u}r jedes $m\in\left\{ 0,1,\ldots,n-1\right\} $ gilt%
\[
\sum_{I\subseteq\left[ n\right] }\left( -1\right) ^{n-\left\vert
I\right\vert }\left( w+\sum_{i\in I}v_{i}\right) ^{m}=0.
\]
\item[\textbf{(b)}] Es gilt%
\[
\sum_{I\subseteq\left[ n\right] }\left( -1\right) ^{n-\left\vert
I\right\vert }\left( w+\sum_{i\in I}v_{i}\right) ^{n}=n!v_{1}v_{2}\cdots
v_{n}.
\]
\item[\textbf{(c)}] Es gilt%
\[
\sum_{I\subseteq\left[ n\right] }\left( -1\right) ^{n-\left\vert
I\right\vert }\left( \sum_{i\in I}v_{i}-\sum_{i\in\left[ n\right] \setminus
I}v_{i}\right) ^{n}=2^{n}n!v_{1}v_{2}\cdots v_{n}.
\]
\end{enumerate}
\end{aufgabe}
\begin{aufgabe}
\label{aufg.stirl.powersum}Sei $m\in\mathbb{N}$. F\"{u}r jedes $n\in
\mathbb{N}$ sei $\operatorname*{sur}\left( m,n\right) $ die Anzahl aller
surjektiven Abbildungen von $\left[ m\right] $ nach $\left[ n\right] $.
(Siehe Aufgabe \ref{aufg.pie-prot} \textbf{(d)} f\"{u}r eine Formel f\"{u}r
$\operatorname*{sur}\left( m,n\right) $. Man bemerke, dass
$\operatorname*{sur}\left( m,n\right) /n!$ auch als die zweite Stirlingzahl
$%
%TCIMACRO{\QDATOPD{\{}{\}}{m}{n}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{m}{n}%
%EndExpansion
$ bekannt ist.)
\begin{enumerate}
\item[\textbf{(a)}] Zeige, dass
\[
k^{m}=\sum_{i=0}^{m}\operatorname*{sur}\left( m,i\right) \cdot\dbinom{k}%
{i}\ \ \ \ \ \ \ \ \ \ \text{f\"{u}r alle }k\in\mathbb{C}\text{ gilt.}%
\]
\item[\textbf{(b)}] Zeige, dass
\[
0^{m}+1^{m}+\cdots+n^{m}=\sum_{i=0}^{m}\operatorname*{sur}\left( m,i\right)
\cdot\dbinom{n+1}{i+1}\ \ \ \ \ \ \ \ \ \ \text{f\"{u}r alle }n\in
\mathbb{N}\text{ gilt.}%
\]
(Wenn $m$ fest gew\"{a}hlt ist, ist dies eine explizite Formel f\"{u}r
$0^{m}+1^{m}+\cdots+n^{m}$, da rechts nur $m+1$ Summanden stehen.)
\item[\textbf{(c)}] Zeige, dass%
\[
\left( -1\right) ^{m}=\sum_{i=0}^{m}\left( -1\right) ^{i}%
\operatorname*{sur}\left( m,i\right) \ \ \ \ \ \ \ \ \ \ \text{gilt.}%
\]
\end{enumerate}
\end{aufgabe}
\begin{noncompile}
Seien $x\in\mathbb{C}$ und $n\in\mathbb{N}$. Man zeige:
\[
\sum_{k=0}^{n}\left( -1\right) ^{k}\dbinom{x}{k}\dbinom{x}{n-k}=%
\begin{cases}
\left( -1\right) ^{n/2}\dbinom{x}{n/2}, & \text{wenn }n\text{ gerade ist;}\\
0, & \text{wenn }n\text{ ungerade ist.}%
\end{cases}
\]
\end{noncompile}
\begin{aufgabe}
\label{aufg.ZmnZnm}F\"{u}r alle $m,n\in\mathbb{N}$ definieren wir ein Polynom
$Z_{m,n}\left( x\right) $ durch%
\[
Z_{m,n}\left( x\right) =\sum_{k=0}^{n}\left( -1\right) ^{k}\dbinom{n}%
{k}\left( x^{n-k}-1\right) ^{m}.
\]
Man zeige: $Z_{m,n}\left( x\right) =Z_{n,m}\left( x\right) $ f\"{u}r alle
$m,n\in\mathbb{N}$.
\end{aufgabe}
\begin{aufgabe}
\label{aufg.polynom0}Sei $n$ eine positive ganze Zahl. Sei $P$ ein Polynom in
$n$ Variablen $x_{1},x_{2},\ldots,x_{n}$ mit $\deg P\sigma\left( j\right) $.
(So hat die Permutation von $\left[ 3\right] $, die $1,2,3$ auf $2,3,1$
abbildet, genau $2$ Inversionen, n\"{a}mlich $\left( 1,3\right) $ und
$\left( 2,3\right) $.)
Eine Permutation von $\left[ n\right] $ hei\ss t \textit{gerade}, wenn sie
gerade viele Inversionen hat, und \textit{ungerade}, wenn sie ungerade viele
Inversionen hat.
Zeige: F\"{u}r $n>1$ gilt%
\begin{align*}
& \left( \text{die Anzahl aller geraden Permutationen von }\left[ n\right]
\right) \\
& =\left( \text{die Anzahl aller ungeraden Permutationen von }\left[
n\right] \right) =n!/2.
\end{align*}
\end{aufgabe}
\begin{aufgabe}
\label{aufg.cgmo2020-gerade}(China Girls Math Olympiad 2020)
Sei $n$ eine positive ganze Zahl. Eine \textit{Komposition} von $n$ ist ein
Tupel $\left( a_{1},a_{2},\ldots,a_{m}\right) $ von positiven ganzen Zahlen
mit $a_{1}+a_{2}+\cdots+a_{m}=n$.
Die \textit{Inversionen} einer Komposition $\left( a_{1},a_{2},\ldots
,a_{m}\right) $ von $n$ sind die Paare $\left( i,j\right) \in\left[
m\right] ^{2}$ mit $ia_{j}$.
Man berechne die Anzahl aller Kompositionen von $n$, die gerade viele
Inversionen haben.
\end{aufgabe}
\begin{aufgabe}
\label{aufg.bipartit-ncatlab}Sei $G=\left( V,E\right) $ ein bipartiter
Graph, und seien $A$ und $B$ die zwei Komponenten der Knotenmenge von $G$.
(Das hei\ss t, $V=A\cup B$ und $A\cap B=\varnothing$; und jede Kante von $G$
verbindet einen Knoten in $A$ mit einem Knoten in $B$.) F\"{u}r jede Teilmenge
$S$ von $V$ sei $N\left( S\right) $ die Menge aller Knoten von $G$, die mit
mindestens einem Knoten in $S$ verbunden sind. Man zeige:%
\[
\sum_{X\subseteq A}\left( -1\right) ^{\left\vert X\right\vert }\left[
N\left( X\right) =B\right] =\sum_{Y\subseteq B}\left( -1\right)
^{\left\vert Y\right\vert }\left[ N\left( Y\right) =A\right] .
\]
\end{aufgabe}
\begin{aufgabe}
\label{aufg.heinrich-tittmann}(Heinrich, Tittmann, 2017)
Sei $G$ ein (einfacher, ungerichteter) Graph mit Eckenmenge $V$. Sei
$n=\left\vert V\right\vert $; wir nehmen an, dass $n>0$ ist.
Eine \textit{dominierende Menge} bedeute eine Teilmenge $W$ von $V$ so,
da\ss \ jede Ecke von $G$ entweder in $W$ liegt oder (mindestens) einen
Nachbarn in $W$ hat.
Ein \textit{Fernpaar} bedeute ein (geordnetes) Paar $\left( A,B\right) $
zweier disjunkter Teilmengen $A$ und $B$ von $V$ so, da\ss \ es keine Kante
mit einem Endpunkt in $A$ und dem anderen Endpunkt in $B$ gibt.
Sei $\alpha$ die Anzahl aller Fernpaare $\left( A,B\right) $, f\"{u}r die
$\left\vert A\right\vert $ und $\left\vert B\right\vert $ gerade positive
Zahlen sind.
Sei $\beta$ die Anzahl aller Fernpaare $\left( A,B\right) $, f\"{u}r die
$\left\vert A\right\vert $ und $\left\vert B\right\vert $ ungerade Zahlen sind.
\begin{enumerate}
\item[\textbf{(a)}] Zeige: Die Anzahl aller dominierenden Mengen ist
$2^{n}-1+\alpha-\beta$.
\item[\textbf{(b)}] Folgere, dass die Anzahl aller dominierenden Mengen
ungerade ist.
\end{enumerate}
\end{aufgabe}
\begin{aufgabe}
\label{aufg.elser}(Elser, 1984)
Sei $G$ ein (ungerichteter) Graph mit Eckenmenge $V$ und Kantenmenge $E$. Sei
$v\in V$.
Ist $F$ eine Teilmenge von $E$, dann verstehen wir unter einem $F$%
\textit{-Pfad} einen Pfad von $G$, dessen Kanten allesamt zu $F$ geh\"{o}ren.
Ist $e\in E$ eine Kante und $F$ eine Teilmenge von $E$, dann sagen wir, dass
$e$ \textit{durch }$F$ \textit{mit }$v$ \textit{verbunden} ist, wenn es einen
$F$-Pfad gibt, der von einem Endpunkt von $e$ nach $v$ f\"{u}hrt. (Dies gilt
u.a. immer dann, wenn $v$ ein Endpunkt von $e$ ist, weil der leere Pfad ein
$F$-Pfad ist.)
Eine Teilmenge $F$ von $E$ hei\ss e \textit{nett}, wenn jede Kante von $G$
durch $F$ mit $v$ verbunden ist.
Man zeige:%
\[
\sum_{F\subseteq E\text{ ist nett}}\left( -1\right) ^{\left\vert
F\right\vert }=\left[ E=\varnothing\right] .
\]
\end{aufgabe}
\section{\label{sec.los}L\"{o}sungen und L\"{o}sungshinweise}
Die nachfolgenden L\"{o}sungen sind gr\"{o}\ss tenteils skizziert (vor allem
die L\"{o}sungen zu den \textquotedblleft weiteren Aufgaben\textquotedblright)
und unter M\"{u}digkeit und Metal-Dauerbeschallung entstanden. Es w\"{u}rde
mich verwundern, wenn sie nicht mindestens von Typos wimmeln. Man wird
vermutlich dem Folgenden auch ansehen k\"{o}nnen, wie lange ich nicht mehr
Deutsch geschrieben habe. Bitte Fehler an
\href{mailto:darijgrinberg@gmail.com}{\texttt{darijgrinberg@gmail.com}}
melden! Kommentare und alternative L\"{o}sungen sind ebenfalls willkommen.
\subsection{zu Aufgabe \ref{aufg.pol-prot}}
Die L\"{o}sung von Aufgabe \ref{aufg.pol-prot} st\"{u}tzt sich auf den
\textquotedblleft Polynomidentit\"{a}ts-Trick\textquotedblright, der in seiner
einfachsten Form in der Anwendung des folgenden Lemmas besteht:
\begin{lemma}
\label{lem.poltrick.1}Seien $p,q:\mathbb{C}\rightarrow\mathbb{C}$ zwei
Polynomfunktionen. Angenommen, es gilt $p\left( z\right) =q\left( z\right)
$ f\"{u}r unendlich viele $z\in\mathbb{C}$. Dann gilt $p=q$.
\end{lemma}
\begin{proof}
[Beweisskizze.]Seien $f\in\mathbb{C}\left[ x\right] $ und $g\in
\mathbb{C}\left[ x\right] $ die Polynome, deren Polynomfunktionen $p$ und
$q$ sind. (Das hei\ss t, $p\left( z\right) =f\left( z\right) $ und
$q\left( z\right) =g\left( z\right) $ f\"{u}r alle $z\in\mathbb{C}$.) Wir
haben angenommen, dass $p\left( z\right) =q\left( z\right) $ f\"{u}r
unendlich viele Zahlen $z\in\mathbb{C}$ gilt. F\"{u}r all diese Zahlen $z$
gilt dann
\[
\left( f-g\right) \left( z\right) =\underbrace{f\left( z\right)
}_{=p\left( z\right) }-\underbrace{g\left( z\right) }_{=q\left( z\right)
}=\underbrace{p\left( z\right) }_{\substack{=q\left( z\right)
\\\text{(laut Annahme)}}}-q\left( z\right) =q\left( z\right) -q\left(
z\right) =0.
\]
Das hei\ss t, all diese Zahlen $z$ sind Nullstellen des Polynoms
$f-g\in\mathbb{C}\left[ x\right] $. Somit hat das Polynom $f-g$ unendlich
viele Nullstellen. Aber das einzige Polynom in $\mathbb{C}\left[ x\right] $,
das unendlich viele Nullstellen hat, ist das Nullpolynom $0$. Folglich ist
$f-g=0$. Das hei\ss t, $f=g$. F\"{u}r \textbf{jedes} $z\in\mathbb{C}$ gilt
also $f\left( z\right) =g\left( z\right) $, und daher $p\left( z\right)
=q\left( z\right) $ (denn $p\left( z\right) =f\left( z\right) $ und
$q\left( z\right) =g\left( z\right) $). Mit anderen Worten: $p=q$. Damit
ist Lemma \ref{lem.poltrick.1} gezeigt.
\end{proof}
(Wir haben uns in diesem Beweis M\"{u}he gegeben, akribisch zwischen
Polynomfunktionen und Polynomen zu unterscheiden. Im Kontext von komplexen
Zahlen besteht darin keine echte Notwendigkeit; ein wenig
Notationsmi\ss brauch darf man sich g\"{o}nnen, denn hier entspricht jeder
Polynomfunktion genau ein Polynom. Allerdings ist dies nicht mehr der Fall,
wenn man mit endlichen K\"{o}rpern oder wilderen Ringen statt $\mathbb{C}$
arbeit; beim L\"{o}sen von Aufgabe \ref{aufg.polar-prot} werden wir dies sogar tun.)
Aufgabe \ref{aufg.pol-prot} ist wohl das \textquotedblleft
kanonische\textquotedblright\ Beispiel f\"{u}r die Anwendung des Polynomtricks
beim Beweis von Identit\"{a}ten f\"{u}r Binomialkoeffizienten:
\begin{proof}
[L\"{o}sungsskizze zu Aufgabe \ref{aufg.pol-prot}.]\textbf{(a)} (F\"{u}r
Details siehe \cite[\S 2.6.1, Second proof of Theorem 2.6.1 for $x,y\in
\mathbb{N}$]{19fco} oder \"{a}hnlich in \cite[proof of Lemma 3.31]{detnotes}.
Diesen Beweis findet man wohl in jeder guten Einf\"{u}hrung in die
abz\"{a}hlende Kombinatorik.) Seien $n,x,y\in\mathbb{N}$. Wir m\"{u}ssen die
Gleichheit (\ref{eq.vandermonde}) beweisen. Da $n,x,y\in\mathbb{N}$ sind,
k\"{o}nnen wir alle Binomialkoeffizienten in dieser Gleichheit kombinatorisch
interpretieren (siehe \textquotedblleft Kombinatorische
Interpretation\textquotedblright\ in Abschnitt \ref{sec.bas}). Dies f\"{u}hrt
auf den Gedanken, dass man einen kombinatorischen Beweis versuchen k\"{o}nnte.
Und hier findet man ihn sogar recht schnell: Gez\"{a}hlt sollen alle
$n$-elementigen Teilmengen $T$ der $\left( x+y\right) $-elementigen Menge
$S:=\left\{ 1,2,\ldots,x\right\} \cup\left\{ -1,-2,\ldots,-y\right\} $.
Einerseits gibt es davon $\dbinom{x+y}{n}$ viele (laut der bereits genannten
\textquotedblleft Kombinatorischen Interpretation\textquotedblright\ der
Binomialkoeffizienten). Andererseits k\"{o}nnen wir eine solche Teilmenge $T$
aber auch dadurch bilden, dass wir
\begin{itemize}
\item zun\"{a}chst die Anzahl aller positiven Elemente in $T$ bestimmen --
dies ist eine Zahl zwischen $0$ und $n$ (inklusive)\footnote{Dieses
\textquotedblleft zwischen $0$ und $n$ (inklusive)\textquotedblright\ hei\ss t
nur, da\ss \ die Zahl immer $\geq0$ und $\leq n$ liegen muss. (Denn insgesamt
wird die Teilmenge $T$ ja $n$ Elemente haben; somit kann sie nicht mehr als
$n$ positive Elemente haben.) Ich sage \textbf{nicht}, dass jede Zahl zwischen
$0$ und $n$ auch tats\"{a}chlich m\"{o}glich ist. (Ist sie auch nicht
immer.)}, die wir fortan $k$ nennen;
\item dann diese $k$ positiven Elemente von $T$ ausw\"{a}hlen -- daf\"{u}r
haben wir $\dbinom{x}{k}$ M\"{o}glichkeiten, da wir $k$ aus den insgesamt $x$
positiven Elementen von $S$ ausw\"{a}hlen wollen;
\item schlie\ss lich die $n-k$ negativen Elemente von $T$ ausw\"{a}hlen --
daf\"{u}r haben wir $\dbinom{y}{n-k}$ M\"{o}glichkeiten, da wir $n-k$ aus den
insgesamt $y$ positiven Elementen von $S$ ausw\"{a}hlen wollen.
\end{itemize}
\noindent F\"{u}r diese Bildungsmethode gibt es also insgesamt $\sum_{k=0}%
^{n}\dbinom{x}{k}\dbinom{y}{n-k}$ M\"{o}glichkeiten. Folglich gibt es
$\sum_{k=0}^{n}\dbinom{x}{k}\dbinom{y}{n-k}$ viele $n$-elementige Teilmengen
von $S$. Aber wir haben vorhin gesehen, da\ss \ es $\dbinom{x+y}{n}$ viele
solche Teilmengen gibt. Beide Seiten der Gleichheit (\ref{eq.vandermonde})
z\"{a}hlen also das gleiche: n\"{a}mlich die $n$-elementigen Teilmengen von
$S$. Also m\"{u}ssen die beiden Seiten gleich sein. Damit ist
(\ref{eq.vandermonde}) bewiesen. Dies l\"{o}st Aufgabe \ref{aufg.pol-prot}
\textbf{(a)}.
\bigskip
\textbf{(b)} Hier gehen wir mit dem Polynomidentit\"{a}tstrick heran. Fixiere
$n\in\mathbb{N}$ und $x\in\mathbb{N}$. Definiere zwei Polynomfunktionen
$p,q:\mathbb{C}\rightarrow\mathbb{C}$ durch%
\[
p\left( y\right) =\dbinom{x+y}{n}\ \ \ \ \ \text{und}\ \ \ \ \ q\left(
y\right) =\sum_{k=0}^{n}\dbinom{x}{k}\dbinom{y}{n-k}%
\ \ \ \ \ \ \ \ \ \ \text{f\"{u}r alle }y\in\mathbb{C}.
\]
\footnote{Da\ss \ dies tats\"{a}chlich Polynomfunktionen sind, folgt aus der
\textquotedblleft Polynomialit\"{a}t\textquotedblright\ in Abschnitt
\ref{sec.bas}.} Aufgabe \ref{aufg.pol-prot} \textbf{(a)} sagt uns dann, dass
$p\left( y\right) =q\left( y\right) $ f\"{u}r alle $y\in\mathbb{N}$ gilt.
Mit anderen Worten: Es gilt $p\left( z\right) =q\left( z\right) $ f\"{u}r
alle $z\in\mathbb{N}$. Insbesondere gilt also $p\left( z\right) =q\left(
z\right) $ f\"{u}r unendlich viele $z\in\mathbb{C}$ (denn es gibt unendlich
viele $z\in\mathbb{N}$). Laut Lemma \ref{lem.poltrick.1} gilt also $p=q$. Das
hei\ss t, $p\left( y\right) =q\left( y\right) $ f\"{u}r alle
$y\in\mathbb{C}$. Mit anderen Worten:%
\[
\dbinom{x+y}{n}=\sum_{k=0}^{n}\dbinom{x}{k}\dbinom{y}{n-k}%
\ \ \ \ \ \ \ \ \ \ \text{f\"{u}r alle }y\in\mathbb{C}.
\]
Aufgabe \ref{aufg.pol-prot} \textbf{(b)} ist damit gel\"{o}st.
\bigskip
\textbf{(c)} Hier kommt der Polynomidentit\"{a}tstrick noch einmal zum Zug --
diesmal ist aber $x$ die \textquotedblleft wandernde\textquotedblright%
\ Variable. Fixiere $n\in\mathbb{N}$ und $y\in\mathbb{C}$. Definiere zwei
Polynomfunktionen $p,q:\mathbb{C}\rightarrow\mathbb{C}$ durch%
\[
p\left( x\right) =\dbinom{x+y}{n}\ \ \ \ \ \text{und}\ \ \ \ \ q\left(
x\right) =\sum_{k=0}^{n}\dbinom{x}{k}\dbinom{y}{n-k}%
\ \ \ \ \ \ \ \ \ \ \text{f\"{u}r alle }x\in\mathbb{C}.
\]
(Dies sind nicht die Funktionen $p$ und $q$ aus der L\"{o}sung von Teil
\textbf{(b)}!) Aufgabe \ref{aufg.pol-prot} \textbf{(b)} sagt uns dann, dass
$p\left( x\right) =q\left( x\right) $ f\"{u}r alle $x\in\mathbb{N}$ gilt.
Mit anderen Worten: Es gilt $p\left( z\right) =q\left( z\right) $ f\"{u}r
alle $z\in\mathbb{N}$. Insbesondere gilt also $p\left( z\right) =q\left(
z\right) $ f\"{u}r unendlich viele $z\in\mathbb{C}$ (denn es gibt unendlich
viele $z\in\mathbb{N}$). Laut Lemma \ref{lem.poltrick.1} gilt also $p=q$. Das
hei\ss t, $p\left( x\right) =q\left( x\right) $ f\"{u}r alle
$x\in\mathbb{C}$. Mit anderen Worten:%
\[
\dbinom{x+y}{n}=\sum_{k=0}^{n}\dbinom{x}{k}\dbinom{y}{n-k}%
\ \ \ \ \ \ \ \ \ \ \text{f\"{u}r alle }x\in\mathbb{C}.
\]
Aufgabe \ref{aufg.pol-prot} \textbf{(c)} ist damit gel\"{o}st.
\bigskip
\textbf{(d)} (Details in \cite[\S 2.6.5, First proof of Proposition
2.6.13]{19fco}.) Seien $n,x,y\in\mathbb{N}$. Wir m\"{u}ssen die Gleichheit
(\ref{eq.vandermonde-upside}) zeigen.
Wir wollen die Chu-Vandermonde-Identit\"{a}t (die wir in Aufgabe
\ref{aufg.pol-prot} \textbf{(c)} endg\"{u}ltig bewiesen haben) auf $n-x-y$,
$-x-1$ und $-y-1$ statt $n$, $x$ und $y$ anwenden. Dies wird dadurch
erschwert, dass wir daf\"{u}r $n-x-y\in\mathbb{N}$ ben\"{o}tigen, was nicht
automatisch erf\"{u}llt ist. Wir wollen also zun\"{a}chst den Fall loswerden,
in dem dies nicht gilt.
Nehmen wir also an, dass $n-x-y\notin\mathbb{N}$ gilt. Dann ist $n-x-y<0$.
Also ist $nn-y$. Es w\"{a}re also gut, wenn diese zus\"{a}tzlichen
Summanden sich zu $0$ aufsummieren und damit die Summe nicht ver\"{a}ndern.
Dies gilt aber tats\"{a}chlich, und zwar aus dem einfachst m\"{o}glichen
Grund: Diese zus\"{a}tzlichen Summanden sind alle $0$. (Und dies folgt aus dem
gleichen Argument, den wir bereits im Fall von $n-x-y\notin\mathbb{N}$
angewendet haben, mit einem kleinen Unterschied: Auch hier gilt f\"{u}r diese
Summanden wieder entweder $kn-y$ gilt.)
Die Summe in (\ref{eq.vandermonde-upside}) und die Summe in
(\ref{sol.pol-prot.d.5}) sind also gleich. Somit folgt
(\ref{eq.vandermonde-upside}) aus (\ref{sol.pol-prot.d.5}). Aufgabe
\ref{aufg.pol-prot} \textbf{(d)} ist also gel\"{o}st.
\bigskip
\textbf{(e)} Nein. Ein einfaches Gegenbeispiel ist $n=1$, $x=1/2$ und $y=1/2$,
denn hier ist die linke Seite von (\ref{eq.vandermonde-upside}) gleich
$\dbinom{1+1}{1/2+1/2+1}=1$, w\"{a}hrend die rechte Seite gleich $0$ ist.
Und dies sollte nicht verwundern. Der Binomialkoeffizient $\dbinom{n}{k}$ ist
eine Polynomfunktion in $n$, aber keine in $k$. Der
Polynomidentit\"{a}tstrick, mit dem wir in Aufgabe \ref{aufg.pol-prot}
\textbf{(b)} die G\"{u}ltigkeit der Chu-Vandermonde-Identit\"{a}t erweitert
haben, l\"{a}\ss t sich also nicht auf die \textquotedblleft umgedrehte
Chu-Vandermonde-Identit\"{a}t\textquotedblright\ anwenden.
\bigskip
\textbf{(f)} (Details in \cite[solution to Exercise 2.6.4]{19fco}.) Die
Hockeystick-Identit\"{a}t besagt, dass%
\[
\dbinom{0}{k}+\dbinom{1}{k}+\dbinom{2}{k}+\cdots+\dbinom{n}{k}=\dbinom
{n+1}{k+1}\ \ \ \ \ \ \ \ \ \ \text{f\"{u}r alle }n,k\in\mathbb{N}%
\]
gilt. Wir schreiben diese Identit\"{a}t erst einmal um, indem wir die Variable
$k$ in $x$ umbenennen. Sie besagt jetzt also, dass%
\[
\dbinom{0}{x}+\dbinom{1}{x}+\dbinom{2}{x}+\cdots+\dbinom{n}{x}=\dbinom
{n+1}{x+1}\ \ \ \ \ \ \ \ \ \ \text{f\"{u}r alle }n,x\in\mathbb{N}%
\]
gilt. Dies folgt aber durch Anwendung der \textquotedblleft umgedrehten
Chu-Vandermonde-Identit\"{a}t\textquotedblright\ (\ref{eq.vandermonde-upside})
auf $y=0$; denn letzteres ergibt%
\[
\dbinom{n+1}{x+1}=\sum_{k=0}^{n}\dbinom{k}{x}\underbrace{\dbinom{n-k}{0}}%
_{=1}=\sum_{k=0}^{n}\dbinom{k}{x}=\dbinom{0}{x}+\dbinom{1}{x}+\dbinom{2}%
{x}+\cdots+\dbinom{n}{x}.
\]
Aufgabe \ref{aufg.pol-prot} \textbf{(f)} ist somit gel\"{o}st.
\bigskip
[\textit{Bemerkung:} Alternative L\"{o}sungen gibt es hier wie Sand am Meer:
\begin{itemize}
\item Man kann Aufgabe \ref{aufg.pol-prot} \textbf{(a)} -- und sogar gleich
Aufgabe \ref{aufg.pol-prot} \textbf{(b)} -- auch durch Induktion nach $x$
beweisen. (Dies wird in \cite[\S 2.6.1, First proof of Theorem 1.3.37 for
$x\in\mathbb{N}$]{19fco} getan.)
\item Man kann die Chu-Vandermonde-Identit\"{a}t auch ganz allgemein (also
gleich f\"{u}r $x,y\in\mathbb{C}$) durch Induktion nach $n$ beweisen. (Siehe
\cite[\S 3.3.2, First proof of Theorem 3.29]{detnotes} f\"{u}r diesen Beweis.)
So spart man sich die Anwendung des Polynomidentit\"{a}tstricks ganz.
\item Man kann Aufgabe \ref{aufg.pol-prot} \textbf{(a)} auch beweisen, indem
man die Polynomidentit\"{a}t%
\[
\left( 1+t\right) ^{x+y}=\left( 1+t\right) ^{x}\left( 1+t\right) ^{y}%
\]
im Polynomring $\mathbb{Z}\left[ t\right] $ ausmultipliziert und die
Koeffizienten von $t^{n}$ auf beiden Seiten vergleicht. (Dies ist ein
einfaches Beispiel der Verwendung von \textit{erzeugenden Funktionen}.) Mit
viel M\"{u}he kann man auch dieses Argument auf allgemeine $x,y\in\mathbb{C}$
ausdehnen; hierzu muss man allerdings von Polynomen zu Potenzreihen
\"{u}bergehen, au\ss erdem die $z$-te Potenz einer Potenzreihe $f$ (f\"{u}r
$z\in\mathbb{C}$ und $f\left( 0\right) =1$) definieren und schlie\ss lich
zeigen, dass diese Potenzen auch noch das Potenzgesetz $f^{z+w}=f^{z}f^{w}$
erf\"{u}llen. Dies ist nicht so einfach\footnote{Siehe
\url{https://math.stackexchange.com/a/2918387/} f\"{u}r eine Diskussion der
M\"{o}glichkeiten, dies zu tun.}; manche Autoren verwenden dabei sogar eine
Variante der Chu-Vandermonde-Identit\"{a}t als Hilfsmittel (z. B. Loehr in
\cite[proof of Theorem 7.71]{Loehr-BC}), wodurch das Argument etwas zyklisch wird...
\item Die \textquotedblleft umgedrehte
Chu-Vandermonde-Identit\"{a}t\textquotedblright\ (\ref{eq.vandermonde-upside})
l\"{a}\ss t sich kombinatorisch beweisen (\cite[\S 2.6.5, Second proof of
Proposition 2.6.13]{19fco}).]
\end{itemize}
\end{proof}
\subsection{zu Aufgabe \ref{aufg.srinvol-prot}}
\begin{proof}
[L\"{o}sungsskizze zu Aufgabe \ref{aufg.srinvol-prot}.]\textbf{(a)} (Siehe
\cite[Exercise 4, second solution]{18f-hw2s} f\"{u}r Details.) Seien
$n\in\mathbb{C}$ und $m\in\mathbb{N}$. F\"{u}r jedes $k\in\mathbb{Z}$ gilt
\begin{align*}
\left( -1\right) ^{k}\underbrace{\dbinom{n}{k}}_{\substack{=\dbinom
{n-1}{k-1}+\dbinom{n-1}{k}\\\text{(laut (\ref{eq.binom.rec}))}}} & =\left(
-1\right) ^{k}\left( \dbinom{n-1}{k-1}+\dbinom{n-1}{k}\right) \\
& =\underbrace{\left( -1\right) ^{k}}_{=-\left( -1\right) ^{k-1}}%
\dbinom{n-1}{k-1}+\left( -1\right) ^{k}\dbinom{n-1}{k}\\
& =\left( -1\right) ^{k}\dbinom{n-1}{k}-\left( -1\right) ^{k-1}%
\dbinom{n-1}{k-1}.
\end{align*}
Summieren wir diese Gleichheit f\"{u}r alle $k\in\left\{ 0,1,\ldots
,m\right\} $ auf, so erhalten wir%
\[
\sum_{k=0}^{m}\left( -1\right) ^{k}\dbinom{n}{k}=\sum_{k=0}^{m}\left(
\left( -1\right) ^{k}\dbinom{n-1}{k}-\left( -1\right) ^{k-1}\dbinom
{n-1}{k-1}\right) .
\]
Doch die rechte Seite hier ist eine Teleskopsumme, die sich zu%
\[
\left( -1\right) ^{m}\dbinom{n-1}{m}-\left( -1\right) ^{-1}%
\underbrace{\dbinom{n-1}{-1}}_{\substack{=0\\\text{(nach (\ref{eq.binom.def}%
),}\\\text{denn }-1\notin\mathbb{N}\text{)}}}=\left( -1\right) ^{m}%
\dbinom{n-1}{m}%
\]
vereinfacht. Somit ist $\sum_{k=0}^{m}\left( -1\right) ^{k}\dbinom{n}%
{k}=\left( -1\right) ^{m}\dbinom{n-1}{m}$. Dadurch ist
(\ref{eq.aufg.srinvol-prot.id}) bewiesen.
\bigskip
\textbf{(b)} (Siehe \cite[Exercise 4, third solution]{18f-hw2s} f\"{u}r
Details.) Sei $n$ eine positive ganze Zahl, und sei $m\in\mathbb{N}$. Sei
$\left[ n\right] :=\left\{ 1,2,\ldots,n\right\} $. Definiere eine
\textit{akzeptable Menge} als eine Teilmenge von $\left[ n\right] $ mit
h\"{o}chstens $m$ Elementen. Das \textit{Vorzeichen} einer endlichen Menge $I$
definieren wir als $\left( -1\right) ^{\left\vert I\right\vert }$.
\begin{noncompile}
Eine endliche Menge hei\ss e \textit{gerade}, wenn sie gerade viele Elemente
(und damit Vorzeichen $1$) hat; sonst hei\ss e sie \textit{ungerade}.
\end{noncompile}
Die akzeptablen Mengen sind genau die $k$-elementigen Teilmengen von $\left[
n\right] $ mit $k\in\left\{ 0,1,\ldots,m\right\} $. Daher ist
\[
\left( \text{die Anzahl aller akzeptablen Mengen}\right) =\sum_{k=0}%
^{m}\dbinom{n}{k}%
\]
(denn laut der kombinatorischen Interpretation der Binomialkoeffizienten ist
die Anzahl aller $k$-elementigen Teilmengen von $\left[ n\right] $ gleich
$\dbinom{n}{k}$). Aus dem gleichen Grund gilt
\begin{align}
& \left( \text{die Summe der Vorzeichen aller akzeptablen Mengen}\right)
\nonumber\\
& =\sum_{k=0}^{m}\left( -1\right) ^{k}\dbinom{n}{k}
\label{sol.srinvol-prot.sum-vorz}%
\end{align}
(denn eine $k$-elementige akzeptable Menge hat Vorzeichen $\left( -1\right)
^{k}$).
Die Summe der Vorzeichen aller akzeptablen Mengen ist eine Summe von $1$en und
$-1$en. Wenn wir es schaffen, die \textquotedblleft meisten\textquotedblright%
\ dieser $1$en und $-1$en gegeneinander zu k\"{u}rzen, dann k\"{o}nnen wir
hoffen, dass sich der Wert der Summe offenbart. (Wir werden dies nachher
formalisieren.) Zum K\"{u}rzen m\"{u}ssen wir akzeptable Mengen
gegens\"{a}tzlicher Vorzeichen gegeneinander aufstellen.
Wie ordnen wir einer endlichen Menge $I$ eine andere endliche Menge mit
gegens\"{a}tzlichem Vorzeichen zu? Wir k\"{o}nnen versuchen, das Element $1$
aus der Menge $I$ zu entfernen oder in sie einzuf\"{u}gen, je nachdem ob es in
ihr enthalten ist oder nicht. Dadurch ver\"{a}ndert sich die M\"{a}chtigkeit
der Menge um genau $1$ (in die eine oder andere Richtung), und somit wechselt
das Vorzeichen zum gegens\"{a}tzlichen. Das Resultat der Prozedur nennen wir
den \textit{Partner} von $I$ und bezeichnen wir mit $\mathbf{p}\left(
I\right) $. Was auch gut ist: Wenn $I$ eine Teilmenge von $\left[ n\right]
$ ist, dann ist auch ihr Partner $\mathbf{p}\left( I\right) $ eine solche.
Und wenn $I$ eine akzeptable Menge ist, dann ist \textbf{meistens} auch
$\mathbf{p}\left( I\right) $ eine solche (wir werden bald sehen, wann genau
dies passiert). Man kann also die zu $I$ und zu $\mathbf{p}\left( I\right) $
geh\"{o}rigen Summanden in der Summe der Vorzeichen aller akzeptablen Mengen
k\"{u}rzen (diese zwei Summanden sind tats\"{a}chlich verschieden, da sie ja
unterschiedliche Vorzeichen haben). Diese Prozedur wiederholt man dann immer
weiter, bis keine Summanden mehr da sind, die Partner in der Summe haben. Das
Endresultat h\"{a}ngt davon ab, welche akzeptablen Mengen keine akzeptablen
Partner haben.
Welche akzeptablen Mengen haben keine Partner in der Summe? Wenn eine
akzeptable Menge $I$ in unserer Summe keinen Partner findet, dann liegt dies
entweder daran, dass ihr Partner bereits gek\"{u}rzt wurde, oder daran, dass
ihr Partner keine akzeptable Menge ist. Der erste Fall kann aber nicht
eintreten, denn der Partner des Partners einer Menge $I$ ist immer $I$ selber
(wie man sich leicht \"{u}berlegt) -- d.h., wenn der Partner einer Menge
gek\"{u}rzt wurde, dann wurde auch die Menge selber mit ihm gek\"{u}rzt. Wir
wollen also sehen, wann der zweite Fall eintritt. Laut Definition von
\textquotedblleft akzeptablen Mengen\textquotedblright\ ist der Partner
$\mathbf{p}\left( I\right) $ einer akzeptablen Menge $I$ nur dann nicht
akzeptabel, wenn er $m+1$ Elemente hat -- was wiederum genau dann der Fall
ist, wenn $I$ selber $m$ Elemente hat und $1$ nicht in $I$ enthalten ist (denn
nur dann wird $\left\vert \mathbf{p}\left( I\right) \right\vert $
gr\"{o}\ss er als $\left\vert I\right\vert $ und \"{u}berschreitet den
kritischen Wert $m$). Solche akzeptablen Mengen $I$ lassen sich leicht
charakterisieren: Sie sind einfach die $m$-elementigen Teilmengen von
$\left\{ 1,2,\ldots,n\right\} $, die $1$ nicht enthalten; mit anderen
Worten: Sie sind die $m$-elementigen Teilmengen der $\left( n-1\right)
$-elementigen Menge $\left\{ 2,3,\ldots,n\right\} $. Es gibt also genau
$\dbinom{n-1}{m}$ viele von ihnen (laut der kombinatorischen Interpretation
der Binomialkoeffizienten), und sie haben also alle das Vorzeichen $\left(
-1\right) ^{m}$ (da sie $m$-elementig sind). Ihr Gesamtbeitrag zur Summe der
Vorzeichen aller akzeptablen Mengen ist also $\dbinom{n-1}{m}\cdot\left(
-1\right) ^{m}=\left( -1\right) ^{m}\dbinom{n-1}{m}$. Da sich (wie schon
gesagt) die Beitr\"{a}ge aller anderen akzeptablen Mengen in der Summe
wegk\"{u}rzen, ist die Summe insgesamt also auch gleich $\left( -1\right)
^{m}\dbinom{n-1}{m}$. Mit anderen Worten:%
\[
\left( \text{die Summe der Vorzeichen aller akzeptablen Mengen}\right)
=\left( -1\right) ^{m}\dbinom{n-1}{m}.
\]
Gleichen wir dies mit (\ref{sol.srinvol-prot.sum-vorz}) ab, so erhalten wir%
\[
\sum_{k=0}^{m}\left( -1\right) ^{k}\dbinom{n}{k}=\left( -1\right)
^{m}\dbinom{n-1}{m}.
\]
Damit ist (\ref{eq.aufg.srinvol-prot.id}) wieder bewiesen im Falle, wenn $n$
eine positive ganze Zahl ist.
Noch ein paar Worte dazu, wie man obigen Beweis formalisiert. So ein
\textquotedblleft K\"{u}rzungsprozess\textquotedblright\ ist kein besonders
wohldefinierter Begriff, aber was er im Wesentlichen konstruiert, ist eine
\textbf{Bijektion} $\mathbf{p}:\mathcal{X}\rightarrow\mathcal{X}$ auf der
Menge
\begin{align*}
\mathcal{X}:= & \left\{ \text{akzeptable Mengen, deren Partner ebenfalls
akzeptable Mengen sind}\right\} \\
= & \left\{ I\subseteq\left[ n\right] \ \mid\ \left\vert I\right\vert
\leq m\text{ aber nicht }\left( \left\vert I\right\vert =m\text{ und }1\notin
I\right) \right\} .
\end{align*}
Diese Bijektion $\mathbf{p}$ ist formal definiert durch%
\[
\mathbf{p}\left( I\right) =\left( \text{Partner von }I\right) =%
\begin{cases}
I\setminus\left\{ 1\right\} , & \text{wenn }1\in I;\\
I\cup\left\{ 1\right\} , & \text{wenn }1\notin I
\end{cases}
\ \ \ \ \ \ \ \ \ \ \text{f\"{u}r alle }I\in\mathcal{X}\text{.}%
\]
Diese Bijektion $\mathbf{p}$ hat die Eigenschaft, \textbf{vorzeichenumkehrend}
zu sein (d.h., es gilt $\left( -1\right) ^{\left\vert \mathbf{p}\left(
I\right) \right\vert }=-\left( -1\right) ^{\left\vert I\right\vert }$
f\"{u}r alle $I\in\mathcal{X}$). Die Behauptung ist nun, dass die Existenz
einer solchen Bijektion automatisch dazu f\"{u}hrt, dass%
\begin{align*}
& \left( \text{die Summe der Vorzeichen aller akzeptablen Mengen}\right) \\
& =\left( \text{die Summe der Vorzeichen aller akzeptablen Mengen, die
\textbf{nicht} in }\mathcal{X}\text{ liegen}\right)
\end{align*}
gilt -- d.h., da\ss \ die Beitr\"{a}ge der akzeptablen Mengen in $\mathcal{X}$
zur Summe der Vorzeichen aller akzeptablen Mengen insgesamt verschwinden. Das
zugrundeliegende Prinzip wollen wir allgemein formulieren:\footnote{Unsere
Behauptung erhalten wir aus diesem Lemma, indem wir es auf%
\begin{align*}
S & =\left[ n\right] ,\\
\mathcal{A} & =\left\{ \text{akzeptable Mengen}\right\} ,\\
\mathcal{X} & =\left\{ \text{akzeptable Mengen, deren Partner ebenfalls
akzeptable Mengen sind}\right\} ,\\
f & =\mathbf{p}%
\end{align*}
anwenden.}
\begin{lemma}
\label{lem.srinvol-prot.bijprinc1}Sei $S$ eine endliche Menge. Sei
$\mathcal{A}$ eine Teilmenge der Potenzmenge von $S$ (also eine Menge, deren
Elemente wiederum Teilmengen von $S$ sind). Sei $\mathcal{X}$ eine Teilmenge
von $\mathcal{A}$. Sei $f:\mathcal{X}\rightarrow\mathcal{X}$ eine Bijektion,
die die Eigenschaft hat, dass%
\begin{equation}
\left( -1\right) ^{\left\vert f\left( I\right) \right\vert }=-\left(
-1\right) ^{\left\vert I\right\vert }\ \ \ \ \ \ \ \ \ \ \text{f\"{u}r alle
}I\in\mathcal{X} \label{eq.lem.srinvol-prot.bijprinc1.vorzeichen-umk}%
\end{equation}
gilt. (Eine solche Bijektion hei\ss t \textit{vorzeichenumkehrend}.) Dann ist
\[
\sum_{I\in\mathcal{A}}\left( -1\right) ^{\left\vert I\right\vert }%
=\sum_{I\in\mathcal{A}\setminus\mathcal{X}}\left( -1\right) ^{\left\vert
I\right\vert }.
\]
(Das hei\ss t, die Beitr\"{a}ge aller $I\in\mathcal{X}$ zur Summe $\sum
_{I\in\mathcal{A}}\left( -1\right) ^{\left\vert I\right\vert }$ verschwinden insgesamt.)
\end{lemma}
\begin{proof}
[Beweisskizze zu Lemma \ref{lem.srinvol-prot.bijprinc1}.]Die Abbildung
$f:\mathcal{X}\rightarrow\mathcal{X}$ ist eine Bijektion; somit hat sie eine
Umkehrabbildung $f^{-1}:\mathcal{X}\rightarrow\mathcal{X}$. Diese
Umkehrabbildung ist ebenfalls vorzeichenumkehrend -- d.h., sie erf\"{u}llt
\begin{equation}
\left( -1\right) ^{\left\vert f^{-1}\left( I\right) \right\vert }=-\left(
-1\right) ^{\left\vert I\right\vert }\ \ \ \ \ \ \ \ \ \ \text{f\"{u}r alle
}I\in\mathcal{X}. \label{pf.lem.srinvol-prot.bijprinc1.vorzeichen-umk}%
\end{equation}
(Dies folgt einfach, indem man
(\ref{eq.lem.srinvol-prot.bijprinc1.vorzeichen-umk}) auf $f^{-1}\left(
I\right) $ statt $I$ anwendet.)
Nun definieren wir zwei Abbildungen%
\begin{align*}
f_{+}:\left\{ I\in\mathcal{X}\ \mid\ \left( -1\right) ^{\left\vert
I\right\vert }=1\right\} & \rightarrow\left\{ I\in\mathcal{X}%
\ \mid\ \left( -1\right) ^{\left\vert I\right\vert }=-1\right\} ,\\
I & \mapsto f\left( I\right)
\end{align*}
und%
\begin{align*}
f_{-}:\left\{ I\in\mathcal{X}\ \mid\ \left( -1\right) ^{\left\vert
I\right\vert }=-1\right\} & \rightarrow\left\{ I\in\mathcal{X}%
\ \mid\ \left( -1\right) ^{\left\vert I\right\vert }=1\right\} ,\\
I & \mapsto f^{-1}\left( I\right) .
\end{align*}
(Dass diese Abbildungen wohldefiniert sind, verdanken wir
(\ref{eq.lem.srinvol-prot.bijprinc1.vorzeichen-umk}) und
(\ref{pf.lem.srinvol-prot.bijprinc1.vorzeichen-umk}).) Es ist klar, dass diese
Abbildungen $f_{+}$ und $f_{-}$ zueinander invers sind. Also sind sie
Bijektionen. Damit haben wir eine Bijektion zwischen den Mengen $\left\{
I\in\mathcal{X}\ \mid\ \left( -1\right) ^{\left\vert I\right\vert
}=1\right\} $ und $\left\{ I\in\mathcal{X}\ \mid\ \left( -1\right)
^{\left\vert I\right\vert }=-1\right\} $ gefunden (n\"{a}mlich $f_{+}$).
Daher sind diese Mengen gleichm\"{a}chtig. Mit anderen Worten:%
\begin{equation}
\left\vert \left\{ I\in\mathcal{X}\ \mid\ \left( -1\right) ^{\left\vert
I\right\vert }=1\right\} \right\vert =\left\vert \left\{ I\in\mathcal{X}%
\ \mid\ \left( -1\right) ^{\left\vert I\right\vert }=-1\right\} \right\vert
. \label{pf.lem.srinvol-prot.bijprinc1.size=size}%
\end{equation}
Nun ist aber $\left( -1\right) ^{\left\vert I\right\vert }$ f\"{u}r jede
Menge $I\in\mathcal{X}$ entweder gleich $1$ oder gleich $-1$. Somit k\"{o}nnen
wir die Summe $\sum_{I\in\mathcal{X}}\left( -1\right) ^{\left\vert
I\right\vert }$ folgenderma\ss en aufspalten:%
\begin{align*}
\sum_{I\in\mathcal{X}}\left( -1\right) ^{\left\vert I\right\vert } &
=\sum_{\substack{I\in\mathcal{X};\\\left( -1\right) ^{\left\vert
I\right\vert }=1}}\underbrace{\left( -1\right) ^{\left\vert I\right\vert }%
}_{=1}+\sum_{\substack{I\in\mathcal{X};\\\left( -1\right) ^{\left\vert
I\right\vert }=-1}}\underbrace{\left( -1\right) ^{\left\vert I\right\vert }%
}_{=-1}\\
& =\underbrace{\sum_{\substack{I\in\mathcal{X};\\\left( -1\right)
^{\left\vert I\right\vert }=1}}1}_{=\left\vert \left\{ I\in\mathcal{X}%
\ \mid\ \left( -1\right) ^{\left\vert I\right\vert }=1\right\} \right\vert
\cdot1}+\underbrace{\sum_{\substack{I\in\mathcal{X};\\\left( -1\right)
^{\left\vert I\right\vert }=-1}}\left( -1\right) }_{=\left\vert \left\{
I\in\mathcal{X}\ \mid\ \left( -1\right) ^{\left\vert I\right\vert
}=-1\right\} \right\vert \cdot\left( -1\right) }\\
& =\left\vert \left\{ I\in\mathcal{X}\ \mid\ \left( -1\right) ^{\left\vert
I\right\vert }=1\right\} \right\vert \cdot1+\left\vert \left\{
I\in\mathcal{X}\ \mid\ \left( -1\right) ^{\left\vert I\right\vert
}=-1\right\} \right\vert \cdot\left( -1\right) \\
& =\left\vert \left\{ I\in\mathcal{X}\ \mid\ \left( -1\right) ^{\left\vert
I\right\vert }=1\right\} \right\vert -\left\vert \left\{ I\in\mathcal{X}%
\ \mid\ \left( -1\right) ^{\left\vert I\right\vert }=-1\right\} \right\vert
\\
& =0\ \ \ \ \ \ \ \ \ \ \left( \text{nach
(\ref{pf.lem.srinvol-prot.bijprinc1.size=size})}\right) .
\end{align*}
Aber $\mathcal{X}$ ist eine Teilmenge von $\mathcal{A}$; somit k\"{o}nnen wir
die Summe $\sum_{I\in\mathcal{A}}\left( -1\right) ^{\left\vert I\right\vert
}$ folgenderma\ss en aufspalten:%
\[
\sum_{I\in\mathcal{A}}\left( -1\right) ^{\left\vert I\right\vert
}=\underbrace{\sum_{I\in\mathcal{X}}\left( -1\right) ^{\left\vert
I\right\vert }}_{=0}+\sum_{I\in\mathcal{A}\setminus\mathcal{X}}\left(
-1\right) ^{\left\vert I\right\vert }=\sum_{I\in\mathcal{A}\setminus
\mathcal{X}}\left( -1\right) ^{\left\vert I\right\vert }.
\]
Damit ist Lemma \ref{lem.srinvol-prot.bijprinc1} gezeigt.
\end{proof}
Lemma \ref{lem.srinvol-prot.bijprinc1} ist eine Abstraktion unserer Strategie,
Summen durch K\"{u}rzung gegens\"{a}tzlicher Summanden zu vereinfachen. Wie so
oft haben wir dabei durch das Abstrahieren ein kleines Geschenk erhalten: In
Lemma \ref{lem.srinvol-prot.bijprinc1} wird nicht vorausgesetzt,
da\ss \ $f\circ f=\operatorname*{id}$ ist, sondern nur, dass $f$ eine
Bijektion ist. Das hei\ss t, beim Anwenden von Lemma
\ref{lem.srinvol-prot.bijprinc1} ist es nicht notwendig, dass der Partner des
Partners einer Menge $I\in\mathcal{X}$ wieder $I$ selber ist; es reicht aus,
dass jede Menge $I\in\mathcal{X}$ genau einen Partner hat (d.h., die Funktion
$f$ ist wohldefiniert) und dass jede Menge $I\in\mathcal{X}$ genau einen
\textquotedblleft Ur-Partner\textquotedblright\ (also genau ein $J\in
\mathcal{X}$ mit $f\left( J\right) =I$) hat (d.h., die Funktion $f$ ist
bijektiv). Aus der Sicht des schrittweisen K\"{u}rzungsparadigmas ist dies
etwas \"{u}berraschend, da dies dazu f\"{u}hren kann, dass eine noch
ungek\"{u}rzte Menge einen bereits gek\"{u}rzten Partner hat; aber unser
obiger Beweis von Lemma \ref{lem.srinvol-prot.bijprinc1} argumentiert nicht
durch schrittweises Wegk\"{u}rzen, sondern durch simultanes systematisches
K\"{u}rzen aller $1$en gegen alle $-1$en, und dabei entsteht das Problem
nicht. Wir haben also ein wenig Allgemeinheit gewonnen. In der Praxis wird
diese Allgemeinheit selten benutzt (die meisten vorzeichenumkehrenden
Bijektionen $f$ in der Kombinatorik haben die Eigenschaft $f\circ
f=\operatorname*{id}$ -- sie sind, wie man es nennt, \textit{Involutionen}).
\bigskip
\textbf{(c)} Dies folgt aus dem Polynomidentit\"{a}tstrick (Lemma
\ref{lem.poltrick.1}). Und zwar: Fixiere $m\in\mathbb{N}$. Definiere zwei
Polynomfunktionen $p,q:\mathbb{C}\rightarrow\mathbb{C}$ durch%
\[
p\left( n\right) =\sum_{k=0}^{m}\left( -1\right) ^{k}\dbinom{n}%
{k}\ \ \ \ \ \text{und}\ \ \ \ \ q\left( n\right) =\left( -1\right)
^{m}\dbinom{n-1}{m}\ \ \ \ \ \ \ \ \ \ \text{f\"{u}r alle }n\in\mathbb{C}%
\text{.}%
\]
Aus Aufgabe \ref{aufg.srinvol-prot} \textbf{(b)} folgt dann, dass $p\left(
n\right) =q\left( n\right) $ f\"{u}r alle positiven ganzen $n$ gilt. Mit
anderen Worten: Es gilt $p\left( z\right) =q\left( z\right) $ f\"{u}r alle
positiven ganzen $z$. Insbesondere gilt also $p\left( z\right) =q\left(
z\right) $ f\"{u}r unendlich viele $z\in\mathbb{C}$ (denn es gibt unendlich
viele positive ganze Zahlen). Laut Lemma \ref{lem.poltrick.1} ist also $p=q$.
Mit anderen Worten: $p\left( n\right) =q\left( n\right) $ f\"{u}r alle
$n\in\mathbb{C}$. Aber dies bedeutet genau, dass
(\ref{eq.aufg.srinvol-prot.id}) f\"{u}r alle $n\in\mathbb{C}$ gilt. Damit ist
(\ref{eq.aufg.srinvol-prot.id}) wieder allgemein bewiesen.
\bigskip
\textbf{(d)} Seien $n\in\mathbb{C}$ und $m\in\mathbb{N}$. Anwendung der
Chu-Vandermonde-Identit\"{a}t (\ref{eq.vandermonde}) auf $n$, $-1$ und $m$
statt $x$, $y$ und $n$ ergibt%
\[
\dbinom{n-1}{m}=\sum_{k=0}^{m}\dbinom{n}{k}\underbrace{\dbinom{-1}{m-k}%
}_{\substack{=\left( -1\right) ^{m-k}\\\text{(nach (\ref{eq.bas.-1choosek}%
))}}}=\sum_{k=0}^{m}\dbinom{n}{k}\underbrace{\left( -1\right) ^{m-k}%
}_{=\left( -1\right) ^{m}\left( -1\right) ^{k}}=\left( -1\right)
^{m}\sum_{k=0}^{m}\left( -1\right) ^{k}\dbinom{n}{k}.
\]
Multiplizieren wir beide Seiten dieser Gleichung mit $\left( -1\right) ^{m}%
$, dann erhalten wir schnell (\ref{eq.aufg.srinvol-prot.id}). Damit ist
(\ref{eq.aufg.srinvol-prot.id}) zum dritten Mal bewiesen.
\end{proof}
\subsection{zu Aufgabe \ref{aufg.pie-prot}}
F\"{u}r Aufgabe \ref{aufg.pie-prot} ben\"{o}tigen wir die
\href{https://en.wikipedia.org/wiki/Iverson_bracket}{\textit{Iversonklammer-Notation}%
}:
\begin{definition}
\label{def.iverson}Sei $\mathcal{A}$ eine beliebige logische Aussage. Dann
definieren wir eine ganze Zahl $\left[ \mathcal{A}\right] \in\left\{
0,1\right\} $ durch%
\[
\left[ \mathcal{A}\right] =%
\begin{cases}
1, & \text{wenn }\mathcal{A}\text{ wahr ist};\\
0, & \text{wenn }\mathcal{A}\text{ falsch ist.}%
\end{cases}
\]
Beispielsweise ist $\left[ 2+2=4\right] =1$ und $\left[ 2+2=5\right] =0$.
Die Zahl $\left[ \mathcal{A}\right] $ hei\ss t \textit{Wahrheitswert} von
$\mathcal{A}$.
\end{definition}
Die folgende Tatsache ist fast trivial (\cite[Proposition 1.6.3]{19fco}); sie
hat aber eine gro\ss e Bedeutung, weil sie Z\"{a}hlprobleme auf
Summenumformungen zur\"{u}ckf\"{u}hren kann:
\begin{proposition}
[\textquotedblleft H\"{a}nde z\"{a}hlen\textquotedblright]%
\label{prop.count.rollcall}Sei $S$ eine endliche Menge.
\begin{enumerate}
\item[\textbf{(a)}] Ist $T$ eine Teilmenge von $S$, so ist%
\[
\left\vert T\right\vert =\sum_{s\in S}\left[ s\in T\right] .
\]
\item[\textbf{(b)}] F\"{u}r jedes $s\in S$ sei $\mathcal{A}\left( s\right) $
eine logische Aussage (die, je nach $s$, entweder wahr oder falsch ist;
beispielsweise kann $\mathcal{A}\left( s\right) $ die Aussage
\textquotedblleft$s$ ist gerade\textquotedblright, wenn $S$ eine Menge ganzer
Zahlen sein, oder die Aussage \textquotedblleft$s$ ist leer\textquotedblright,
wenn $S$ eine Menge von Mengen ist). Dann gilt%
\[
\left( \text{Anzahl aller }s\in S\text{, die }\mathcal{A}\left( s\right)
\text{ erf\"{u}llen}\right) =\sum_{s\in S}\left[ \mathcal{A}\left(
s\right) \right] .
\]
\end{enumerate}
\end{proposition}
\begin{proof}
[Beweisskizze.]\textbf{(a)} In der Summe $\sum_{s\in S}\left[ s\in T\right]
$ sind genau $\left\vert T\right\vert $ viele Summanden gleich $1$
(n\"{a}mlich die Summanden mit $s\in T$); alle \"{u}brigen $\left\vert
S\setminus T\right\vert $ Summanden sind $0$. Somit ist diese Summe gleich
$\left\vert T\right\vert \cdot1+\left\vert S\setminus T\right\vert
\cdot0=\left\vert T\right\vert $.
\textbf{(b)} Wende Proposition \ref{prop.count.rollcall} \textbf{(a)} auf die
Teilmenge $T:=\left\{ s\in S\ \mid\ \mathcal{A}\left( s\right) \text{ ist
wahr}\right\} $ an. F\"{u}r diese Teilmenge gilt n\"{a}mlich, dass $\left[
s\in T\right] =\left[ \mathcal{A}\left( s\right) \right] $ f\"{u}r jedes
$s\in S$ gilt.
\end{proof}
Wir erinnern uns ferner an folgenden fundamentalen Satz (eine der Formen des Schubfachprinzips):
\begin{proposition}
\label{prop.pie.surj1}Seien $X$ und $Y$ zwei endliche Mengen mit $\left\vert
X\right\vert \leq\left\vert Y\right\vert $. Dann ist jede surjektive Abbildung
von $X$ nach $Y$ automatisch bijektiv.
\end{proposition}
\begin{proof}
[Beweisskizze zu Proposition \ref{prop.pie.surj1}.]Sei $f:X\rightarrow Y$ eine
surjektive Abbildung. Wir m\"{u}ssen zeigen, dass $f$ bijektiv ist. Dazu
reicht es aus, zu beweisen, dass $f$ injektiv ist (denn surjektiv ist $f$ bereits).
Nehmen wir das Gegenteil an. Dann ist $f$ nicht injektiv; d.h., es gibt zwei
verschiedene Elemente $x,x^{\prime}\in X$ mit $f\left( x\right) =f\left(
x^{\prime}\right) $.
Seien $x_{1},x_{2},\ldots,x_{k}$ alle Elemente von $X$ (aufgelistet ohne
Wiederholungen); dann ist $k=\left\vert X\right\vert $ und $X=\left\{
x_{1},x_{2},\ldots,x_{k}\right\} $. Da $f$ surjektiv ist, gilt
\begin{align}
Y & =f\left( X\right) =f\left( \left\{ x_{1},x_{2},\ldots,x_{k}\right\}
\right) \ \ \ \ \ \ \ \ \ \ \left( \text{denn }X=\left\{ x_{1},x_{2}%
,\ldots,x_{k}\right\} \right) \nonumber\\
& =\left\{ f\left( x_{1}\right) ,f\left( x_{2}\right) ,\ldots,f\left(
x_{k}\right) \right\} . \label{pf.prop.pie.surj1.Y=}%
\end{align}
Doch, wie wir wissen, gibt es zwei verschiedene Elemente $x,x^{\prime}\in X$
mit $f\left( x\right) =f\left( x^{\prime}\right) $. Diese zwei Elemente
$x,x^{\prime}$ m\"{u}ssen unter den Elementen $x_{1},x_{2},\ldots,x_{k}$ sein
(denn $x_{1},x_{2},\ldots,x_{k}$ sind alle Elemente von $X$). Das hei\ss t, es
gibt zwei verschiedene Elemente $x_{i},x_{j}\in X$ mit $f\left( x_{i}\right)
=f\left( x_{j}\right) $. Mit anderen Worten: unter den $k$ Elementen
$f\left( x_{1}\right) ,f\left( x_{2}\right) ,\ldots,f\left( x_{k}\right)
$ sind mindestens zwei gleiche. Daher ist die M\"{a}chtigkeit der Menge
$\left\{ f\left( x_{1}\right) ,f\left( x_{2}\right) ,\ldots,f\left(
x_{k}\right) \right\} $ h\"{o}chstens $k-1$. Mit anderen Worten: $\left\vert
\left\{ f\left( x_{1}\right) ,f\left( x_{2}\right) ,\ldots,f\left(
x_{k}\right) \right\} \right\vert \leq k-1$. Wegen
(\ref{pf.prop.pie.surj1.Y=}) vereinfacht sich dies zu $\left\vert Y\right\vert
\leq k-1$. Also haben wir $k=\left\vert X\right\vert \leq\left\vert
Y\right\vert \leq k-1$, was absurd ist. Dieser Widerspruch vollendet den
Beweis von Proposition \ref{prop.pie.surj1}.
\end{proof}
\begin{corollary}
\label{cor.pie.surj2}Seien $X$ und $Y$ zwei endliche Mengen mit $\left\vert
X\right\vert <\left\vert Y\right\vert $. Dann gibt es keine surjektiven
Abbildungen von $X$ nach $Y$.
\end{corollary}
\begin{proof}
[Beweisskizze.]G\"{a}be es eine surjektive Abbildung von $X$ nach $Y$, dann
w\"{a}re diese Abbildung (laut Proposition \ref{prop.pie.surj1}) bijektiv, was
zu $\left\vert X\right\vert =\left\vert Y\right\vert $ f\"{u}hren w\"{u}rde.
Aber dies w\"{u}rde $\left\vert X\right\vert <\left\vert Y\right\vert $ widersprechen.
\end{proof}
\begin{proof}
[L\"{o}sungsskizze zu Aufgabe \ref{aufg.pie-prot}.]\textbf{(a)} Sei $S$ eine
endliche Menge. Wir m\"{u}ssen die Gleichheit (\ref{eq.simple-cancellation})
beweisen. Im Falle von $S=\varnothing$ ist dies trivial (auf der linken Seite
steht eine Summe mit dem einzigen Summanden $\left( -1\right) ^{\left\vert
\varnothing\right\vert }=\left( -1\right) ^{0}=1$; auf der rechten steht
$\left[ S=\varnothing\right] =1$). Also nehmen wir o. B. d. A. an, dass
$S\neq\varnothing$ ist. Dann hat die Menge $S$ mindestens ein Element. Es gibt
also ein $s\in S$. Fixiere ein solches $s$.
Da $S\neq\varnothing$ ist, haben wir $\left[ S=\varnothing\right] =0$. Die
zu beweisende Gleichheit (\ref{eq.simple-cancellation}) vereinfacht sich also
zu $\sum_{I\subseteq S}\left( -1\right) ^{\left\vert I\right\vert }=0$.
Wir wollen jetzt Lemma \ref{lem.srinvol-prot.bijprinc1} anwenden -- etwa so
wie in unserer L\"{o}sung von Aufgabe \ref{aufg.srinvol-prot} \textbf{(b)},
aber einfacher, weil diesmal jede Teilmenge von $S$ einen Partner finden soll
(denn die Summe soll sich zu $0$ vereinfachen).
Dazu setzen wir $\mathcal{A}=\left\{ \text{alle Teilmengen von }S\right\} $
und $\mathcal{X}=\mathcal{A}$. Wir definieren jetzt eine Bijektion
$f:\mathcal{X}\rightarrow\mathcal{X}$ folgenderma\ss en: F\"{u}r jedes
$I\in\mathcal{X}$ setzen wir%
\[
f\left( I\right) =%
\begin{cases}
I\setminus\left\{ s\right\} , & \text{wenn }s\in I;\\
I\cup\left\{ s\right\} , & \text{wenn }s\notin I.
\end{cases}
\]
Dass dieses $f$ tats\"{a}chlich wohldefiniert und eine Bijektion ist, ist
ziemlich klar (wieder einmal ist $f$ nicht nur eine Bijektion, sondern
erf\"{u}llt $f\circ f=\operatorname*{id}$). Au\ss erdem gilt
\[
\left( -1\right) ^{\left\vert f\left( I\right) \right\vert }=-\left(
-1\right) ^{\left\vert I\right\vert }\ \ \ \ \ \ \ \ \ \ \text{f\"{u}r alle
}I\in\mathcal{X},
\]
denn $\left\vert f\left( I\right) \right\vert $ unterscheidet sich von
$\left\vert I\right\vert $ immer um $\pm1$. Lemma
\ref{lem.srinvol-prot.bijprinc1} liefert also%
\begin{align*}
\sum_{I\in\mathcal{A}}\left( -1\right) ^{\left\vert I\right\vert } &
=\sum_{I\in\mathcal{A}\setminus\mathcal{X}}\left( -1\right) ^{\left\vert
I\right\vert }=\left( \text{leere Summe}\right) \\
& \ \ \ \ \ \ \ \ \ \ \left( \text{denn wegen }\mathcal{X}=\mathcal{A}\text{
ist }\mathcal{A}\setminus\mathcal{X}\text{ eine leere Menge}\right) \\
& =0.
\end{align*}
Doch das Summenzeichen $\sum_{I\in\mathcal{A}}$ auf der linken Seite ist
\"{a}quivalent zu $\sum_{I\subseteq S}$ (da $\mathcal{A}=\left\{ \text{alle
Teilmengen von }S\right\} $ ist). Damit haben wir gezeigt, dass
$\sum_{I\subseteq S}\left( -1\right) ^{\left\vert I\right\vert }=0$ gilt.
Damit ist (\ref{eq.simple-cancellation}) bewiesen. Aufgabe \ref{aufg.pie-prot}
\textbf{(a)} ist also gel\"{o}st.
(Ein \"{a}hnlicher Beweis von (\ref{eq.simple-cancellation}) findet sich
ausgef\"{u}hrt in \cite[\S 2.9.2, Second proof of Proposition 2.9.10]{19fco}.
Man kann (\ref{eq.simple-cancellation}) auch auf die
Binomialkoeffizienten-Identit\"{a}t $\sum_{k=0}^{n}\left( -1\right)
^{k}\dbinom{n}{k}=0$ reduzieren.)
\bigskip
\textbf{(b)} (Details in \cite[\S 2.9.3, proof of Theorem 2.9.9]{19fco}.) Der
Ansatz ist folgender: Wir halten ein Element $s\in U$ fest und schauen uns an,
wie oft in der Summe
\begin{equation}
\sum_{I\subseteq\left[ n\right] }\left( -1\right) ^{\left\vert
I\right\vert }\left\vert \bigcap_{i\in I}A_{i}\right\vert
\label{pf.thm.pie.bU.plan-sum}%
\end{equation}
dieses Element $s$ \textquotedblleft gez\"{a}hlt\textquotedblright\ wird. Das
hei\ss t, statt (\ref{pf.thm.pie.bU.plan-sum}) direkt auszurechnen, berechnen
wir die Summe $\sum_{I\subseteq\left[ n\right] }\left( -1\right)
^{\left\vert I\right\vert }\left[ s\in\bigcap_{i\in I}A_{i}\right] $ f\"{u}r
ein einzelnes $s\in U$. Dann summieren wir die Ergebnisse \"{u}ber alle $s\in
U$, und erhalten (wegen Proposition \ref{prop.count.rollcall} \textbf{(a)})
genau die Summe (\ref{pf.thm.pie.bU.plan-sum}).
Hier sind die Details: Fixiere $s\in U$. Definiere eine Teilmenge $S$ von
$\left[ n\right] $ durch%
\[
S=\left\{ i\in\left[ n\right] \ \mid\ s\in A_{i}\right\} .
\]
Nun sind die zwei Aussagen \textquotedblleft$S=\varnothing$\textquotedblright%
\ und \textquotedblleft$s\in U\setminus\left( A_{1}\cup A_{2}\cup\cdots\cup
A_{n}\right) $\textquotedblright\ \"{a}quivalent (dies folgt leicht aus der
Definition von $S$). Da \"{a}quivalente Aussagen gleiche Wahrheitswerte haben,
gilt also%
\begin{equation}
\left[ S=\varnothing\right] =\left[ s\in U\setminus\left( A_{1}\cup
A_{2}\cup\cdots\cup A_{n}\right) \right] . \label{pf.thm.pie.b.S=nothing=}%
\end{equation}
Andererseits sei $I$ eine beliebige Teilmenge von $\left[ n\right] $. Dann
sind die zwei Aussagen \textquotedblleft$s\in\bigcap_{i\in I}A_{i}%
$\textquotedblright\ und \textquotedblleft$I\subseteq S$\textquotedblright%
\ \"{a}quivalent (warum?\footnote{Man erkennt hier, warum wir den
\textquotedblleft leeren\textquotedblright\ Durchschnitt $\bigcap
_{i\in\varnothing}A_{i}$ als $U$ definiert haben: Dies hat n\"{a}mlich zur
Folge, dass $\bigcap_{i\in I}A_{i}$ immer (also auch f\"{u}r $I=\varnothing$)
gleich der Menge aller $t\in U$ ist, die $t\in A_{i}$ f\"{u}r alle $i\in I$
erf\"{u}llen. (Im Fall von $I=\varnothing$ ist \textquotedblleft$t\in A_{i}$
f\"{u}r alle $i\in I$\textquotedblright\ eine leere Aussage, und gilt also
f\"{u}r alle $t\in U$.) Dies wird hier ausgenutzt.}). Folglich sind ihre
Wahrheitswerte gleich, d.h., wir haben%
\begin{equation}
\left[ s\in\bigcap_{i\in I}A_{i}\right] =\left[ I\subseteq S\right] .
\label{pf.thm.pie.b.xincap}%
\end{equation}
Vergessen wir wieder, dass wir $I$ fixiert haben. Wir haben also
(\ref{pf.thm.pie.b.xincap}) f\"{u}r jede Teilmenge $I$ von $\left[ n\right]
$ bewiesen.
Nun ist
\begin{align}
& \sum_{I\subseteq\left[ n\right] }\left( -1\right) ^{\left\vert
I\right\vert }\underbrace{\left[ s\in\bigcap_{i\in I}A_{i}\right]
}_{\substack{=\left[ I\subseteq S\right] \\\text{(nach
(\ref{pf.thm.pie.b.xincap}))}}}\nonumber\\
& =\sum_{I\subseteq\left[ n\right] }\left( -1\right) ^{\left\vert
I\right\vert }\left[ I\subseteq S\right] \nonumber\\
& =\underbrace{\sum_{\substack{I\subseteq\left[ n\right] ;\\I\subseteq S}%
}}_{\substack{=\sum_{I\subseteq S}\\\text{(denn jede Teilmenge }I\text{ von
}S\\\text{ist eine Teilmenge von }\left[ n\right] \text{)}}}\left(
-1\right) ^{\left\vert I\right\vert }\underbrace{\left[ I\subseteq S\right]
}_{\substack{=1\\\text{(denn }I\subseteq S\text{)}}}+\sum
_{\substack{I\subseteq\left[ n\right] ;\\I\not \subseteq S}}\left(
-1\right) ^{\left\vert I\right\vert }\underbrace{\left[ I\subseteq S\right]
}_{\substack{=0\\\text{(denn }I\not \subseteq S\text{)}}}\nonumber\\
& =\sum_{I\subseteq S}\left( -1\right) ^{\left\vert I\right\vert
}+\underbrace{\sum_{\substack{I\subseteq\left[ n\right] ;\\I\not \subseteq
S}}\left( -1\right) ^{\left\vert I\right\vert }0}_{=0}=\sum_{I\subseteq
S}\left( -1\right) ^{\left\vert I\right\vert }=\left[ S=\varnothing\right]
\ \ \ \ \ \ \ \ \ \ \left( \text{nach (\ref{eq.simple-cancellation})}\right)
\nonumber\\
& =\left[ s\in U\setminus\left( A_{1}\cup A_{2}\cup\cdots\cup A_{n}\right)
\right] \label{pf.thm.pie.b.xsum}%
\end{align}
(nach (\ref{pf.thm.pie.b.S=nothing=})).
Vergessen wir nun, dass wir $s$ fixiert haben. Wir haben also
(\ref{pf.thm.pie.b.xsum}) f\"{u}r jedes $s\in U$ bewiesen. Nun gilt
\begin{align*}
& \sum_{I\subseteq\left[ n\right] }\left( -1\right) ^{\left\vert
I\right\vert }\underbrace{\left\vert \bigcap_{i\in I}A_{i}\right\vert
}_{\substack{=\sum_{s\in U}\left[ s\in\bigcap_{i\in I}A_{i}\right]
\\\text{(laut Proposition \ref{prop.count.rollcall} \textbf{(a),}%
}\\\text{angewandt auf }S=U\text{ und }T=\bigcap_{i\in I}A_{i}\text{)}}}\\
& =\sum_{I\subseteq\left[ n\right] }\left( -1\right) ^{\left\vert
I\right\vert }\sum_{s\in U}\left[ s\in\bigcap_{i\in I}A_{i}\right]
=\underbrace{\sum_{I\subseteq\left[ n\right] }\ \ \sum_{s\in U}%
}_{\substack{=\sum_{s\in U}\ \ \sum_{I\subseteq\left[ n\right] }\\\text{(da
zwei voneinander unabh\"{a}ngige}\\\text{Summenzeichen immer vertauscht}%
\\\text{werden k\"{o}nnen)}}}\left( -1\right) ^{\left\vert I\right\vert
}\left[ s\in\bigcap_{i\in I}A_{i}\right] \\
& =\sum_{s\in U}\ \ \underbrace{\sum_{I\subseteq\left[ n\right] }\left(
-1\right) ^{\left\vert I\right\vert }\left[ s\in\bigcap_{i\in I}%
A_{i}\right] }_{\substack{=\left[ s\in U\setminus\left( A_{1}\cup A_{2}%
\cup\cdots\cup A_{n}\right) \right] \\\text{(nach (\ref{pf.thm.pie.b.xsum}%
))}}}=\sum_{s\in U}\left[ s\in U\setminus\left( A_{1}\cup A_{2}\cup
\cdots\cup A_{n}\right) \right] .
\end{align*}
Andererseits ist%
\[
\left\vert U\setminus\left( A_{1}\cup A_{2}\cup\cdots\cup A_{n}\right)
\right\vert =\sum_{s\in U}\left[ s\in U\setminus\left( A_{1}\cup A_{2}%
\cup\cdots\cup A_{n}\right) \right]
\]
(laut Proposition \ref{prop.count.rollcall} \textbf{(a)}, angewandt auf $S=U$
und $T=U\setminus\left( A_{1}\cup A_{2}\cup\cdots\cup A_{n}\right) $).
Abgleich dieser zwei Gleichheiten ergibt%
\[
\left\vert U\setminus\left( A_{1}\cup A_{2}\cup\cdots\cup A_{n}\right)
\right\vert =\sum_{I\subseteq\left[ n\right] }\left( -1\right)
^{\left\vert I\right\vert }\left\vert \bigcap_{i\in I}A_{i}\right\vert .
\]
Somit ist Aufgabe \ref{aufg.pie-prot} \textbf{(b)} gel\"{o}st.
[\textit{Bemerkung:} Die Sylvestersche Siebformel (\ref{eq.thm.pie.b.claim})
ist wohl eine der bekanntesten Aussagen auf diesem Aufgabenblatt, und kommt in
der Literatur in vielen Formen vor. So kann man z. B. die Menge $U\setminus
\left( A_{1}\cup A_{2}\cup\cdots\cup A_{n}\right) $ umschreiben als
$A_{1}^{c}\cap A_{2}^{c}\cap\cdots\cap A_{n}^{c}$, wobei $A_{i}^{c}%
:=U\setminus A_{i}$ f\"{u}r jedes $i\in\left[ n\right] $ gesetzt wird. So
umgeschrieben kommt (\ref{eq.thm.pie.b.claim}) in \cite[Theorem 1]{White10}
vor, wo eine kombinatorische Version von unserer obigen L\"{o}sung gegeben
wird. In \cite{Smid09} wird (\ref{eq.thm.pie.b.claim}) in der \"{a}quivalenten
Form%
\[
\left\vert A_{1}\cup A_{2}\cup\cdots\cup A_{n}\right\vert =\sum
_{\substack{I\subseteq\left[ n\right] ;\\I\neq\varnothing}}\left(
-1\right) ^{\left\vert I\right\vert -1}\left\vert \bigcap_{i\in I}%
A_{i}\right\vert
\]
formuliert (und durch Induktion nach $n$ bewiesen); die \"{A}quivalenz
zwischen dieser Gleichung und (\ref{eq.thm.pie.b.claim}) sieht man ein, indem
man eine dieser Gleichungen von $\left\vert U\right\vert =\left\vert
U\right\vert $ subtrahiert.]
\bigskip
\textbf{(c)} (Siehe \cite[\S 2.9.5]{19fco} f\"{u}r Details.) Sei $U$ die Menge
aller Permutationen von $\left[ n\right] $. F\"{u}r jedes $i\in\left[
n\right] $ setzen wir%
\begin{equation}
A_{i}=\left\{ \sigma\in U\ \mid\ \sigma\left( i\right) =i\right\} .
\label{pf.thm.count.dera.teasers.d.Ai=}%
\end{equation}
Somit haben wir $n$ Teilmengen $A_{1},A_{2},\ldots,A_{n}$ von $U$ definiert.
Die Definition von Derangements l\"{a}\ss t sich nun folgenderma\ss en
umschreiben:%
\[
\left\{ \text{Derangements von }\left[ n\right] \right\} =U\setminus
\left( A_{1}\cup A_{2}\cup\cdots\cup A_{n}\right) .
\]
Also ist%
\begin{align}
& \left( \text{Anzahl aller Derangements von }\left[ n\right] \right)
\nonumber\\
& =\left\vert U\setminus\left( A_{1}\cup A_{2}\cup\cdots\cup A_{n}\right)
\right\vert =\sum_{I\subseteq\left[ n\right] }\left( -1\right)
^{\left\vert I\right\vert }\left\vert \bigcap_{i\in I}A_{i}\right\vert
\label{sol.pie-prot.c.2}%
\end{align}
laut Aufgabe \ref{aufg.pie-prot} \textbf{(b)}.
Wir wollen nun die M\"{a}chtigkeiten $\left\vert \bigcap_{i\in I}%
A_{i}\right\vert $ auf der rechten Seite von (\ref{sol.pie-prot.c.2})
bestimmen. Dazu fixieren wir eine Teilmenge $I$ von $\left[ n\right] $. Dann
ist $\bigcap_{i\in I}A_{i}$ die Menge aller Permutationen $\sigma$ von
$\left[ n\right] $, die $\sigma\left( i\right) =i$ f\"{u}r alle $i\in I$
erf\"{u}llen\footnote{Pr\"{u}fe nach, dass dies auch f\"{u}r $I=\varnothing$
gilt! (Wir haben ja $\bigcap_{i\in I}A_{i}$ f\"{u}r $I=\varnothing$ separat
definiert.)}. Wir behaupten, es gibt genau $\left( n-\left\vert I\right\vert
\right) !$ solche Permutationen. In der Tat k\"{o}nnen wir so eine
Permutation $\sigma$ ja dadurch aufbauen, dass wir zun\"{a}chst ihre Werte auf
allen Elementen von $I$ festlegen (hier haben wir keine Wahl, denn die
Bedingung \textquotedblleft$\sigma\left( i\right) =i$ f\"{u}r alle $i\in
I$\textquotedblright\ legt diese Werte eindeutig fest), und dann die
restlichen $n-\left\vert I\right\vert $ Elemente von $\left[ n\right] $
unter den restlichen $n-\left\vert I\right\vert $ Werten von $\sigma$
verteilen (hier haben wir $\left( n-\left\vert I\right\vert \right) !$ viele
M\"{o}glichkeiten, denn wir legen hier im Wesentlichen eine Permutation der
$\left( n-\left\vert I\right\vert \right) $-elementigen Menge $\left[
n\right] \setminus I$ fest). Es gibt also genau $\left( n-\left\vert
I\right\vert \right) !$ Permutationen $\sigma$ von $\left[ n\right] $, die
$\sigma\left( i\right) =i$ f\"{u}r alle $i\in I$ erf\"{u}llen. Da
$\bigcap_{i\in I}A_{i}$ die Menge all dieser Permutationen ist, haben wir also
gezeigt, dass%
\begin{equation}
\left\vert \bigcap_{i\in I}A_{i}\right\vert =\left( n-\left\vert I\right\vert
\right) ! \label{sol.pie-prot.c.5}%
\end{equation}
ist.
Vergessen wir nun, dass wir $I$ fixiert haben. F\"{u}r jede Teilmenge $I$ von
$\left[ n\right] $ haben wir also (\ref{sol.pie-prot.c.5}) bewiesen. Damit
wird (\ref{sol.pie-prot.c.2}) zu%
\begin{align*}
& \left( \text{Anzahl aller Derangements von }\left[ n\right] \right) \\
& =\sum_{I\subseteq\left[ n\right] }\left( -1\right) ^{\left\vert
I\right\vert }\underbrace{\left\vert \bigcap_{i\in I}A_{i}\right\vert
}_{\substack{=\left( n-\left\vert I\right\vert \right) !\\\text{(laut
(\ref{sol.pie-prot.c.5}))}}}=\sum_{I\subseteq\left[ n\right] }\left(
-1\right) ^{\left\vert I\right\vert }\left( n-\left\vert I\right\vert
\right) !\\
& =\sum_{k=0}^{n}\ \ \sum_{\substack{I\subseteq\left[ n\right]
;\\\left\vert I\right\vert =k}}\underbrace{\left( -1\right) ^{\left\vert
I\right\vert }\left( n-\left\vert I\right\vert \right) !}%
_{\substack{=\left( -1\right) ^{k}\left( n-k\right) !\\\text{(denn
}\left\vert I\right\vert =k\text{)}}}\\
& \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{hier haben wir die Summe nach dem Wert von }\left\vert I\right\vert
\text{ aufgespalten,}\\
\text{denn f\"{u}r jede Teilmenge }I\text{ von }\left[ n\right] \text{ ist
}\left\vert I\right\vert \in\left\{ 0,1,\ldots,n\right\}
\end{array}
\right) \\
& =\sum_{k=0}^{n}\ \ \underbrace{\sum_{\substack{I\subseteq\left[ n\right]
;\\\left\vert I\right\vert =k}}\left( -1\right) ^{k}\left( n-k\right)
!}_{=\left( -1\right) ^{k}\left( n-k\right) !\cdot\left( \text{Anzahl
aller Teilmengen }I\text{ von }\left[ n\right] \text{ mit }\left\vert
I\right\vert =k\right) }\\
& =\sum_{k=0}^{n}\left( -1\right) ^{k}\left( n-k\right) !\cdot
\underbrace{\left( \text{Anzahl aller Teilmengen }I\text{ von }\left[
n\right] \text{ mit }\left\vert I\right\vert =k\right) }_{\substack{=\left(
\text{Anzahl aller }k\text{-elementigen Teilmengen von }\left[ n\right]
\right) \\=\dbinom{n}{k}\\\text{(laut der kombinatorischen Interpretation der
Binomialkoeffizienten)}}}\\
& =\sum_{k=0}^{n}\left( -1\right) ^{k}\left( n-k\right) !\cdot
\underbrace{\dbinom{n}{k}}_{\substack{=\dfrac{n!}{k!\cdot\left( n-k\right)
!}\\\text{(laut der Fakult\"{a}tenformel f\"{u}r}%
\\\text{Binomialkoeffizienten)}}}=\sum_{k=0}^{n}\left( -1\right) ^{k}\left(
n-k\right) !\cdot\dfrac{n!}{k!\cdot\left( n-k\right) !}\\
& =\sum_{k=0}^{n}\left( -1\right) ^{k}\dfrac{n!}{k!}.
\end{align*}
Damit ist Aufgabe \ref{aufg.pie-prot} \textbf{(c)} gel\"{o}st.
\bigskip
\textbf{(d)} (Details finden sich in \cite[\S 2.9.4]{19fco}.) Sei $U$ die
Menge aller Abbildungen von $\left[ m\right] $ nach $\left[ n\right] $.
(Kurzgefasst: Sei $U=\left[ n\right] ^{\left[ m\right] }$.)
F\"{u}r jedes $i\in\left[ n\right] $ sei%
\begin{align*}
A_{i} & =\left\{ f:\left[ m\right] \rightarrow\left[ n\right]
\ \mid\ i\text{ ist kein Wert von }f\right\} \\
& =\left\{ f:\left[ m\right] \rightarrow\left[ n\right] \ \mid\ f\left(
x\right) \neq i\text{ f\"{u}r alle }x\in\left[ m\right] \right\} .
\end{align*}
Damit haben wir $n$ Teilmengen $A_{1},A_{2},\ldots,A_{n}$ von $U$ definiert.
Es ist leicht einzusehen, dass%
\[
\left\{ \text{surjektive Abbildungen }\left[ m\right] \rightarrow\left[
n\right] \right\} =U\setminus\left( A_{1}\cup A_{2}\cup\cdots\cup
A_{n}\right)
\]
ist (denn eine Abbildung von $\left[ m\right] $ nach $\left[ n\right] $
ist genau dann surjektiv, wenn jedes Element von $\left[ n\right] $ zu ihren
Werten geh\"{o}rt, also genau dann, wenn sie in keiner der Mengen $A_{1}%
,A_{2},\ldots,A_{n}$ enthalten ist). Also ist%
\begin{align}
& \left( \text{Anzahl aller surjektiven Abbildungen von }\left[ m\right]
\text{ nach }\left[ n\right] \right) \nonumber\\
& =\left\vert U\setminus\left( A_{1}\cup A_{2}\cup\cdots\cup A_{n}\right)
\right\vert =\sum_{I\subseteq\left[ n\right] }\left( -1\right)
^{\left\vert I\right\vert }\left\vert \bigcap_{i\in I}A_{i}\right\vert
\label{sol.pie-prot.d.2}%
\end{align}
laut Aufgabe \ref{aufg.pie-prot} \textbf{(b)}.
Wir wollen wieder die M\"{a}chtigkeiten auf der rechten Seite bestimmen. Dazu
fixieren wir eine Teilmenge $I$ von $\left[ n\right] $. Dann ist
$\bigcap_{i\in I}A_{i}$ die Menge aller Abbildungen von $\left[ m\right] $
nach $\left[ n\right] $, die keins der Elemente von $I$ als Wert annehmen
(d.h., deren Wertemenge zu $I$ disjunkt ist). Diese Abbildungen k\"{o}nnen wir
gleichsetzen mit den Abbildungen von $\left[ m\right] $ nach $\left[
n\right] \setminus I$ (pedantisch gesehen unterscheiden sie sich in der
Zielmenge, aber dies ist auch der einzige Unterschied). Somit ist ihre Anzahl
gleich $\left\vert \left[ n\right] \setminus I\right\vert ^{\left\vert
\left[ m\right] \right\vert }$. Da $\bigcap_{i\in I}A_{i}$ die Menge all
dieser Abbildungen ist, haben wir hiermit gezeigt, dass%
\begin{equation}
\left\vert \bigcap_{i\in I}A_{i}\right\vert =\left\vert \left[ n\right]
\setminus I\right\vert ^{\left\vert \left[ m\right] \right\vert }
\label{sol.pie-prot.d.5}%
\end{equation}
gilt.
Vergessen wir, dass wir $I$ fixiert haben. Wir haben also
(\ref{sol.pie-prot.d.5}) f\"{u}r jede Teilmenge $I$ von $\left[ n\right] $
bewiesen. Damit wird (\ref{sol.pie-prot.d.2}) zu%
\begin{align*}
& \left( \text{Anzahl aller surjektiven Abbildungen von }\left[ m\right]
\text{ nach }\left[ n\right] \right) \\
& =\sum_{I\subseteq\left[ n\right] }\left( -1\right) ^{\left\vert
I\right\vert }\underbrace{\left\vert \bigcap_{i\in I}A_{i}\right\vert
}_{\substack{=\left\vert \left[ n\right] \setminus I\right\vert ^{\left\vert
\left[ m\right] \right\vert }\\\text{(laut (\ref{sol.pie-prot.d.5}))}}%
}=\sum_{I\subseteq\left[ n\right] }\left( -1\right) ^{\left\vert
I\right\vert }\underbrace{\left\vert \left[ n\right] \setminus I\right\vert
^{\left\vert \left[ m\right] \right\vert }}_{\substack{=\left( n-\left\vert
I\right\vert \right) ^{m}\\\text{(denn }\left\vert \left[ n\right]
\setminus I\right\vert =n-\left\vert I\right\vert \\\text{und }\left\vert
\left[ m\right] \right\vert =m\text{)}}}\\
& =\sum_{k=0}^{n}\ \ \sum_{\substack{I\subseteq\left[ n\right]
;\\\left\vert I\right\vert =k}}\underbrace{\left( -1\right) ^{\left\vert
I\right\vert }\left( n-\left\vert I\right\vert \right) ^{m}}%
_{\substack{=\left( -1\right) ^{k}\left( n-k\right) ^{m}\\\text{(denn
}\left\vert I\right\vert =k\text{)}}}\\
& \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{hier haben wir, wie schon in der L\"{o}sung von Teil \textbf{(c)},
die}\\
\text{Summe nach dem Wert von }\left\vert I\right\vert \text{ aufgespalten}%
\end{array}
\right) \\
& =\sum_{k=0}^{n}\ \ \underbrace{\sum_{\substack{I\subseteq\left[ n\right]
;\\\left\vert I\right\vert =k}}\left( -1\right) ^{k}\left( n-k\right)
^{m}}_{=\left( -1\right) ^{k}\left( n-k\right) ^{m}\cdot\left(
\text{Anzahl aller Teilmengen }I\text{ von }\left[ n\right] \text{ mit
}\left\vert I\right\vert =k\right) }\\
& =\sum_{k=0}^{n}\left( -1\right) ^{k}\left( n-k\right) ^{m}%
\cdot\underbrace{\left( \text{Anzahl aller Teilmengen }I\text{ von }\left[
n\right] \text{ mit }\left\vert I\right\vert =k\right) }_{\substack{=\left(
\text{Anzahl aller }k\text{-elementigen Teilmengen von }\left[ n\right]
\right) \\=\dbinom{n}{k}\\\text{(laut der kombinatorischen Interpretation der
Binomialkoeffizienten)}}}\\
& =\sum_{k=0}^{n}\underbrace{\left( -1\right) ^{k}}_{=\left( -1\right)
^{n-\left( n-k\right) }}\left( n-k\right) ^{m}\cdot\underbrace{\dbinom
{n}{k}}_{\substack{=\dbinom{n}{n-k}\\\text{(laut (\ref{eq.bas.symmetry}))}%
}}=\sum_{k=0}^{n}\left( -1\right) ^{n-\left( n-k\right) }\left(
n-k\right) ^{m}\cdot\dbinom{n}{n-k}\\
& =\sum_{i=0}^{n}\left( -1\right) ^{n-i}i^{m}\cdot\dbinom{n}{i}%
\ \ \ \ \ \ \ \ \ \ \left( \text{hier haben wir }i\text{ f\"{u}r }n-k\text{
substituiert}\right) \\
& =\sum_{i=0}^{n}\left( -1\right) ^{n-i}\dbinom{n}{i}i^{m}.
\end{align*}
Damit ist Aufgabe \ref{aufg.pie-prot} \textbf{(d)} gel\"{o}st.
\bigskip
\textbf{(e)} Seien $n,m\in\mathbb{N}$. Sei $S$ die Menge aller surjektiven
Abbildungen von $\left[ m\right] $ nach $\left[ n\right] $. Laut Aufgabe
\ref{aufg.pie-prot} \textbf{(d)} ist dann
\begin{equation}
\left\vert S\right\vert =\sum_{i=0}^{n}\left( -1\right) ^{n-i}\dbinom{n}%
{i}i^{m}. \label{sol.pie-prot.e.used}%
\end{equation}
Wir m\"{u}ssen aber zeigen, dass $\sum_{i=0}^{n}\left( -1\right)
^{n-i}\dbinom{n}{i}i^{m}$ durch $n!$ teilbar ist. Wegen
(\ref{sol.pie-prot.e.used}) reicht es hierf\"{u}r aus, zu zeigen, dass
$\left\vert S\right\vert $ durch $n!$ teilbar ist.
Wie zeigen wir dies? Die Idee ist, dass wir eine \"{A}quivalenzrelation auf
der Menge $S$ einf\"{u}hren, von der jede \"{A}quivalenzklasse genau $n!$
viele Elemente hat. Daraus wird dann folgen, dass $\left\vert S\right\vert $
gleich $n!$ mal der Anzahl dieser \"{A}quivalenzklassen ist, und somit wird
$\left\vert S\right\vert $ durch $n!$ teilbar sein.
Die richtige \"{A}quivalenzrelation l\"{a}\ss t sich folgenderma\ss en definieren:
Sei $P$ die Menge aller Permutationen von $\left[ n\right] $. Da die
Permutationen von $\left[ n\right] $ nichts anderes sind als die bijektiven
Abbildungen von $\left[ n\right] $ nach $\left[ n\right] $, sehen wir, dass
\begin{itemize}
\item die Verkettung $\sigma\circ\tau$ von zwei Permutationen $\sigma,\tau\in
P$ wieder eine Permutation in $P$ ist;
\item die Identit\"{a}tsabbildung $\operatorname*{id}:\left[ n\right]
\rightarrow\left[ n\right] $ eine Permutation in $P$ ist;
\item die Umkehrung $\sigma^{-1}$ einer jeden Permutation $\sigma\in P$ wieder
eine Permutation in $P$ ist (und insbesondere wohldefiniert ist, da bijektive
Abbildungen immer Umkehrungen haben).
\end{itemize}
\noindent(Algebraiker fassen diese Fakten gerne in einem Satz zusammen:
\textquotedblleft Die Menge $P$ ist eine Gruppe bez\"{u}glich Verkettung, mit
neutralem Element $\operatorname*{id}$.\textquotedblright)
Au\ss erdem wissen wir, da\ss \ die Menge $\left[ n\right] $ genau $n!$
Permutationen hat; das hei\ss t, $\left\vert P\right\vert =n!$.
F\"{u}r alle $f\in S$ und $\sigma\in P$ ist ferner $\sigma\circ f\in S$. (Denn
wenn $f$ surjektiv und $\sigma$ bijektiv ist, dann ist auch $\sigma\circ f$ surjektiv.)
Jetzt definieren wir eine bin\"{a}re Relation $\sim$ auf der Menge $S$, indem
wir%
\[
\left( f\sim g\right) \ \Longleftrightarrow\ \left( \text{es gibt ein
}\sigma\in P\text{ mit }g=\sigma\circ f\right)
\]
f\"{u}r je zwei surjektive Abbildungen $f,g\in S$ setzen. Mit anderen Worten:
Zwei Abbildungen $f$ und $g$ in $S$ sind genau dann \"{a}quivalent
(bez\"{u}glich $\sim$), wenn eine aus der anderen durch Verkettung mit einer
Permutation von $\left[ n\right] $ hervorgeht.\footnote{\textit{Beispiel:}
Seien $m=5$ und $n=3$. Sei $f:\left[ m\right] \rightarrow\left[ n\right] $
die Abbildung, die $1,2,3,4,5$ auf $2,1,3,2,1$ (in dieser Reihenfolge)
abbildet. Sei $g:\left[ m\right] \rightarrow\left[ n\right] $ die
Abbildung, die $1,2,3,4,5$ auf $3,2,1,3,2$ (in dieser Reihenfolge) abbildet.
Beide diese Abbildungen $f$ und $g$ sind surjektiv und liegen daher in $S$.
Ferner gibt es ein $\sigma\in P$ (also eine Permutation $\sigma$ von $\left[
n\right] =\left[ 3\right] $) mit $g=\sigma\circ f$; und zwar ist dieses
$\sigma$ diejenige Permutation von $\left[ 3\right] $, die $1,2,3$ auf
$2,3,1$ (in diesr Reihenfolge) abbildet. Daher ist $f\sim g$.}
Diese Relation $\sim$ ist tats\"{a}chlich eine \"{A}quivalenzrelation, wie man
unschwer mithilfe der obengenannten Fakten \"{u}ber $P$ beweist. (So folgt z.
B. die Transitivit\"{a}t von $\sim$ daraus, dass die die Verkettung
$\sigma\circ\tau$ von zwei Permutationen $\sigma,\tau\in P$ wieder eine
Permutation in $P$ ist.)
Da $\sim$ eine \"{A}quivalenzrelation ist, unterteilt sie die Menge $S$ in
(disjunkte und nichtleere) \"{A}quivalenzklassen. Wir m\"{u}ssen nur noch
zeigen, dass jede dieser \"{A}quivalenzklassen genau $n!$ viele Elemente hat.
Sei also $K$ eine \"{A}quivalenzklasse von $\sim$. Wir m\"{u}ssen zeigen, dass
$\left\vert K\right\vert =n!$ ist. Wir w\"{a}hlen ein beliebiges Element $f$
von $K$. Dann ist $K$ die \"{A}quivalenzklasse von $f$ (bez\"{u}glich der
Relation $\sim$). Wegen der Definition von $\sim$ bedeutet dies folgendes:%
\begin{equation}
K=\left\{ \sigma\circ f\ \mid\ \sigma\in P\right\} .
\label{sol.pie-prot.e.K=}%
\end{equation}
Hieraus w\"{u}rde schnell $\left\vert K\right\vert =n!$ folgen, wenn wir
w\"{u}ssten, dass die Abbildungen $\sigma\circ f$ f\"{u}r alle $\sigma\in P$
verschieden sind (denn $\left\vert P\right\vert =n!$). Sind sie es denn?
Ja, sind sie. Denn sind $\sigma$ und $\tau$ zwei verschiedene Permutationen in
$P$, dann gibt es ein $i\in\left[ n\right] $ mit $\sigma\left( i\right)
\neq\tau\left( i\right) $; und da $f$ surjektiv ist (denn $f\in K\subseteq
S$), gibt es zu diesem $i\in\left[ n\right] $ auch ein $j\in\left[
m\right] $ mit $i=f\left( j\right) $. F\"{u}r dieses $j$ gilt dann
\[
\left( \sigma\circ f\right) \left( j\right) =\sigma\left(
\underbrace{f\left( j\right) }_{=i}\right) =\sigma\left( i\right)
\neq\tau\left( \underbrace{i}_{=f\left( j\right) }\right) =\tau\left(
f\left( j\right) \right) =\left( \tau\circ f\right) \left( j\right) ,
\]
woraus nat\"{u}rlich $\sigma\circ f\neq\tau\circ f$ folgt. Wir haben also
gezeigt, dass $\sigma\circ f\neq\tau\circ f$ f\"{u}r je zwei verschiedene
Permutationen $\sigma$ und $\tau$ in $P$ gilt. Das hei\ss t, die Abbildungen
$\sigma\circ f$ f\"{u}r $\sigma\in P$ sind alle verschieden. Folglich ist
$\left\vert \left\{ \sigma\circ f\ \mid\ \sigma\in P\right\} \right\vert
=\left\vert P\right\vert =n!$. Wegen (\ref{sol.pie-prot.e.K=}) l\"{a}\ss t
sich dies umschreiben als $\left\vert K\right\vert =n!$, was uns gerade zum
Beweis gefehlt hat. Die L\"{o}sung von Aufgabe \ref{aufg.pie-prot}
\textbf{(e)} ist damit fertig.
\bigskip
\textbf{(f)} Sei $n\in\mathbb{N}$. Laut Proposition \ref{prop.pie.surj1}
(angewandt auf $X=\left[ n\right] $ und $Y=\left[ n\right] $) ist jede
surjektive Abbildung von $\left[ n\right] $ nach $\left[ n\right] $
automatisch bijektiv. Da die Umkehrung selbstverst\"{a}ndlich gilt, sind also
die surjektiven Abbildungen von $\left[ n\right] $ nach $\left[ n\right] $
dasselbe wie die bijektiven Abbildungen von $\left[ n\right] $ nach $\left[
n\right] $. Wir haben daher%
\begin{align*}
& \left\{ \text{surjektive Abbildungen von }\left[ n\right] \text{ nach
}\left[ n\right] \right\} \\
& =\left\{ \text{bijektive Abbildungen von }\left[ n\right] \text{ nach
}\left[ n\right] \right\} \\
& =\left\{ \text{Permutationen von }\left[ n\right] \right\}
\end{align*}
und folglich%
\begin{align*}
& \left( \text{Anzahl aller surjektiven Abbildungen von }\left[ n\right]
\text{ nach }\left[ n\right] \right) \\
& =\left( \text{Anzahl aller Permutationen von }\left[ n\right] \right)
=n!.
\end{align*}
Doch laut Aufgabe \ref{aufg.pie-prot} \textbf{(d)} (angewendet auf $m=n$) gilt%
\begin{align*}
& \left( \text{Anzahl aller surjektiven Abbildungen von }\left[ n\right]
\text{ nach }\left[ n\right] \right) \\
& =\sum_{i=0}^{n}\left( -1\right) ^{n-i}\dbinom{n}{i}i^{n}.
\end{align*}
Abgleich der letzten zwei Gleichungen ergibt $\sum_{i=0}^{n}\left( -1\right)
^{n-i}\dbinom{n}{i}i^{n}=n!$. Damit ist Aufgabe \ref{aufg.pie-prot}
\textbf{(f)} gel\"{o}st.
\bigskip
\textbf{(g)} Seien $n,m\in\mathbb{N}$ mit $m0$ ist, und wenn die Polynomfunktion $f$ den Grad $k$ hat, dann kann
man sogar sehen, dass $\Delta f$ eine Polynomfunktion von Grad exakt $k-1$
ist. Dies werden wir in Aussage 4 weiter unten beweisen. Wenn $k=0$ ist, dann
ist $\Delta f=0$, weil auf der rechten Seite von (\ref{sol.findiff-prot.a.2b})
eine leere Summe steht. Das Nullpolynom $0$ hat Grad $-\infty$, nicht $0-1$.)]
\medskip
Wir k\"{o}nnen das Zeichen $\Delta$ als einen \textit{Operator} auffassen --
d. h., als eine Abbildung $\mathbb{C}^{\mathbb{A}}\rightarrow\mathbb{C}%
^{\mathbb{A}}$ von der Menge $\mathbb{C}^{\mathbb{A}}=\left\{ \text{alle
Funktionen von }\mathbb{A}\text{ nach }\mathbb{C}\right\} $ in sich selbst.
Dieser Operator sendet jede Funktion $f\in\mathbb{C}^{\mathbb{A}}$ auf die
Funktion $\Delta f\in\mathbb{C}^{\mathbb{A}}$. Da $\Delta$ eine Abbildung von
der Menge $\mathbb{C}^{\mathbb{A}}$ in sich selbst ist, kann man $\Delta$
beliebig oft hintereinander ausf\"{u}hren -- d.h. die Verkettungspotenzen
$\Delta^{n}=\underbrace{\Delta\circ\Delta\circ\cdots\circ\Delta}_{n\text{ mal
}\Delta}$ f\"{u}r alle $n\in\mathbb{N}$ sind alle wohldefiniert (mit
$\Delta^{0}=\operatorname*{id}\nolimits_{\mathbb{C}^{\mathbb{A}}}$). Die
$n$-te Verkettungspotenz $\Delta^{n}$ \"{u}berf\"{u}hrt nat\"{u}rlich jede
Funktion $f\in\mathbb{C}^{\mathbb{A}}$ in die in der Aufgabe definierte $n$-te
Differenz $\Delta^{n}f$, denn genau so wurde letztere ja definiert.
Nun haben wir aber vorhin Aussage 1 bewiesen. Kurzgefasst besagt diese
Aussage, dass der Operator $\Delta$ jede Polynomfunktion in eine
Polynomfunktion mit mindestens um $1$ kleinerem Grad \"{u}berf\"{u}hrt.
Hieraus folgt, dass die $n$-fache Hintereinanderausf\"{u}hrung $\Delta^{n}$
dieses Operators $\Delta$ (f\"{u}r jedes $n\in\mathbb{N}$) jede
Polynomfunktion in eine Polynomfunktion mit mindestens um $n$ kleinerem Grad
\"{u}berf\"{u}hrt. Mit anderen Worten:
\begin{statement}
\textit{Aussage 2: }Seien $k\in\mathbb{N}\cup\left\{ -\infty\right\} $ und
$n\in\mathbb{N}$. Ist $f:\mathbb{A}\rightarrow\mathbb{C}$ eine Polynomfunktion
von Grad $\leq k$, dann ist $\Delta^{n}f$ eine Polynomfunktion von Grad $\leq
k-n$.
\end{statement}
(Strenggenommen muss man dies durch Induktion nach $n$ zeigen. Aber dies ist
v\"{o}llig straightforward.)
Aufgabe \ref{aufg.findiff-prot} \textbf{(a)} folgt sofort aus Aussage 2.
\bigskip
\textbf{(b)} Sei $f:\mathbb{A}\rightarrow\mathbb{C}$ eine beliebige Funktion.
Wir behaupten nun:
\begin{statement}
\textit{Aussage 3:} Es gilt%
\[
\left( \Delta^{n}f\right) \left( x\right) =\sum_{k=0}^{n}\left(
-1\right) ^{n-k}\dbinom{n}{k}f\left( x+k\right)
\ \ \ \ \ \ \ \ \ \ \text{f\"{u}r alle }x\in\mathbb{A}\text{ und }%
n\in\mathbb{N}.
\]
\end{statement}
[\textit{Beweis von Aussage 3:} Wir zeigen Aussage 3 durch Induktion nach $n$:
\textit{Induktionsanfang:} F\"{u}r $n=0$ behauptet Aussage 3, dass
\[
\left( \Delta^{0}f\right) \left( x\right) =\sum_{k=0}^{0}\left(
-1\right) ^{0-k}\dbinom{0}{k}f\left( x+k\right)
\ \ \ \ \ \ \ \ \ \ \text{f\"{u}r alle }x\in\mathbb{A}%
\]
gilt. Dies l\"{a}uft aber auf $f\left( x\right) =f\left( x\right) $ hinaus
(denn $\Delta^{0}f=f$ und $\dbinom{0}{0}=1$). Somit ist Aussage 3 f\"{u}r
$n=0$ bewiesen.
\textit{Induktionsschritt:} Sei $m\in\mathbb{N}$. Angenommen, dass Aussage 3
f\"{u}r $n=m$ gilt. Wir m\"{u}ssen zeigen, dass Aussage 3 auch f\"{u}r $n=m+1$ gilt.
Wir haben angenommen, dass Aussage 3 f\"{u}r $n=m$ gilt. Mit anderen Worten:
Es gilt%
\begin{equation}
\left( \Delta^{m}f\right) \left( x\right) =\sum_{k=0}^{m}\left(
-1\right) ^{m-k}\dbinom{m}{k}f\left( x+k\right)
\label{sol.findiff-prot.b.IH}%
\end{equation}
f\"{u}r alle $x\in\mathbb{A}$.
Sei nun $x\in\mathbb{A}$. Dann ist $\Delta^{m+1}f=\Delta\left( \Delta
^{m}f\right) $ (laut der rekursiven Definition von $\Delta^{n}f$),
also\footnote{Wer den Induktionsbeweis des Binomischen Satzes noch im
Ged\"{a}chtnis hat, wird ihn im Folgenden in abgewandelter Form
wiedererkennen. Dies ist kein gro\ss es Wunder, denn Aussage 2 l\"{a}\ss t
sich auch als Sonderfall des Binomischen Satzes im Operatorenring sehen -- und
der Beweis, den wir hier f\"{u}hren, folgt einfach dem Beweis des Binomischen
Satzes in diesem Sonderfall. Diesen Blickwinkel will ich hier aber nicht
genauer darstellen.}
\begin{align*}
& \left( \Delta^{m+1}f\right) \left( x\right) \\
& =\left( \Delta\left( \Delta^{m}f\right) \right) \left( x\right) \\
& =\underbrace{\left( \Delta^{m}f\right) \left( x+1\right) }%
_{\substack{=\sum_{k=0}^{m}\left( -1\right) ^{m-k}\dbinom{m}{k}f\left(
x+1+k\right) \\\text{(nach (\ref{sol.findiff-prot.b.IH}),}\\\text{angewandt
auf }x+1\text{ statt }x\text{)}}}-\underbrace{\left( \Delta^{m}f\right)
\left( x\right) }_{\substack{=\sum_{k=0}^{m}\left( -1\right) ^{m-k}%
\dbinom{m}{k}f\left( x+k\right) \\\text{(nach (\ref{sol.findiff-prot.b.IH}%
))}}}\\
& \ \ \ \ \ \ \ \ \ \ \left( \text{laut der Definition von }\Delta\left(
\Delta^{m}f\right) \right) \\
& =\sum_{k=0}^{m}\left( -1\right) ^{m-k}\dbinom{m}{k}f\left( x+1+k\right)
-\sum_{k=0}^{m}\left( -1\right) ^{m-k}\dbinom{m}{k}f\left( x+k\right) \\
& =\sum_{k=1}^{m+1}\underbrace{\left( -1\right) ^{m-\left( k-1\right) }%
}_{=\left( -1\right) ^{\left( m+1\right) -k}}\dbinom{m}{k-1}f\left(
\underbrace{x+1+\left( k-1\right) }_{=x+k}\right) -\sum_{k=0}%
^{m}\underbrace{\left( -1\right) ^{m-k}}_{=-\left( -1\right) ^{\left(
m+1\right) -k}}\dbinom{m}{k}f\left( x+k\right) \\
& \ \ \ \ \ \ \ \ \ \ \left( \text{hier haben wir das }k\text{ in der ersten
Summe durch }k-1\text{ substituiert}\right) \\
& =\sum_{k=1}^{m+1}\left( -1\right) ^{\left( m+1\right) -k}\dbinom
{m}{k-1}f\left( x+k\right) -\sum_{k=0}^{m}\left( -\left( -1\right)
^{\left( m+1\right) -k}\right) \dbinom{m}{k}f\left( x+k\right) \\
& =\sum_{k=1}^{m+1}\left( -1\right) ^{\left( m+1\right) -k}\dbinom
{m}{k-1}f\left( x+k\right) +\sum_{k=0}^{m}\left( -1\right) ^{\left(
m+1\right) -k}\dbinom{m}{k}f\left( x+k\right) .
\end{align*}
Die zwei Summen auf der rechten Seite sehen so aus, als sollten wir sie
zusammenfassen. Dies wird aber erst einmal durch die verschiedenen
Summationsintervalle behindert: Die erste Summe geht von $1$ bis $m+1$,
w\"{a}hrend die zweite von $0$ bis $m$ geht. Doch dies ist kein echtes
Hindernis, lassen sich doch beide Summen auf einfachste Weise zu Summen von
$0$ bis $m+1$ ausdehnen. F\"{u}r die erste Summe geschieht dies, indem wir
ihre Untergrenze von $1$ auf $0$ reduzieren und den neu dazugekommenen
$k=0$-Summanden wieder subtrahieren:%
\begin{align*}
& \sum_{k=1}^{m+1}\left( -1\right) ^{\left( m+1\right) -k}\dbinom{m}%
{k-1}f\left( x+k\right) \\
& =\sum_{k=0}^{m+1}\left( -1\right) ^{\left( m+1\right) -k}\dbinom
{m}{k-1}f\left( x+k\right) -\left( -1\right) ^{\left( m+1\right)
-0}\underbrace{\dbinom{m}{0-1}}_{\substack{=0\\\text{(laut (\ref{eq.binom.def}%
),}\\\text{denn }0-1\notin\mathbb{N}\text{)}}}f\left( x+0\right) \\
& =\sum_{k=0}^{m+1}\left( -1\right) ^{\left( m+1\right) -k}\dbinom
{m}{k-1}f\left( x+k\right) -\underbrace{\left( -1\right) ^{\left(
m+1\right) -0}0f\left( x+0\right) }_{=0}\\
& =\sum_{k=0}^{m+1}\left( -1\right) ^{\left( m+1\right) -k}\dbinom
{m}{k-1}f\left( x+k\right) .
\end{align*}
F\"{u}r die zweite Summe erh\"{o}hen wir die Obergrenze von $m$ auf $m+1$ und
subtrahieren den neuen Term wieder:%
\begin{align*}
& \sum_{k=0}^{m}\left( -1\right) ^{\left( m+1\right) -k}\dbinom{m}%
{k}f\left( x+k\right) \\
& =\sum_{k=0}^{m+1}\left( -1\right) ^{\left( m+1\right) -k}\dbinom{m}%
{k}f\left( x+k\right) \\
& \ \ \ \ \ \ \ \ \ \ -\left( -1\right) ^{\left( m+1\right) -\left(
m+1\right) }\underbrace{\dbinom{m}{m+1}}_{\substack{=0\\\text{(nach
(\ref{eq.binom.0rechts}),}\\\text{angewandt auf }n=m\text{ und }k=m+1\text{)}%
}}f\left( x+m+1\right) \\
& =\sum_{k=0}^{m+1}\left( -1\right) ^{\left( m+1\right) -k}\dbinom{m}%
{k}f\left( x+k\right) -\underbrace{\left( -1\right) ^{\left( m+1\right)
-\left( m+1\right) }0f\left( x+m+1\right) }_{=0}\\
& =\sum_{k=0}^{m+1}\left( -1\right) ^{\left( m+1\right) -k}\dbinom{m}%
{k}f\left( x+k\right) .
\end{align*}
Unsere obige Formel f\"{u}r $\left( \Delta^{m+1}f\right) \left( x\right) $
wird nun zu%
\begin{align*}
& \left( \Delta^{m+1}f\right) \left( x\right) \\
& =\underbrace{\sum_{k=1}^{m+1}\left( -1\right) ^{\left( m+1\right)
-k}\dbinom{m}{k-1}f\left( x+k\right) }_{=\sum_{k=0}^{m+1}\left( -1\right)
^{\left( m+1\right) -k}\dbinom{m}{k-1}f\left( x+k\right) }%
+\underbrace{\sum_{k=0}^{m}\left( -1\right) ^{\left( m+1\right) -k}%
\dbinom{m}{k}f\left( x+k\right) }_{=\sum_{k=0}^{m+1}\left( -1\right)
^{\left( m+1\right) -k}\dbinom{m}{k}f\left( x+k\right) }\\
& =\sum_{k=0}^{m+1}\left( -1\right) ^{\left( m+1\right) -k}\dbinom
{m}{k-1}f\left( x+k\right) +\sum_{k=0}^{m+1}\left( -1\right) ^{\left(
m+1\right) -k}\dbinom{m}{k}f\left( x+k\right) \\
& =\sum_{k=0}^{m+1}\left( -1\right) ^{\left( m+1\right) -k}\left(
\dbinom{m}{k-1}+\dbinom{m}{k}\right) f\left( x+k\right) \\
& \ \ \ \ \ \ \ \ \ \ \left( \text{hier haben wir die zwei Summen endlich
zusammengefasst}\right) .
\end{align*}
Vergleichen wir dies mit%
\begin{align*}
& \sum_{k=0}^{m+1}\left( -1\right) ^{\left( m+1\right) -k}%
\underbrace{\dbinom{m+1}{k}}_{\substack{=\dbinom{m}{k-1}+\dbinom{m}%
{k}\\\text{(nach (\ref{eq.binom.rec}),}\\\text{angewandt auf }n=m+1\text{)}%
}}f\left( x+k\right) \\
& =\sum_{k=0}^{m+1}\left( -1\right) ^{\left( m+1\right) -k}\left(
\dbinom{m}{k-1}+\dbinom{m}{k}\right) f\left( x+k\right) ,
\end{align*}
so erhalten wir%
\[
\left( \Delta^{m+1}f\right) \left( x\right) =\sum_{k=0}^{m+1}\left(
-1\right) ^{\left( m+1\right) -k}\dbinom{m+1}{k}f\left( x+k\right) .
\]
Wir haben also gezeigt, dass $\left( \Delta^{m+1}f\right) \left( x\right)
=\sum_{k=0}^{m+1}\left( -1\right) ^{\left( m+1\right) -k}\dbinom{m+1}%
{k}f\left( x+k\right) $ f\"{u}r alle $x\in\mathbb{A}$ gilt. Mit anderen
Worten: Aussage 3 gilt f\"{u}r $n=m+1$. Damit ist der Induktionsschritt
fertig, und Aussage 3 ist bewiesen.]
Mit dem Beweis von Aussage 3 ist Aufgabe \ref{aufg.findiff-prot} \textbf{(b)} gel\"{o}st.
\bigskip
\textbf{(c)} Seien $a,b,c\in\mathbb{R}$ und $n\in\mathbb{N}$ mit $c,>=stealth',shorten >=1pt,auto,node distance=3cm, thick,main node/.style={circle,fill=blue!20,draw}%
%]
%\node[main node] (1) {1};
%\node[main node] (3) [below right of=1] {3};
%\node[main node] (4) [above right of=1] {4};
%\node[main node] (2) [above left of=1] {2};
%\node[main node] (6) [below left of=1] {6};
%\node[main node] (5) [below right of=4] {5};
%\node[main node] (7) [above right of=5] {7};
%\node[main node] (9) [below right of=5] {9};
%\node[main node] (8) [above right of=9] {8};
%\path[every node/.style={font=\sffamily\small}%
%] (1) edge (4) (2) edge [bend right] (6) (3) edge (1) (4) edge (3) (5) edge [loop left] (5) (6) edge [bend right] (2) (7) edge [bend right] (9) (8) edge [loop left] (8) (9) edge [bend right] (7);
%\end{tikzpicture}}}%
%BeginExpansion
\begin{tikzpicture}%
[->,>=stealth',shorten >=1pt,auto,node distance=3cm, thick,main node/.style={circle,fill=blue!20,draw}%
]
\node[main node] (1) {1};
\node[main node] (3) [below right of=1] {3};
\node[main node] (4) [above right of=1] {4};
\node[main node] (2) [above left of=1] {2};
\node[main node] (6) [below left of=1] {6};
\node[main node] (5) [below right of=4] {5};
\node[main node] (7) [above right of=5] {7};
\node[main node] (9) [below right of=5] {9};
\node[main node] (8) [above right of=9] {8};
\path[every node/.style={font=\sffamily\small}%
] (1) edge (4) (2) edge [bend right] (6) (3) edge (1) (4) edge (3) (5) edge [loop left] (5) (6) edge [bend right] (2) (7) edge [bend right] (9) (8) edge [loop left] (8) (9) edge [bend right] (7);
\end{tikzpicture}%
%EndExpansion
\ \ .
\]
Jeder Knoten $i$ dieses Graphen hat genau eine ausgehende Kante (n\"{a}mlich
die Kante $i\rightarrow\sigma\left( i\right) $) und genau eine einkommende
Kante (n\"{a}mlich die Kante $\sigma^{-1}\left( i\right) \rightarrow i$).
Hieraus folgt unschwer, dass jeder Knoten dieses Graphen auf genau einem
Zyklus liegt (n\"{a}mlich dem, den man erh\"{a}lt, wenn man von diesem Knoten
aus losgeht und immer den Pfeilen folgt), und dass diese Zyklen keinen Knoten
und keine Kante gemeinsam haben. Grob gesprochen sieht der Graph also immer
aus wie im obigen Beispiel (bis auf Anzahl der Zyklen, ihre L\"{a}ngen, und
welcher Knoten auf welchem Zyklus liegt).
Wie findet man nun die $\sigma$-Spur eines Elementes $i\in X$ anhand von
diesem Graphen? Man geht im Knoten $i$ los und folgt den Pfeilen, bis man zum
Knoten $i$ zur\"{u}ckgekommen ist. Die bei diesem Rundgang verlassenen Knoten
(angefangen mit $i$ selber) schreibt man nun in eine Liste (in der
Reihenfolge, in der sie verlassen wurden); diese Liste ist die $\sigma$-Spur
von $i$. Im obigen Beispiel sind die $\sigma$-Spuren die folgenden:%
\begin{align*}
\left( \sigma\text{-Spur von }1\right) & =\left( 1,4,3\right) ;\\
\left( \sigma\text{-Spur von }2\right) & =\left( 2,6\right) ;\\
\left( \sigma\text{-Spur von }3\right) & =\left( 3,1,4\right) ;\\
\left( \sigma\text{-Spur von }4\right) & =\left( 4,3,1\right) ;\\
\left( \sigma\text{-Spur von }5\right) & =\left( 5\right) ;\\
\left( \sigma\text{-Spur von }6\right) & =\left( 6,2\right) ;\\
\left( \sigma\text{-Spur von }7\right) & =\left( 7,9\right) ;\\
\left( \sigma\text{-Spur von }8\right) & =\left( 8\right) ;\\
\left( \sigma\text{-Spur von }9\right) & =\left( 9,7\right) .
\end{align*}
\end{example}
\begin{proof}
[Beweisskizze zu Proposition \ref{prop.perm.spur2}.]Dem Leser \"{u}berlassen
(falls n\"{o}tig, nehme man Beispiel \ref{bsp.perm.spur2a} zur Inspiration).
\end{proof}
Nun beschr\"{a}nken wir uns auf Permutationen der Mengen $\left[ n\right] $
f\"{u}r $n\in\mathbb{N}$ (statt von allgemeinen endlichen Mengen).
\begin{definition}
Sei $n\in\mathbb{N}$. Die \textit{Werteliste} einer Permutation $\sigma$ von
$\left[ n\right] $ ist definiert als das $n$-Tupel mit Eintr\"{a}gen
$\sigma\left( 1\right) ,\sigma\left( 2\right) ,\ldots,\sigma\left(
n\right) $ (in dieser Reihenfolge). Wir werden (einer traditionellen
Konvention folgend) dieses $n$-Tupel durch eckige statt runde Klammern
abschlie\ss en -- d.h. wir bezeichnen es mit $\left[ \sigma\left( 1\right)
,\sigma\left( 2\right) ,\ldots,\sigma\left( n\right) \right] $ statt mit
$\left( \sigma\left( 1\right) ,\sigma\left( 2\right) ,\ldots
,\sigma\left( n\right) \right) $.
\end{definition}
(In der englischsprachigen Literatur wird f\"{u}r die Werteliste einer
Permutation der Begriff \textquotedblleft one-line notation\textquotedblright\ verwendet.)
Es ist klar, dass die Werteliste einer Permutation von $\left[ n\right] $
immer ein $n$-Tupel ist, das jede der $n$ Zahlen $1,2,\ldots,n$ genau einmal
enth\"{a}lt. Umgekehrt gibt es f\"{u}r jedes solche $n$-Tupel genau eine
Permutation von $\left[ n\right] $, deren Werteliste dieses $n$-Tupel ist.
Eine andere Methode, eine Permutation von $\left[ n\right] $ als eine Art
Zahlenliste zu kodieren, ist die \textit{Zykelliste}, die wir bald
einf\"{u}hren werden. Zun\"{a}chst definieren wir den Datentyp, den diese
Zykelliste haben wird:
\begin{definition}
Sei $n\in\mathbb{N}$.
\begin{enumerate}
\item[\textbf{(a)}] Eine $n$\textit{-Blockliste} ist definiert als ein
$n$-Tupel von ganzen Zahlen, in dem je zwei aufeinanderfolgende Eintr\"{a}ge
entweder durch ein Komma oder durch einen vertikalen Balken ( $\mid$ )
voneinander getrennt sind. Beispielsweise sind $\left( 3,1\mid4\mid
1,2,1\right) $ und $\left( 5\mid1\mid2,3,4,1\right) $ zwei $6$-Blocklisten.
(Diesmal benutzen wir runde Klammern.)
\item[\textbf{(b)}] Die Balken zerteilen eine $n$-Blockliste in Segmente, die
wir \textit{Bl\"{o}cke} nennen; zum Beispiel hat die $6$-Blockliste $\left(
3,1\mid4\mid1,2,1\right) $ genau drei Bl\"{o}cke, n\"{a}mlich $\left(
3,1\right) $, $\left( 4\right) $ und $\left( 1,2,1\right) $.
\item[\textbf{(c)}] Eine $n$-Blockliste hei\ss t \textit{normal}, wenn sie die
folgenden Eigenschaften hat:
\begin{enumerate}
\item[1.] Ihre $n$ Eintr\"{a}ge sind genau die Zahlen $1,2,\ldots,n$ (in
irgendeiner Reihenfolge).
\item[2.] Jeder Block beginnt mit seinem kleinsten Element.
\item[3.] Das kleinste (und damit erste) Element eines jeden Blocks ist
gr\"{o}\ss er als das kleinste Element des n\"{a}chsten Blocks.
\end{enumerate}
Beispielsweise sind $\left( 2,4,5\mid1,6,3\right) $ und $\left(
2,6,3,5\mid1,4\right) $ und $\left( 1,4,2,6,5,3\right) $ und $\left(
6\mid5\mid4\mid3\mid2\mid1\right) $ vier normale $6$-Blocklisten. Die
$6$-Blockliste $\left( 6,2\mid4\mid3,5\mid1\right) $ ist nicht normal (da
Eigenschaft 2 verletzt ist), und die $6$-Blockliste $\left( 1,5,4,2\mid
3,6\right) $ auch nicht (da Eigenschaft 3 verletzt ist).
\end{enumerate}
\end{definition}
Nun definieren wir die \textit{Zykelliste} einer Permutation $\sigma$ von
$\left[ n\right] $:
\begin{definition}
\label{def.perm.Csig}Sei $n\in\mathbb{N}$. Sei $\sigma$ eine Permutation von
$\left[ n\right] $. Die \textit{Zykelliste} von $\sigma$ ist die normale
$n$-Blockliste $C\left( \sigma\right) $, die durch folgenden Algorithmus
konstruiert wird:
\begin{itemize}
\item[1.] Wir setzen $S=\left[ n\right] $.
\item[2.] Wir w\"{a}hlen das kleinste Element $x$ von $S$ (also $1$).
\item[3.] Der letzte Block von $C\left( \sigma\right) $ ist die $\sigma
$-Spur von $x$.
\item[4.] Jetzt entfernen wir die Elemente dieses Blocks aus $S$. (Damit wird
$S$ kleiner.)
\item[2'.] Wenn $S$ nichtleer ist, w\"{a}hlen wir wieder das kleinste Element
$x$ von $S$ (dies ist nicht mehr $1$).
\item[3'.] Der vorletzte Block von $C\left( \sigma\right) $ ist die $\sigma
$-Spur von $x$.
\item[4'.] Jetzt entfernen wir die Elemente dieses Blocks aus $S$. (Damit wird
$S$ noch kleiner.)
\item[2\textquotedblright.] Wenn $S$ nichtleer ist, w\"{a}hlen wir wieder das
kleinste Element $x$ von $S$.
\item[3\textquotedblright.] Der vorvorletzte Block von $C\left(
\sigma\right) $ ist die $\sigma$-Spur von $x$.
\item[4\textquotedblright.] Jetzt entfernen wir die Elemente dieses Blocks aus
$S$. (Damit wird $S$ noch kleiner.)
\item[5.] Man f\"{a}hrt (wie in Schritten 2\textquotedblright,
3\textquotedblright\ und 4\textquotedblright) so lange fort, bis $S$ leer ist.
\end{itemize}
\noindent Wir sch\"{o}pfen also die Menge $\left[ n\right] $ aus durch
$\sigma$-Spuren, und schreiben diese Spuren jeweils als Bl\"{o}cke in unsere
Blockliste $C\left( \sigma\right) $.
\end{definition}
\begin{example}
\label{bsp.perm.Csig1} \ \
\begin{enumerate}
\item[\textbf{(a)}] Sei $n=9$, und sei $\sigma$ die Permutation von $\left[
n\right] $, die in Beispiel \ref{bsp.perm.spur2a} definiert wurde. Die
Werteliste von $\sigma$ ist $\left[ 4,6,1,3,5,2,9,8,7\right] $. Wir wollen
$C\left( \sigma\right) $ berechnen. Daf\"{u}r folgen wir dem Algorithmus in
Definition \ref{def.perm.Csig}:
\begin{itemize}
\item[1.] Zun\"{a}chst setzen wir $S=\left[ n\right] $. Also ist jetzt
$S=\left[ n\right] =\left[ 9\right] =\left\{ 1,2,\ldots,9\right\} $.
\item[2.] Wir w\"{a}hlen das kleinste Element $x$ von $S$. Also ist jetzt
$x=1$.
\item[3.] Der letzte Block von $C\left( \sigma\right) $ ist die $\sigma
$-Spur von $x$, also das Tupel $\left( 1,4,3\right) $.
\item[4.] Jetzt entfernen wir die Elemente dieses Blocks aus $S$. Jetzt ist
also $S=\left\{ 2,5,6,7,8,9\right\} $.
\item[2'.] Da $S$ nichtleer ist, w\"{a}hlen wir wieder das kleinste Element
$x$ von $S$. Also ist jetzt $x=2$.
\item[3'.] Der vorletzte Block von $C\left( \sigma\right) $ ist die $\sigma
$-Spur von $x$, also das Tupel $\left( 2,6\right) $.
\item[4'.] Jetzt entfernen wir die Elemente dieses Blocks aus $S$. Jetzt ist
also $S=\left\{ 5,7,8,9\right\} $.
\item[2\textquotedblright.] Da $S$ nichtleer ist, w\"{a}hlen wir wieder das
kleinste Element $x$ von $S$. Also ist jetzt $x=5$.
\item[3\textquotedblright.] Der vorvorletzte Block von $C\left(
\sigma\right) $ ist die $\sigma$-Spur von $x$, also das Tupel $\left(
5\right) $.
\item[4\textquotedblright.] Jetzt entfernen wir die Elemente dieses Blocks aus
$S$. Jetzt ist also $S=\left\{ 7,8,9\right\} $.
\item[2\textquotedblright'.] Da $S$ nichtleer ist, w\"{a}hlen wir wieder das
kleinste Element $x$ von $S$. Also ist jetzt $x=7$.
\item[3\textquotedblright'.] Der vorvorvorletzte Block von $C\left(
\sigma\right) $ ist die $\sigma$-Spur von $x$, also das Tupel $\left(
7,9\right) $.
\item[4\textquotedblright'.] Jetzt entfernen wir die Elemente dieses Blocks
aus $S$. Jetzt ist also $S=\left\{ 8\right\} $.
\item[2\textquotedblright\textquotedblright.] Da $S$ nichtleer ist, w\"{a}hlen
wir wieder das kleinste Element $x$ von $S$. Also ist jetzt $x=8$.
\item[3\textquotedblright\textquotedblright.] Der vorvorvorvorletzte Block von
$C\left( \sigma\right) $ ist die $\sigma$-Spur von $x$, also das Tupel
$\left( 8\right) $.
\item[4\textquotedblright\textquotedblright.] Jetzt entfernen wir die Elemente
dieses Blocks aus $S$. Jetzt ist also $S=\varnothing$.
\item[5.] Jetzt ist $S$ leer, und wir sind damit fertig.
\end{itemize}
\noindent Somit ist%
\[
C\left( \sigma\right) =\left( 8\mid7,9\mid5\mid2,6\mid1,4,3\right) .
\]
\item[\textbf{(b)}] Sei $n=7$, und sei $\sigma$ die Permutation von $\left[
n\right] $, die in Beispiel \ref{bsp.perm.spur1a} definiert wurde. Die
Werteliste von $\sigma$ ist $\left[ 2,6,3,7,5,4,1\right] $. Die Zykelliste
von $\sigma$ ist%
\[
C\left( \sigma\right) =\left( 5\mid3\mid1,2,6,4,7\right) .
\]
\item[\textbf{(c)}] Sei $n\in\mathbb{N}$, und sei $\operatorname*{id}%
\nolimits_{n}$ die Permutation $\operatorname*{id}:\left[ n\right]
\rightarrow\left[ n\right] $ von $\left[ n\right] $. Die Werteliste von
$\operatorname*{id}\nolimits_{n}$ ist $\left[ 1,2,\ldots,n\right] $. Die
Zykelliste von $\operatorname*{id}\nolimits_{n}$ ist%
\[
C\left( \operatorname*{id}\nolimits_{n}\right) =\left( n\mid n-1\mid
\cdots\mid1\right) .
\]
\item[\textbf{(d)}] Sei $n$ eine positive ganze Zahl, und sei $\zeta$ die
zyklische Permutation von $\left[ n\right] $, die $1,2,\ldots,n-1,n$ auf
$2,3,\ldots,n,1$ (in dieser Reihenfolge) abbildet. Die Werteliste von $\zeta$
ist $\left[ 2,3,\ldots,n,1\right] $. Die Zykelliste von $\zeta$ ist%
\[
C\left( \zeta\right) =\left( 1,2,\ldots,n\right) .
\]
\item[\textbf{(e)}] Sei $n\in\mathbb{N}$, und sei $k\in\left[ n-1\right] $.
Sei $\sigma$ die Permutation von $\left[ n\right] $, die die zwei Zahlen $k$
und $k+1$ vertauscht und alle anderen Elemente von $\left[ n\right] $
unver\"{a}ndert l\"{a}\ss t. Die Werteliste von $\sigma$ ist $\left[
1,2,\ldots,k-1,k+1,k,k+2,\ldots,n\right] $ (also die Liste $\left[
1,2,\ldots,n\right] $ nach Vertauschung der Eintr\"{a}ge $k$ und $k+1$). Die
Zykelliste von $\sigma$ ist%
\[
\left( n\mid n-1\mid\cdots\mid k+2\mid k,k+1\mid k-1\mid k-2\mid\cdots
\mid1\right) .
\]
\end{enumerate}
\end{example}
Folgendes wurde in Definition \ref{def.perm.Csig} ohne Beweis impliziert:
\begin{proposition}
\label{prop.perm.Csig-wd}Sei $n\in\mathbb{N}$, und sei $\sigma$ eine
Permutation von $\left[ n\right] $. Dann ist $C\left( \sigma\right) $
tats\"{a}chlich eine normale $n$-Blockliste.
\end{proposition}
\begin{proof}
[Beweisskizze.]Folgt unschwer aus Proposition \ref{prop.perm.spur1} und
Proposition \ref{prop.perm.spur2}.
\end{proof}
Es ist klar, dass jede Permutation $\sigma$ von $\left[ n\right] $ eindeutig
durch ihre Werteliste bestimmt ist. Das gleiche gilt f\"{u}r die Zykelliste:
\begin{proposition}
\label{prop.perm.Csig-uni}Sei $n\in\mathbb{N}$. Dann ist jede Permutation
$\sigma$ von $\left[ n\right] $ eindeutig durch ihre Zykelliste $C\left(
\sigma\right) $ bestimmt.
\end{proposition}
\begin{proof}
[Beweisskizze.]Sei $\sigma$ eine Permutation von $\left[ n\right] $. Sei
$i\in\left[ n\right] $. Dann muss die Zahl $i$ irgendwo in der Zykelliste
$C\left( \sigma\right) $ vorkommen (denn $C\left( \sigma\right) $ ist eine
normale $n$-Blockliste). Laut Konstruktion von $C\left( \sigma\right) $ ist
dann klar, wo $\sigma\left( i\right) $ in $C\left( \sigma\right) $ vorkommt:
\begin{itemize}
\item Steht die Zahl $i$ in $C\left( \sigma\right) $ am Ende eines Blocks,
dann steht $\sigma\left( i\right) $ am Anfang dieses Blocks.
\item Steht die Zahl $i$ in $C\left( \sigma\right) $ nicht am Ende eines
Blocks, dann steht $\sigma\left( i\right) $ gleich rechts von $i$ in
$C\left( \sigma\right) $.
\end{itemize}
Somit k\"{o}nnen wir $\sigma\left( i\right) $ aus der Zykelliste $C\left(
\sigma\right) $ ablesen. Daher k\"{o}nnen wir die gesamte Permutation
$\sigma$ aus ihrer Zykelliste $C\left( \sigma\right) $ rekonstruieren (denn
wenn wir die Werte $\sigma\left( i\right) $ f\"{u}r alle $i\in\left[
n\right] $ kennen, dann kennen wir ganz $\sigma$). Proposition
\ref{prop.perm.Csig-uni} ist damit bewiesen.
\end{proof}
\begin{proposition}
\label{prop.perm.Csig-conv}Sei $n\in\mathbb{N}$. Sei $D$ eine normale
$n$-Blockliste. Dann gibt es genau eine Permutation $\sigma$ von $\left[
n\right] $, deren Zykelliste $D$ ist.
\end{proposition}
\begin{proof}
[Beweisskizze.]Im Beweis von Proposition \ref{prop.perm.Csig-uni} haben wir
gesehen, wie wir eine Permutation $\sigma$ aus ihrer Zykelliste $C\left(
\sigma\right) $ ablesen k\"{o}nnen. Wenden wir die gleiche Methode auf $D$
statt $C\left( \sigma\right) $ an, dann finden wir eine Permutation $\sigma$
von $\left[ n\right] $, deren Zykelliste $D$ ist.
\end{proof}
Wir k\"{o}nnen jetzt die fundamentale Bijektion definieren:
\begin{definition}
\label{def.perm.sighat}Sei $n\in\mathbb{N}$. Sei $\sigma$ eine Permutation von
$\left[ n\right] $. Wenn wir in der Zykelliste $C\left( \sigma\right) $
von $\sigma$ alle Balken durch Kommas ersetzen, erhalten wir ein $n$-Tupel
$C^{\prime}\left( \sigma\right) $ von ganzen Zahlen, welches jede der $n$
Zahlen $1,2,\ldots,n$ genau einmal enth\"{a}lt. Wir ersetzen die runden
Klammern um dieses $n$-Tupel $C^{\prime}\left( \sigma\right) $ durch eckige
Klammern, und definieren $\widehat{\sigma}$ als diejenige Permutation von
$\left[ n\right] $, deren Werteliste dieses $n$-Tupel $C^{\prime}\left(
\sigma\right) $ ist.
\end{definition}
\begin{example}
Sei $n=9$, und sei $\sigma$ die Permutation von $\left[ n\right] $, die in
Beispiel \ref{bsp.perm.spur2a} definiert wurde. Laut Beispiel
\ref{bsp.perm.Csig1} ist $C\left( \sigma\right) =\left( 8\mid7,9\mid
5\mid2,6\mid1,4,3\right) $. Das $n$-Tupel $C^{\prime}\left( \sigma\right) $
in Definition \ref{def.perm.sighat} ist also%
\[
C^{\prime}\left( \sigma\right) =\left[ 8,7,9,5,2,6,1,4,3\right] .
\]
Also ist $\widehat{\sigma}$ die Permutation von $\left[ 9\right] $, deren
Werteliste $\left[ 8,7,9,5,2,6,1,4,3\right] $ ist.
\end{example}
\begin{theorem}
\label{thm.perm.sighat}Sei $n\in\mathbb{N}$. Die Abbildung%
\begin{align*}
\Phi:\left\{ \text{Permutationen von }\left[ n\right] \right\} &
\rightarrow\left\{ \text{Permutationen von }\left[ n\right] \right\} ,\\
\sigma & \mapsto\widehat{\sigma}%
\end{align*}
(also die Abbildung, die jede Permutation $\sigma$ von $\left[ n\right] $ in
$\widehat{\sigma}$ \"{u}berf\"{u}hrt) ist bijektiv.
\end{theorem}
\begin{proof}
[Beweisskizze.]Wir zeigen erst einmal, dass $\Phi$ injektiv ist. Dazu
m\"{u}ssen wir erkl\"{a}ren, wie wir eine Permutation $\sigma$ aus ihrem Bild
$\Phi\left( \sigma\right) =\widehat{\sigma}$ rekonstruieren k\"{o}nnen.
Dazu f\"{u}hren wir folgende Notation ein: Ist $u=\left( u_{1},u_{2}%
,\ldots,u_{n}\right) $ eine Liste von $n$ verschiedenen ganzen Zahlen, dann
bezeichnen wir einen Eintrag $u_{i}$ dieser Liste als \textit{Negativrekord}
von $u$, wenn er kleiner ist als alle vorherigen Eintr\"{a}ge (d.h., wenn er
$u_{i}