Kurs:Diskrete Mathematik (Osnabrück 2020)/Arbeitsblatt 13
- Übungsaufgaben
Es seien und mit . Zeige, dass die Anzahl der Abbildungen
bei denen das Urbild zu aus genau Elementen besteht, gleich dem Multinomialkoeffizienten
ist.
Es seien und mit . Zeige, dass die Anzahl der -Tupel
in denen die Zahl genau -mal vorkommt, gleich
ist.
Im Fressnapf von Vorli liegen heute drei Würste, vier Knochen, sieben Trockenbällchen und zwei Kaustangen. In wie vielen Reihenfolgen kann Vorli das auffressen?
Kommentar:
Insgesamt gibt es Sachen zum Fressen. Eine Fressreihenfolge dieser Sachen kann man auffassen als eine Abbildung
wobei die Fresssachen so oft getroffen werden, wie sie da sind. Somit gibt es
In einem Studium werden Leistungsnachweise verlangt, und zwar Seminarscheine, Klausuren, mündliche Prüfungen und eine Hausarbeit, die in beliebiger Reihenfolge erbracht werden können. Wie viele Reihenfolgen gibt es, um diese Leistungsnachweise zu erbringen?
Auf wie viele Arten kann man aus dem Wort „Eisenbeis“ Wörter bilden?
Es seien endlich viele natürliche Zahlen fixiert. Zeige, dass die für
definierte Funktion
(die vorderen Blockanzahlen sind also fixiert und werden durch einen einzigen weiteren Block aufgefüllt) ein Polynom in ist. Welchen Grad besitzt es?
Es seien endlich viele natürliche Zahlen fixiert. Zeige, dass die für
definierte Funktion
(die vorderen Blockanzahlen sind also fixiert und werden durch Einserblöcke aufgefüllt) kein Polynom in ist.
Es sei ein kommutativer Halbring und seien Elemente und . Zeige
Es sei ein kommutativer Halbring und . Berechne explizit
- ,
- ,
- .
Zeige
für .
Es sei ein kommutativer Halbring und Elemente mit
Erstelle eine Formel für
die diese Nullteilereigenschaften berücksichtigt.
Kommentar:
Zunächst einmal kann man einfach solche Ringe angeben, zum Beispiel kann man den Restklassenring
betrachten, wobei das von diesen Elementen erzeugte Ideal im Polynomring über einem Körper bezeichnet. Wir schreiben für die Restklassen der Variablen. Da in der Restklassenbildung das Ideal zu wird, werden insbesondere die angegebene Produkte zu . Man kann aber auch Restklassenringe von angeben, wo solche Nullteilereigenschaften gelten. Beispielsweise kann man
und in die Elemente
und
nehmen (viel einfacher geht das wohl nicht, man muss ja auch sicherstellen, dass beispielsweise oder nicht sind).
Der Multinomialsatz liefert allgemein
Dabei sind allerdings die Produkte, deren Exponententupel oberhalb eines der drei Exponententupel zu den angegebenen Monomen ist, gleich und müssen nicht angegeben werden. Es kommen nur die Monome
vor (wobei bei die beiden letzten zusammenfallen). Die anderen Exponenten sind dann jeweils gleich . Somit ist (bei )
Die vorstehende Aufgabe wird durch die folgenden Begriffe und die anschließenden Aufgaben weiter vertieft. Ferner sind monomiale Ideale vergleichsweise einfache Ideale mit übersichtlichen Restklassenringen.
Es sei ein kommutativer Ring. Aufbauend auf dem Polynomring in einer Variablen kann man Polynomringe in mehreren Variablen definieren. Man setzt rekursiv
Dies ist äquivalent zur Menge aller Linearkombinationen von Monomen:
Es sei der Polynomring über dem kommutativen Ring und sei
eine Familie von Monomen, . Dann nennt man das von den Monomen erzeugte Ideal ein monomiales Ideal.
Es sei ein Körper und
ein monomiales Ideal. Zeige, dass ein Monom genau dann zu gehört, wenn es ein mit gibt.
Es sei ein Körper und
ein monomiales Ideal. Zeige, dass ein Polynom genau dann zu gehört, wenn sämtliche Monome, die in (mit einem Koeffizienten ) vorkommen, zu gehören.
Es sei ein Körper. Bestimme eine Basis und die Dimension des Restklassenringes
zum monomialen Ideal .
Bestimme die Anzahl der surjektiven Abbildungen von einer -elementigen Menge in eine zweielementige Menge mit Hilfe von Lemma 13.5, Satz 13.6, Satz 13.7 und direkt.
Bestimme die Anzahl der surjektiven Abbildungen von einer sechselementigen Menge in eine dreielementige Menge mit Hilfe von Lemma 13.5, Satz 13.6 und Satz 13.7.
Zu bezeichne die Anzahl der surjektiven Abbildungen einer -elementigen Menge in eine -elementige Menge. Zeige, dass die Rekursionsformel
gilt.
Es sei und . Bestimme die Anzahl der surjektiven Abbildungen von nach mit der zusätzlichen Eigenschaft, dass jedes Element aus höchstens zweimal getroffen wird.
Es sei und . Bestimme die Anzahl der surjektiven Abbildungen von nach mit der zusätzlichen Eigenschaft, dass jedes Element aus höchstens fünfmal getroffen wird.
Kommentar:
Hier ist es geschickt, die komplementären Möglichkeiten zu zählen, also die surjektiven Abbildungen, bei denen mindestens ein Element aus sechsfach getroffen wird. Da jedes Element aus zumindest einmal getroffen werden soll, kann jedes Element höchstens siebenmal getroffen werden. Von diesem Extremfall gibt es Möglichkeiten, man muss sich ja fragen, welches Element von welchen sieben Elementen getroffen wird und wohin die verbleibenden drei Elemente gehen.
Wir müssen also noch die Situation ja verstehen, dass mindestens ein Element sechsmal getroffen wird. In diesem Fall kann auch nur ein Element genau sechsmal getroffen werden, und ein Element muss zweifach getroffen werden. Die Anzahl der Möglichkeiten ergeben sich durch eine ähnliche Überlegung.
Wenn die Zahlen größer werden, so kann man die Möglichkeiten zählen, dass das Element -fach getroffen wird. Man muss dann aber die Möglichkeit beachten, dass gleichzeitig das Element -fach und das Element -fach getroffen wird und beides den Vorgaben widerspricht. Dann muss man die Siebformel verwenden, um Mehrfachzählungen zu vermeiden.
Es seien und endliche Mengen mit bzw. Elementen und sei
eine surjektive Abbildung. Wie viele Abbildungen
mit
gibt es?
Es seien und endliche Mengen mit bzw. Elementen und sei
eine Abbildung. Wie viele Abbildungen
mit
gibt es?
- Aufgaben zum Abgeben
Aufgabe (2 Punkte)
Auf wie viele Arten kann man aus dem Wort „Ouagadougou“ Wörter bilden?
Aufgabe (4 Punkte)
Es sei ein kommutativer Halbring und seien Elemente mit
Erstelle eine Formel für
die diese Nullteilereigenschaften berücksichtigt.
Aufgabe (4 Punkte)
Man gebe ein Beispiel für eine endliche Familie von Monomen
mit gewissen Exponententupeln derart an, dass es keinen Restklassenring und keine Realisierung gibt, bei der genau dann gilt, wenn zu dem von den Monomen erzeugten Ideal in gehört.
Aufgabe (3 Punkte)
Bestimme die Anzahl der surjektiven Abbildungen von einer siebenelementigen Menge in eine dreielementige Menge mit Hilfe von Lemma 13.5, Satz 13.6 und Satz 13.7.
Aufgabe (5 Punkte)
Es sei und . Bestimme die Anzahl der surjektiven Abbildungen von nach mit der zusätzlichen Eigenschaft, dass jedes Element aus höchstens viermal getroffen wird.
<< | Kurs:Diskrete Mathematik (Osnabrück 2020) | >> |
---|