Kurs:Diskrete Mathematik (Osnabrück 2020)/Arbeitsblatt 3

Übungsaufgaben

Aufgabe

Es sei ${}LA$ die Menge der Großbuchstaben des lateinischen Alphabets, ${}GA$ die Menge der Großbuchstaben des griechischen Alphabets und ${}RA$ die Menge der Großbuchstaben des russischen Alphabets. Überprüfe die Siebformel anhand dieses Beispiels.

Aufgabe

Zeige

${}\sum _{k=0}^{n}(-1)^{k}{\binom {n}{k}}=0\,$

für ${}n\geq 1$.

Betrachte den Fall ${}n$ ungerade zuerst. Eine andere Beweismöglichkeit besprechen wir in Aufgabe 5.19.

Aufgabe

Zeige mit Hilfe von Lemma 2.16, dass die Summen

$\sum _{k=0}^{s}(-1)^{k}{\binom {n}{k}}$

für ${}s=0,1,2,\ldots ,n-1$ abwechselnd positiv und negativ sind.

Aufgabe

Aus der lineare Algebra ist die Formel

${}\operatorname {dim} _{}\left(U_{1}+U_{2}\right)=\operatorname {dim} _{}\left(U_{1}\right)+\operatorname {dim} _{}\left(U_{2}\right)-\operatorname {dim} _{}\left(U_{1}\cap U_{2}\right)\,$

für Untervektorräume ${}U_{1},U_{2}\subseteq V$ bekannt, siehe Satz 9.7 (Lineare Algebra (Osnabrück 2017-2018)), die an die Siebformel für zwei Mengen erinnert. Gilt für Untervektorräume ${}U_{1},U_{2},\ldots ,U_{n}\subseteq V$ die entsprechende Formel

