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

Übungsaufgaben

In einem Studium werden $11$ Leistungsnachweise verlangt, und zwar $3$ Seminarscheine, $5$ Klausuren, $2$ 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?

Aufgabe

Auf wie viele Arten kann man aus den Buchstaben des Wortes „Eisenbeis“ Wörter bilden?

Aufgabe

Es seien endlich viele natürliche Zahlen $r_{1}, \dots, r_{k}$ fixiert. Zeige, dass die für

n \geq r_{1} + \dots + r_{k}

definierte Funktion

n ⟼ (\binom{n}{r_{1}, \dots, r_{k}, n - r_{1} - \dots - r_{k}})

(die vorderen Blockanzahlen sind also fixiert und werden durch einen einzigen weiteren Block aufgefüllt) ein Polynom in $n$ ist. Welchen Grad besitzt es?

Aufgabe

Es seien endlich viele natürliche Zahlen $r_{1}, \dots, r_{k}$ fixiert. Zeige, dass die für

n \geq r_{1} + \dots + r_{k}

definierte Funktion

n ⟼ (\binom{n}{r_{1}, \dots, r_{k}, 1, \dots, 1})

(die vorderen Blockanzahlen sind also fixiert und werden durch Einserblöcke aufgefüllt) kein Polynom in $n$ ist.

Aufgabe *

Es sei $R$ ein kommutativer Halbring und seien $x_{1}, \dots, x_{k} \in R$ Elemente und $n \in ℕ$ . Zeige

{(x_{1} + \dots + x_{k})}^{n} = \sum_{r_{1} + \dots + r_{k} = n} (\binom{n}{r_{1}, \dots, r_{k}}) x_{1}^{r_{1}} \dots x_{k}^{r_{k}} .

Aufgabe

Es sei $R$ ein kommutativer Halbring und $x, y, z \in R$ . Berechne explizit

$(x + y + z)^{2}$ ,
$(x + y + z)^{3}$ ,
$(x + y + z)^{4}$ .

Aufgabe

Zeige

k^{n} = \sum_{r_{1} + \dots + r_{k} = n} (\binom{n}{r_{1}, \dots, r_{k}})

für $k, n \in ℕ$ .

Aufgabe

Es sei $R$ ein kommutativer Halbring und $x, y, z \in R$ Elemente mit

x z = x y^{2} = y^{2} z^{2} = 0 .

Erstelle eine Formel für

(x + y + z)^{n},

die diese Nullteilereigenschaften berücksichtigt.

Kommentar:

Zunächst einmal kann man einfach solche Ringe angeben, zum Beispiel kann man den Restklassenring

K [X, Y, Z] / (X Z, X Y^{2}, Y^{2} Z^{2})

betrachten, wobei $(X Z, X Y^{2}, Y^{2} Z^{2})$ das von diesen Elementen erzeugte Ideal im Polynomring $K [X, Y, Z]$ über einem Körper $K$ bezeichnet. Wir schreiben $x, y, z$ für die Restklassen der Variablen. Da in der Restklassenbildung das Ideal zu $0$ wird, werden insbesondere die angegebene Produkte zu $0$ . Man kann aber auch Restklassenringe von $ℤ$ angeben, wo solche Nullteilereigenschaften gelten. Beispielsweise kann man

n = 2^{2} \cdot 3^{2} \cdot 5^{4} \cdot 7 \cdot 1 1^{2} \cdot 1 3^{2}

und in $ℤ / (n)$ die Elemente

x = 2^{2} \cdot 5^{3} \cdot 7 \cdot 1 1^{2} \cdot 1 3^{2},

y = 3 \cdot 5 \cdot 7 \cdot 11

und

z = 2^{2} \cdot 3^{2} \cdot 5 \cdot 13

nehmen (viel einfacher geht das wohl nicht, man muss ja auch sicherstellen, dass beispielsweise $x y$ oder $y z^{3}$ nicht $0$ sind).

