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

Aus Wikiversity
Zur Navigation springen Zur Suche springen



Übungsaufgaben

Aufgabe

Venn diagram gr la ru.svg

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


Aufgabe

Zeige

für .

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

Aufgabe

Zeige mit Hilfe von Lemma 2.16, dass die Summen

für abwechselnd positiv und negativ sind.


Aufgabe

Aus der lineare Algebra ist die Formel

für Untervektorräume 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 die entsprechende Formel

wobei ?


Aufgabe

Es sei eine Menge und es sei

eine Abbildung. Zeige, dass genau dann einen Fixpunkt besitzt, wenn der Durchschnitt des Graphen von mit der Diagonalen nicht leer ist.


Aufgabe

Bestimme die Fixpunkte der Abbildung


Aufgabe

Es sei ein Polynom vom Grad , . Zeige, dass maximal Fixpunkte besitzt.


Aufgabe

Es sei eine stetige Funktion und es gebe mit

und

Zeige, dass einen Fixpunkt besitzt.


Aufgabe *

Wir betrachten die durch die Wertetabelle

gegebene Abbildung von in sich selbst.

  1. Erstelle eine Wertetabelle für .
  2. Erstelle eine Wertetabelle für .
  3. Begründe, dass sämtliche iterierten Hintereinanderschaltungen bijektiv sind.
  4. Bestimme für jedes das minimale mit der Eigenschaft, dass

    ist.

  5. Bestimme das minimale mit der Eigenschaft, dass

    für alle ist.


Aufgabe

Berechne für die Permutation mit

die Potenzen und und gebe die Zyklendarstellung für diese drei Permutationen an.


Aufgabe

Permutation8.png

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

Snijden kruisen evenwijdig.png


Es sei diejenige Drehung am Würfel um die Achse durch die Eckpunkte und , die den Eckpunkt auf schickt, und es sei die Halbdrehung um die vertikale Achse (also die Gerade, die durch den Mittelpunkt der Seitenfläche und den Mittelpunkt der Seitenfläche läuft).

a) Man gebe eine Wertetabelle für die Permutationen auf der Eckpunktmenge , die durch und bewirkt werden.

b) Bestimme die Drehachse von und von sowie die Ordnung dieser Drehungen.

c) Man gebe die Zykeldarstellung der von bewirkten Permutation auf der Eckpunktmenge an. Was ist ?

d) Man betrachte die Permutation , die auf der Eckpunktmenge durch die Wertetabelle

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


Aufgabe *

Erstelle eine Liste von sämtlichen Permutationen auf der Menge und bestimme, welche von ihnen fixpunktfrei sind.


Aufgabe *

Berechne die Anzahl der fixpunktfreien Permutationen auf einer -elementigen Menge für 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 -elementigen Mengen mit zumindest Fixpunkten.


Aufgabe

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


Aufgabe

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

() besitzen.


Aufgabe

Es sei und , , fixiert. Wir interessieren uns für die Anzahl der -elementigen Teilmengen von , bei denen der Abstand zwischen zwei benachbarten Elementen aus der Teilmenge maximal gleich ist. Bestimme diese Anzahl für

  1. beliebig, .
  2. beliebig, .
  3. , beliebig.
  4. , 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 reinpasst?
  2. Was ist die maximale Seitenlänge eines gleichseitigen Dreieckes, das in einen Kreis mit Radius reinpasst?
  3. Was ist die maximale Seitenlänge eines gleichseitigen Dreieckes, das in ein Quadrat mit Seitenlänge reinpasst?


Aufgabe (5 (1+4) Punkte)

Diversity and Unity.jpg

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 -elementigen Menge, die genau Fixpunkte besitzen.


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

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

  1. Es sei fixiert. Bestimme den Grenzwert des beschriebenen Quotienten, wenn gegen unendlich geht.
  2. Es sei fixiert. Bestimme den Grenzwert des beschriebenen Quotienten, wenn gegen unendlich geht.
  3. Es sei eine reelle Zahl , , fixiert. Bestimme den Grenzwert des beschriebenen Quotienten, wenn ist und gegen unendlich geht.


<< | Kurs:Diskrete Mathematik (Osnabrück 2020) | >>

PDF-Version dieses Arbeitsblattes

Zur Vorlesung (PDF)