${}\dim _{}{\left(U_{1}+U_{2}+\cdots +U_{n}\right)}=\sum _{k=1}^{n}(-1)^{k+1}{\left(\sum _{J\subseteq \{1,\ldots ,n\},\,{\#\left(J\right)}=k}\dim _{}{\left(U_{J}\right)}\right)}\,,$

wobei ${}U_{J}=\bigcap _{j\in J}U_{j}$?

Aufgabe

Es sei ${}M$ eine Menge und es sei

$F\colon M\longrightarrow M$

eine Abbildung. Zeige, dass ${}F$ genau dann einen Fixpunkt besitzt, wenn der Durchschnitt des Graphen von ${}F$ mit der Diagonalen ${}\triangle ={\left\{(x,x)\in M\times M\mid x\in M\right\}}$ nicht leer ist.

Aufgabe

Bestimme die Fixpunkte der Abbildung

$f\colon \mathbb {R} \longrightarrow \mathbb {R} ,\,x\longmapsto x^{2}.$

Aufgabe

Es sei ${}P\in \mathbb {R} [X]$ ein Polynom vom Grad ${}d\geq 1$, ${}P\neq X$. Zeige, dass ${}P$ maximal ${}d$ Fixpunkte besitzt.

Aufgabe

Es sei ${}f\colon \mathbb {R} \rightarrow \mathbb {R}$ eine stetige Funktion und es gebe ${}x,y\in \mathbb {R}$ mit

${}f(x)\leq x\,$

und

${}f(y)\geq y\,.$

Zeige, dass ${}f$ einen Fixpunkt besitzt.

Aufgabe *

Wir betrachten die durch die Wertetabelle

${}x$	${}1$	${}2$	${}3$	${}4$	${}5$	${}6$	${}7$	${}8$
${}F(x)$	${}3$	${}5$	${}1$	${}7$	${}8$	${}2$	${}6$	${}4$

gegebene Abbildung ${}F$ von

${}M=\{1,2,\ldots ,8\}\,$

in sich selbst.

1. Erstelle eine Wertetabelle für ${}F^{2}=F\circ F$.
2. Erstelle eine Wertetabelle für ${}F^{3}=F\circ F\circ F$.
3. Begründe, dass sämtliche iterierten Hintereinanderschaltungen ${}F^{n}$ bijektiv sind.
4. Bestimme für jedes ${}x\in M$ das minimale ${}n\in \mathbb {N} _{+}$ mit der Eigenschaft, dass

   ${}F^{n}(x)=x\,$

   ist.

5. Bestimme das minimale ${}n\in \mathbb {N} _{+}$ mit der Eigenschaft, dass

   ${}F^{n}(x)=x\,$

   für alle ${}x\in M$ ist.

Aufgabe

Berechne für die Permutation ${}\sigma$ mit

${}P$	${}1$	${}2$	${}3$	${}4$	${}5$	${}6$	${}7$	${}8$	${}9$	${}10$
${}\sigma (P)$	${}7$	${}10$	${}3$	${}9$	${}5$	${}2$	${}4$	${}1$	${}8$	${}6$

die Potenzen ${}\sigma ^{2}$ und ${}\sigma ^{3}$ und gebe die Zyklendarstellung für diese drei Permutationen an.

Kommentar:

Für jedes ${}P$ berechnet man das Bild von ${}P$ unter ${}\sigma ^{2}$ durch

$P\mapsto \sigma (P)\mapsto \sigma (\sigma (P)).$

Also z.B. ${}\sigma ^{2}(1)=4$, da ${}1\mapsto 7\mapsto 4.$ Auf diese Weise erhält man die Wertetabelle für ${}\sigma ^{2}$, und ähnlich für ${}\sigma ^{3}$.

Um die Zyklendarstellung für ${}\sigma$ zu erhalten, muss man alle Zyklen von ${}\sigma$ finden. Sei ${}P$ beliebig. Der Zykel von ${}\sigma$, der ${}P$ enthält, wird durch Bestimmen des minimalen ${}n\in \mathbb {N} _{+}$ mit

$P\mapsto \sigma (P)\mapsto \sigma ^{2}(P)\mapsto \cdots \mapsto \sigma ^{n}(P)=P$

gefunden. In diesem Fall ist

$Z=\langle P,\sigma (P),\dots ,\sigma ^{n-1}(P)\rangle$

ein Zykel von ${}\sigma$. Die Bestimmung von ${}n$ und damit von ${}Z$ kann leicht mit der Wertetabelle von ${}\sigma$ erfolgen. Sei nun ${}Q\not \in Z$. Ähnlich wie zuvor kann man einen Zykel ${}Z'$ von ${}\sigma$ finden, der ${}Q$ enthält. Wenn man dieses Verfahren fortsetzt, erhält man alle Zyklen von ${}\sigma$ in endlich vielen Schritten.

Die Zyklendarstellungen für ${}\sigma ^{2}$ und ${}\sigma ^{3}$ kann man wie oben aus ihren Wertetabellen ableiten. Man kann diese Darstellungen aber auch direkt aus der Zyklendarstellung von ${}\sigma$ erhalten. Zum Beispiel ist

$Z=\langle 1,7,4,9,8\rangle$

ein Zykel von ${}\sigma$. Dann sieht man leicht, dass

${\hat {Z}}=\langle 1,4,8,7,9\rangle$

ein Zykel von ${}\sigma ^{2}$.

Diskussion:

Wie kommt man auf ${}{\hat {Z}}=\langle 1,4,8,7,9\rangle$? Ich dachte, dass die Zyklen für alle sigmas gleich sein müssen. Wenn ich doch z.B. 1 verfolge, bildet sich 1 wieder auf 7 ab, egal wie „tief“ in Sigmas ich bin.

Die Zyklen hängen von den ${}\sigma$ ab, und ${}\sigma ^{2}\neq \sigma$, es ist die Hintereinanderschaltung. ${}\sigma$ anwenden und dann nochmal anwenden. Deshalb

${}\sigma ^{2}(1)=\sigma (\sigma (1))=\sigma (7)=4\,.$

Danke!!!

 

Aufgabe

Skizziere ein Pfeildiagramm, das die nebenstehende Permutation überschneidungsfrei darstellt.

Aufgabe

Zeige, dass man jede endliche Permutation durch ein überschneidungsfreies Pfeildiagramm darstellen kann.

Aufgabe *

Betrachte den Würfel

Es sei ${}\alpha$ diejenige Drehung am Würfel um die Achse durch die Eckpunkte ${}A$ und ${}G$, die den Eckpunkt ${}B$ auf ${}D$ schickt, und es sei ${}\beta$ die Halbdrehung um die vertikale Achse (also die Gerade, die durch den Mittelpunkt der Seitenfläche ${}A,B,C,D$ und den Mittelpunkt der Seitenfläche ${}E,F,G,H$ läuft).

a) Man gebe eine Wertetabelle für die Permutationen auf der Eckpunktmenge ${}\{A,B,C,D,E,F,G,H\}$, die durch ${}\alpha ,\beta ,\alpha \beta$ und ${}\beta \alpha$ bewirkt werden.

b) Bestimme die Drehachse von ${}\alpha \beta$ und von ${}\beta \alpha$ sowie die Ordnung dieser Drehungen.

c) Man gebe die Zykeldarstellung der von ${}\alpha ^{2}$ bewirkten Permutation auf der Eckpunktmenge an. Was ist ${}\alpha ^{1001}$?

d) Man betrachte die Permutation ${}\sigma$, die auf der Eckpunktmenge durch die Wertetabelle