Der Multinomialsatz liefert allgemein

{(x + y + z)}^{n} = \sum_{r_{1} + r_{2} + r_{3} = n} (\binom{n}{r_{1}, r_{2}, r_{3}}) x^{r_{1}} y^{r_{2}} z^{r_{3}} .

Dabei sind allerdings die Produkte, deren Exponententupel oberhalb eines der drei Exponententupel zu den angegebenen Monomen ist, gleich $0$ und müssen nicht angegeben werden. Es kommen nur die Monome

x^{r_{1}}, y^{r_{2}}, z^{r_{3}}, x^{r_{1}} y, y^{r_{2}} z, y z^{r_{3}}

vor (wobei bei $n = 2$ die beiden letzten zusammenfallen). Die anderen Exponenten sind dann jeweils gleich $0$ . Somit ist (bei $n \geq 3$ )

{(x + y + z)}^{n} = x^{n} + y^{n} + z^{n} + n x^{n - 1} y + n y^{n - 1} z + n y z^{n - 1} .

Diskutieren und Fragen

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 $R$ ein kommutativer Ring. Aufbauend auf dem Polynomring in einer Variablen kann man Polynomringe in mehreren Variablen definieren. Man setzt rekursiv

R [X_{1}, X_{2}] := (R [X_{1}]) [X_{2}], \dots, R [X_{1}, \dots, X_{n - 1}, X_{n}] := (R [X_{1}, \dots, X_{n - 1}]) [X_{n}] .

Dies ist äquivalent zur Menge aller Linearkombinationen von Monomen:

\sum_{(ν_{1}, \dots, ν_{n})} a_{(ν_{1}, \dots, ν_{n})} X_{1}^{ν_{1}} \dots X_{n}^{ν_{n}} .

Es sei $R [X_{1}, \dots, X_{k}]$ der Polynomring über dem kommutativen Ring $R$ und sei

X^{ν_{j}} = X_{1}^{ν_{j 1}} \dots X_{k}^{ν_{j k}}

eine Familie von Monomen, $j \in J$ . Dann nennt man das von den Monomen $X^{ν_{j}}$ erzeugte Ideal ein monomiales Ideal.

Aufgabe

Es sei $K$ ein Körper und

I = (X^{ν_{j}}, j \in J) \subseteq K [X_{1}, \dots, X_{n}]

ein monomiales Ideal. Zeige, dass ein Monom $X^{μ}$ genau dann zu $I$ gehört, wenn es ein $ν_{j}$ mit $μ \geq ν_{j}$ gibt.

Aufgabe

Es sei $K$ ein Körper und

I = (X^{ν_{j}}, j \in J) \subseteq K [X_{1}, \dots, X_{n}]

ein monomiales Ideal. Zeige, dass ein Polynom $P \in K [X_{1}, \dots, X_{n}]$ genau dann zu $I$ gehört, wenn sämtliche Monome, die in $P$ (mit einem Koeffizienten $\neq 0$ ) vorkommen, zu $I$ gehören.

Aufgabe

Es sei $K$ ein Körper. Bestimme eine Basis und die Dimension des Restklassenringes

K [X, Y, Z] / (X^{3}, Y^{4}, Z^{2}, X^{2} Y^{3}, X^{2} Z, Y^{3} Z, X Y Z)

zum monomialen Ideal $(X^{3}, Y^{4}, Z^{2}, X^{2} Y^{3}, X^{2} Z, Y^{3} Z, X Y Z)$ .

Aufgabe

Bestimme die Anzahl der surjektiven Abbildungen von einer $n$ -elementigen Menge in eine zweielementige Menge mit Hilfe von Lemma 13.5, Satz 13.6, Satz 13.7 und direkt.

Aufgabe

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.

Aufgabe *

Zu $n, k \in ℕ$ bezeichne $surj (n, k)$ die Anzahl der surjektiven Abbildungen einer $n$ -elementigen Menge in eine $k$ -elementige Menge. Zeige, dass die Rekursionsformel

