Lösung
Formuliere die folgenden Sätze.
- Der Satz über die Wohldefiniertheit der Anzahl.
- Das
allgemeine Distributivgesetz
für einen kommutativen Halbring.
- Der
Satz von Kirchhoff
über die Anzahl der Spannbäume.
Lösung
- Wenn
eine Menge ist und wenn
-
und
-
bijektive Abbildungen sind, so ist
-
![{\displaystyle {}n=k\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6f848bf8ea252d2be5ac98055a919684f3171e71)
- Es sei
ein kommutativer Halbring und es seien
Elemente aus
. Dann gilt das allgemeine Distributivgesetz
-
![{\displaystyle {}{\left(\sum _{i=1}^{r}a_{i}\right)}{\left(\sum _{k=1}^{s}b_{k}\right)}=\sum _{1\leq i\leq r,\,1\leq k\leq s}a_{i}b_{k}\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9b9e4eb89c5969a20b5e5f55d2059356339491c6)
- Es sei
ein
Multigraph
und sei
die
Laplace-Matrix
zu
. Es sei
die
Streichungsmatrix
von
bezüglich eines Knotenpunktes. Dann ist die Anzahl der
Spannbäume
von
gleich der
Determinante
von
.
Es sei
. Zeige, wie man
mit vier Multiplikationen berechnen kann.
Lösung
Sei
-
![{\displaystyle {}b:=a\cdot a=a^{2}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a102e5ef7b977cf5e46df4e87db7d25bff89bda3)
und
-
![{\displaystyle {}c:=b\cdot b=b^{2}=a^{4}\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d1810c6c3df7b500a04ba0f4413781defe974a86)
Dann ist
-
![{\displaystyle {}a^{10}=(c\cdot c)\cdot b\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ee47bfb4f5b232b30c927c496d7d294b966aae4b)
eine Berechnung mit vier Multiplikationen.
Gabi Hochster möchte sich die Fingernägel ihrer linken Hand
(ohne den Daumennagel)
lackieren, wobei die drei Farben
zur Verfügung stehen. Sie möchte nicht, dass zwei benachbarte Finger die gleiche Farbe bekommen. Wie viele Möglichkeiten gibt es?
Lösung
Sie beginnt mit dem Zeigefinger, dafür hat sie drei Möglichkeiten. Für den Mittelfinger hat sie zwei Möglichkeiten, da die Farbe des Zeigefingers ausgeschlossen ist. Für den Ringfinger hat sie wieder zwei Möglichkeiten, da die Farbe des Mittelfingers ausgeschlossen ist. Für die Farbe des kleinen Fingers hat sie wieder zwei Möglichkeiten, da die Farbe des Ringfingers ausgeschlossen ist. Insgesamt gibt es also
-
![{\displaystyle {}3\cdot 2\cdot 2\cdot 2=24\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bbee86f934614af751532fad25a104cb6d61c259)
Möglichkeiten.
Zeige, dass die
Binomialkoeffizienten
die rekursive Beziehung
-
![{\displaystyle {}{\binom {n+1}{k}}={\binom {n}{k}}+{\binom {n}{k-1}}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a535bf09663ace3351845455ddadb5857b6a6309)
erfüllen.
Lösung
Es ist
![{\displaystyle {}{\begin{aligned}{\binom {n}{k}}+{\binom {n}{k-1}}&={\frac {n!}{(n-k)!k!}}+{\frac {n!}{(n-(k-1))!(k-1)!}}\\&={\frac {n!}{(n-k)!k!}}+{\frac {n!}{(n+1-k)!(k-1)!}}\\&={\frac {(n+1-k)\cdot n!}{(n+1-k)!k!}}+{\frac {k\cdot n!}{(n+1-k)!k!}}\\&={\frac {(n+1-k+k)\cdot n!}{(n+1-k)!k!}}\\&={\frac {(n+1)!}{(n+1-k)!k!}}\\&={\binom {n+1}{k}}.\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/155e1c3cc9e8288b7ef4b0da235d59fe94ddd489)
Es sei
eine zweielementige Menge. Erstelle eine Verknüpfungstabelle für die Verknüpfung „Vereinigung“ auf der
Potenzmenge
.
Lösung
Die Menge sei
,
die Potenzmenge ist dann
-
![{\displaystyle {}{\mathfrak {P}}\,(M)=\{\emptyset ,\{a\},\{b\},\{a,b\}\}\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/367cb8fd20bbb08570f2c31f46e24f601b40885e)
Die Verknüpfungstabelle für die Vereinigung ist
![{\displaystyle {}\cup }](https://wikimedia.org/api/rest_v1/media/math/render/svg/d46107ba622b77761a5af33655223b668e8ba463) |
![{\displaystyle {}\emptyset }](https://wikimedia.org/api/rest_v1/media/math/render/svg/f24c7a68f9153122a17babe008235b76e18dfc4b) |
![{\displaystyle {}\{a\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/daba267d8c831ab4ecc108ff5361adfec8577ad7) |
![{\displaystyle {}\{b\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a7309353796c3a655d69bfbe1beab9ca18870eed) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Lösung Untergruppenkriterium/Aufgabe/Lösung
Zu
sei
-
![{\displaystyle {}[n]=\{0,1,2,\ldots ,n\}\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3a832b5b0d45fa6896df016e4b4a047b6e45bd59)
Zu jedem
und jedem
seien die Abbildungen
-
durch
-
![{\displaystyle {}D_{k}(j)={\begin{cases}j,{\text{ falls }}j<k,\\j+1{\text{ sonst}},\end{cases}}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a603195a49c5e1b57e2be979a88ecc1eef0e5fdd)
und die Abbildungen
-
durch
-
![{\displaystyle {}S_{k}(j)={\begin{cases}j,{\text{ falls }}j\leq k,\\j-1{\text{ sonst}},\end{cases}}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1638b3579de538a5f20b0ff2b801730117ee5eec)
definiert.
a) Erstelle eine Wertetabelle für
-
b) Erstelle eine Wertetabelle für
-
c) Beschreibe die durch die Wertetabelle
|
|
|
|
|
|
|
|
|
|
|
|
|
|
gegebene Abbildung
-
als eine Hintereinanderschaltung von geeigneten
und
.
Lösung
a)
|
|
|
|
|
|
|
|
|
|
|
|
b)
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
c) Wir behaupten
-
![{\displaystyle {}\varphi =D_{3}\circ D_{1}\circ S_{3}\circ S_{1}\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/753f61c6978234cc94e2d7a0e9bd89f6d785ffc2)
Die Komposition hat für die Elemente
jeweils den folgenden Effekt:
-
-
-
-
-
-
Das Gesamtergebnis stimmt also mit
überein.
Lösung
Wir beweisen die Aussage durch Induktion über das Maximum von
und
,
wobei wir ohne Einschränkung
wählen können. Wenn das Maximum
ist, so sind beide Zahlen
und somit nicht teilerfremd. Wenn das Maximum
ist, so ist
und somit ergeben
und
eine Darstellung der
. Es seien nun
teilerfremd,
und die Aussage sei für alle Zahlenpaare, deren Maxima kleiner als
sind, schon bewiesen. Dann ist
,
da bei
die beiden Zahlen nicht teilerfremd sind. Ebenso können wir
ausschließen. Wir betrachten das Zahlenpaar
und wollen darauf die Induktionsvoraussetzung anwenden. Das Maximum dieses neuen Paares ist jedenfalls kleiner als
. Allerdings müssen wir, damit die Induktionsvoraussetzung wirklich angewendet werden kann, wissen, dass auch
und
teilerfemd sind.
Dazu führen wir einen Widerspruchsbeweis. Nehmen wir also an, dass
und
nicht teilerfremd sind. Dann gibt es eine natürliche Zahl
,
die sowohl
als auch
teilt. Dies bedeutet wiederum, dass es natürliche Zahlen
mit
und
gibt. Doch dann ist
-
![{\displaystyle {}b=(b-a)+a=nt+mt=(n+m)t\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e8f77d50f0be8f665a3e991ad07adc8e201e8638)
ebenfalls ein Vielfaches von
, im Widerspruch zur Teilerfremdheit von
und
.
Die Induktionsvoraussetzung ist also auf
und
anwendbar und somit gibt es ganze Zahlen
mit
-
![{\displaystyle {}ra+s(b-a)=1\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0081f4324c271c1a070e95666a1842c05aad5827)
Dann ist aber auch
-
![{\displaystyle {}(r-s)a+sb=ra+s(b-a)=1\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3cc1256de6bd6e69f9188526c732dc2f907b7ea7)
und wir haben eine Darstellung der
mit
und
gefunden.
Lösung /Aufgabe/Lösung
Es sei
die Menge der zweimal stetig differenzierbaren Funktionen von
nach
. Definiere auf
eine Relation durch
-
a) Zeige, dass dies eine
Äquivalenzrelation
ist.
b) Finde für jede Äquivalenzklasse dieser Äquivalenzrelation einen polynomialen Vertreter.
c) Zeige, dass diese Äquivalenzrelation mit der Addition von Funktionen verträglich ist.
d) Zeige, dass diese Äquivalenzrelation nicht mit der Multiplikation von Funktionen verträglich ist.
Lösung
a) Wir betrachten die Abbildung
-
Zwei Funktionen
und
stehen genau dann in dieser Relation zueinander, wenn ihre Bilder unter
übereinstimmen. Daher liegt eine Äquivalenzrelation vor
(und
beschreibt die Äquivalenzklassenbildung).
b) Das Polynom
-
wird unter
auf
abgebildet, so dass dieses Polynom diese Klasse repräsentiert.
c) Es sei
und
.
Es ist
zu zeigen. Dies folgt aber sofort aufgrund der Additivität der Ableitung.
d) Wir betrachten
und
und
. Offenbar ist
. Die relevanten Werte für
sind wegen
einfach
-
Für
ergibt sich
.
Daher ist
-
so dass
ist. Wir behaupten, dass
und
nicht äquivalent sind. Es ist
mit den Ableitungen
und daher ist
-
Für
hat man die Ableitungen
und daher ist
-
Lösung /Aufgabe/Lösung
Lösung /Aufgabe/Lösung
Beweise den Charakterisierungssatz für Bäume.
Lösung
Aus (1) folgt (2). Da
nach Voraussetzung zusammenhängend ist, gibt es zu
zumindest einen verbindenden Weg. Würde es zwei Wege geben, so könnte man daraus direkt einen Zyklus und dann auch einen Kreis konstruieren, was ausgeschlossen ist.
Aus (2) folgt (1). Die Zusammenhangseigenschaft ist klar. Würde es einen Kreis geben, so könnte man dies direkt als einen zweifachen Weg ohne Wiederholung zwischen zwei Punkten auffassen.
Aus (1) folgt (3). Wir führen Induktion über die Anzahl der Punkte von
. Bei einem einzigen Punkt gibt es keine Kante und die Gleichung stimmt. Es sei also
ein Baum mit
Punkten. Nach
Lemma 17.20 (Diskrete Mathematik (Osnabrück 2020))
besitzt
ein
Blatt
und nach
Lemma 17.21 (Diskrete Mathematik (Osnabrück 2020))
ist
ebenfalls ein Baum. Dabei wird ein Punkt und eine Kante herausgenommen. Nach Induktionsvoraussetzung gilt die Gleichung für den verkleinerten Baum, also gilt sie auch für
.
Von (3) nach (1). Wir führen wieder Induktion über die Knotenanzahl, bei einem Knoten ist alles klar. Aufgrund der Voraussetzung und
Lemma 15.16 (Diskrete Mathematik (Osnabrück 2020))
gilt
-
![{\displaystyle {}\sum _{v\in V}d(v)=2\cdot {\left({\#\left(V\right)}-1\right)}=2{\#\left(V\right)}-2\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0bf8eaecddd2fe41732ff345dec79a53825acad3)
Wegen der Zusammenhangseigenschaft sind die Grade zumindest
. Deshalb muss es
(zumindest
)
Punkte mit Grad
, also Blätter geben. Es sei
ein Blatt. Die Formel gilt dann auch für
. Nach Induktionsvoraussetzung ist
ein Baum, und daher ist nach
Lemma 17.21 (Diskrete Mathematik (Osnabrück 2020))
auch
ein Baum.
Lösung /Aufgabe/Lösung
Lösung /Aufgabe/Lösung
Lösung /Aufgabe/Lösung
Lösung /Aufgabe/Lösung
Lösung /Aufgabe/Lösung