${}x$	${}A$	${}B$	${}C$	${}D$	${}E$	${}F$	${}G$	${}H$
${}\sigma (x)$	${}B$	${}C$	${}D$	${}A$	${}G$	${}H$	${}E$	${}F$

gegeben ist. Gibt es eine Drehung des Würfels, die diese Permutation bewirkt? Berechne das Signum von ${}\sigma$.

Aufgabe *

Erstelle eine Liste von sämtlichen Permutationen auf der Menge ${}\{A,B,C,D\}$ und bestimme, welche von ihnen fixpunktfrei sind.

Aufgabe *

Berechne die Anzahl der fixpunktfreien Permutationen auf einer ${}n$-elementigen Menge für ${}n\leq 5$ mit Hilfe von Lemma 3.7 (bzw. die Wahrscheinlichkeiten, dass eine zufällige Permutation fixpunktfrei ist) und vergleiche mit den direkten Abzählungen.

Aufgabe

Erstelle eine Formel für die Anzahl der Permutationen auf einer ${}n$-elementigen Mengen mit zumindest ${}r$ Fixpunkten.

Aufgabe

Erstelle eine Formel dafür, dass eine Permutation auf einer ${}n$-elementigen Menge genau einen Fixpunkt besitzt.

Kommentar:

Man betrachtet eine Permutation ${}\varphi$ auf ${}M=\{1,\dots ,n\}$, die einen Fixpunkt ${}i$ besitzt. Da ${}\varphi (i)=i$, bildet ${}\varphi$ die Menge ${}M\setminus \{i\}$ auf sich selbst ab. Also ist die Einschränkung ${}\varphi '$ von ${}\varphi$ auf ${}M\setminus \{i\}$ eine Permutation. Falls ${}i$ der einzige Fixpunkt von ${}\varphi$ ist, dann ist ${}\varphi '$ fixpunktfrei auf ${}M\setminus \{i\}$. Es ist daher natürlich, die Menge ${}B_{i}$ aller Permutationen auf ${}M$ mit dem einzigen Fixpunkt ${}i$ zu betrachten. (Dies ist anders als im Beweis zu Lemma 3.7, wo die ${}A_{i}$ diejenigen Permutationen sind, wo ${}i$ Fixpunkt ist, aber es auch noch weitere Fixpunkte geben kann.) Aus der obigen Beobachtung überlegt man sich, dass es eine Bijektion zwischen ${}B_{i}$ und der Menge ${}C_{i}$ aller fixpunktfreien Permutationen auf ${}M\setminus \{i\}$ gibt. Eine Formel für die Anzahl von ${}C_{i}$ ergibt sich aus Lemma 3.7. Man muss jetzt nur noch beachten, dass die Mengen ${}B_{i}$ paarweise disjunkt sind und ihre Vereinigung die Menge aller Permutationen auf ${}M$ mit genau einem Fixpunkt bildet. Somit ist