surj (n + 1, k) = k \cdot surj (n, k) + k \cdot surj (n, k - 1)

gilt.

Aufgabe *

Es sei $M = {1, 2, 3, 4, 5, 6, 7}$ und $N = {a, b, c, d}$ . Bestimme die Anzahl der surjektiven Abbildungen von $M$ nach $N$ mit der zusätzlichen Eigenschaft, dass jedes Element aus $N$ höchstens zweimal getroffen wird.

Aufgabe

Es sei $M = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}$ und $N = {a, b, c, d}$ . Bestimme die Anzahl der surjektiven Abbildungen von $M$ nach $N$ mit der zusätzlichen Eigenschaft, dass jedes Element aus $N$ 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 $N$ sechsfach getroffen wird. Da jedes Element aus $N$ zumindest einmal getroffen werden soll, kann jedes Element höchstens siebenmal getroffen werden. Von diesem Extremfall gibt es $4 \cdot (\binom{10}{7}) \cdot 3!$ 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 $z \in N$ $a$ -fach getroffen wird. Man muss dann aber die Möglichkeit beachten, dass gleichzeitig das Element $z$ $a$ -fach und das Element $w$ $b$ -fach getroffen wird und beides den Vorgaben widerspricht. Dann muss man die Siebformel verwenden, um Mehrfachzählungen zu vermeiden.

Diskutieren und Fragen

Aufgabe *

Es seien $M$ und $N$ endliche Mengen mit $m$ bzw. $n$ Elementen und sei

f : M ⟶ N

eine surjektive Abbildung. Wie viele Abbildungen

s : N ⟶ M

mit

f \circ s = {Id}_{N}

gibt es?

Aufgabe *

Es seien $M$ und $N$ endliche Mengen mit $m$ bzw. $n$ Elementen und sei

f : M ⟶ N

eine Abbildung. Wie viele Abbildungen

s : N ⟶ M

mit

f \circ s = {Id}_{N}

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 $R$ ein kommutativer Halbring und seien $x, y, z, w \in R$ Elemente mit

x y z = x^{2} w = x z^{2} = y^{2} z w = w^{2} = 0 .

Erstelle eine Formel für

(x + y + z + w)^{n},

die diese Nullteilereigenschaften berücksichtigt.

Aufgabe (4 Punkte)

Man gebe ein Beispiel für eine endliche Familie von Monomen

X^{ν} = X_{1}^{ν_{1}} \dots X_{k}^{ν_{k}}

mit gewissen Exponententupeln $ν$ derart an, dass es keinen Restklassenring $ℤ / (n)$ und keine Realisierung $φ : X_{i} \mapsto a_{i} \in ℤ / (n)$ gibt (gemeint ist der Ringhomomorphismus $ℤ [X_{1}, \dots, X_{k}] \to ℤ / (n)$ , der durch $X_{i} \mapsto a_{i}$ festgelegt ist), bei der $φ (X^{μ}) = 0$ genau dann gilt, wenn $X^{μ}$ zu dem von den Monomen $X^{ν}$ erzeugten Ideal in $ℤ [X_{1}, \dots, X_{k}]$ 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 $M = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}$ und $N = {a, b, c, d, e}$ . Bestimme die Anzahl der surjektiven Abbildungen von $M$ nach $N$ mit der zusätzlichen Eigenschaft, dass jedes Element aus $N$ höchstens viermal getroffen wird.

Aufgabe (4 Punkte)

Es sei $k \in ℕ_{+}$ fixiert. Bestimme den Grenzwert der Folge

x_{n} = \frac{Anzahl der surjektiven Abbildungen von {1, \dots, n} nach {1, \dots, k}}{Anzahl der Abbildungen von {1, \dots, n} nach {1, \dots, k}} .

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

PDF-Version dieses Arbeitsblattes

Zur Vorlesung (PDF)