Abbildung/Knöpfe und Löcher am Hemd/Aufgabe

Mathematiker haben, so ein weitverbreitetes Vorurteil, Schwierigkeiten, ihre Hemden korrekt zuzuknöpfen. Ein Hemd hat auf der einen Seite eine von oben nach unten geordnete Knopfreihe bestehend aus ${\displaystyle {}n}$ Knöpfen und auf der anderen Seite eine ebenso geordnete Lochreihe aus ${\displaystyle {}n}$ Löchern. Beide Reihen seien von oben nach unten mit ${\displaystyle {}1}$ bis ${\displaystyle {}n}$ durchnummeriert. Eine Zuknöpfung ${\displaystyle {}\sigma }$ ordnet jedem Knopf genau ein Loch zu, sie ist also eine Abbildung

${\displaystyle \sigma \colon {\{1,\ldots ,n\}}\longrightarrow {\{1,\ldots ,n\}},\,i\longmapsto \sigma (i),}$

wobei die identische Abbildung ${\displaystyle {}i\mapsto i}$ als korrekte (oder triviale) Zuknöpfung gilt. Der Zerstreutheitsindex ${\displaystyle {}Z(\sigma )}$ ist ein wichtiges numerisches Maß für die Zerstreutheit (oder Kreativität) einer Zuknöpfung ${\displaystyle {}\sigma }$. Er ist definiert über die Abbildung

${\displaystyle Z\colon A_{n}=\operatorname {Abb} \,{\left({\{1,\ldots ,n\}},{\{1,\ldots ,n\}}\right)}\longrightarrow \mathbb {N} ,\,\sigma \longmapsto Z(\sigma )=\sum _{i=1}^{n}\vert {i-\sigma (i)}\vert .}$

1. Zeige: Eine Zuknöpfung ${\displaystyle {}\sigma }$ ist genau dann korrekt, wenn ${\displaystyle {}Z(\sigma )=0}$ ist.
2. Kann eine Zuknöpfung den Zerstreutheitsindex ${\displaystyle {}1}$ haben? Wie sieht es bei bijektiven Zuknöpfungen aus?
3. Bestimme

   ${\displaystyle a_{n}=\max {\left\{Z(\sigma )\mid {\sigma \in A_{n}}\right\}}}$

   in Abhängigkeit von ${\displaystyle {}n\in \mathbb {N} }$.

4. Es sei ${\displaystyle {}B_{n}\subseteq A_{n}}$ die Menge aller bijektiven Zuknöpfungen. Bestimme

   ${\displaystyle b_{n}=\max {\left\{Z(\sigma )\mid {\sigma \in B_{n}}\right\}}}$

   für ${\displaystyle {}n=0,1,2,3,4,5}$.

5. Es sei ${\displaystyle {}C_{n}\subseteq A_{n}}$ die Menge aller konstanten Zuknöpfungen. Bestimme

   ${\displaystyle c_{n}=\max {\left\{Z(\sigma )\mid {\sigma \in C_{n}}\right\}}}$

   in Abhängigkeit von ${\displaystyle {}n\in \mathbb {N} }$.

6. Eine Zuknöpfung ${\displaystyle {}\sigma }$ heißt semikorrekt, wenn ${\displaystyle {}Z(\sigma )\leq n}$ ist. Klassifiziere alle semikorrekten Zuknöpfungen bei ${\displaystyle {}n\leq 3}$.