${}{\#\left(B_{i}\right)}={\#\left(C_{i}\right)}=(n-1)!\sum _{k=0}^{n-1}{\frac {(-1)^{k}}{k!}}\,$

und die Anzahl aller Permutationen mit genau eniem Fixpunkt ist

${}\sum _{i=1}^{n}{\#\left(B_{i}\right)}=n!\sum _{k=0}^{n-1}{\frac {(-1)^{k}}{k!}}\,.$

 

Aufgabe

Bestimme für die Permutationen auf einer ${}5$-elementigen Menge, wie viele davon genau ${}r$ Fixpunkte

(${}r=0,1,2,3,4,5$) besitzen.

Aufgabe

Es sei ${}M={\{1,\ldots ,n\}}$ und ${}r,k$, ${}1\leq r,k\leq n$, fixiert. Wir interessieren uns für die Anzahl der ${}k$-elementigen Teilmengen von ${}M$, bei denen der Abstand zwischen zwei benachbarten Elementen aus der Teilmenge maximal gleich ${}r$ ist. Bestimme diese Anzahl für

1. ${}n,k$ beliebig, ${}r=n$.
2. ${}n,k$ beliebig, ${}r=1$.
3. ${}n=3$, ${}k,r$ beliebig.
4. ${}n=4$, ${}k,r$ beliebig.

Aufgaben zum Abgeben

Aufgabe (7 (1+1+5) Punkte)

1. Was ist die maximale Seitenlänge eines Quadrats, das in einen Kreis mit Radius ${}1$ reinpasst?
2. Was ist die maximale Seitenlänge eines gleichseitigen Dreieckes, das in einen Kreis mit Radius ${}1$ reinpasst?
3. Was ist die maximale Seitenlänge eines gleichseitigen Dreieckes, das in ein Quadrat mit Seitenlänge ${}1$ reinpasst?

Aufgabe (5 (1+4) Punkte)

Gabi Hochster und Heinz Ngolo wollen „Händchen halten“ üben und verschiedene Varianten durchprobieren. Jedenfalls soll die rechte Hand von Gabi und die linke Hand von Heinz sich vorderseitig berühren und die Finger der einen Hand sollen in den Fingerzwischenräumen der anderen Hand liegen, der Platz jenseits von Daumen und kleinem Finger gilt als Fingerzwischenraum. Dabei wird die anatomische Reihenfolge der Finger beibehalten.

1. Wie viele Möglichkeiten gibt es, wenn in jedem Fingerzwischenraum höchstens ein Finger zu liegen kommt?
2. Wie viele Möglichkeiten gibt es, wenn in jedem Fingerzwischenraum höchstens zwei Finger zu liegen kommt?

Aufgabe (2 Punkte)

Erstelle eine Formel für die Anzahl der Permutationen auf einer ${}n$-elementigen Menge, die genau ${}r$ Fixpunkte besitzen.

Aufgabe (7 (1+2+4) Punkte)

Es sei ${}L$ eine ${}\ell$-elementige Menge und ${}M$ eine ${}m$-elementige Menge. Wir interessieren uns für den Quotienten aus der Anzahl der injektiven Abbildungen von ${}L$ nach ${}M$ dividiert durch die Anzahl aller Abbildungen von ${}L$ nach ${}M$, und was man über das Grenzwertverhalten aussagen kann.

1. Es sei ${}m$ fixiert. Bestimme den Grenzwert des beschriebenen Quotienten, wenn ${}\ell$ gegen unendlich geht.
2. Es sei ${}\ell$ fixiert. Bestimme den Grenzwert des beschriebenen Quotienten, wenn ${}m$ gegen unendlich geht.
3. Es sei eine reelle Zahl ${}\alpha$, ${}0<\alpha \leq 1$, fixiert. Bestimme den Grenzwert des beschriebenen Quotienten, wenn ${}\ell :=\left\lfloor \alpha m\right\rfloor$ ist und ${}m$ gegen unendlich geht.