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

Übungsaufgaben

Aufgabe

Es seien ${}n,k\in \mathbb {N}$ und ${}r=(r_{1},\ldots ,r_{k})$ mit ${}n$. Zeige, dass die Anzahl der Abbildungen

${\{1,\ldots ,n\}}\longrightarrow \{1,\ldots ,k\},$

bei denen das Urbild zu ${}j\in {\{1,\ldots ,n\}}$ aus genau ${}r_{j}$ Elementen besteht, gleich dem Multinomialkoeffizienten

${}{\binom {n}{r}}={\frac {n!}{r_{1}!\cdots r_{k}!}}\,$

ist.

Aufgabe

Es seien ${}k,n\in \mathbb {N}$ und ${}r=(r_{1},\ldots ,r_{n})$ mit ${}\sum _{j=1}^{k}r_{j}=n$. Zeige, dass die Anzahl der ${}n$-Tupel

$(j_{1},\ldots ,j_{n})\in \{1,\ldots ,k\}^{n},$

in denen die Zahl ${}j$ genau ${}r_{j}$-mal vorkommt, gleich

${}{\binom {n}{r}}={\frac {n!}{r_{1}!\cdots r_{k}!}}\,$

ist.

Aufgabe

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 ${}16$ Sachen zum Fressen. Eine Fressreihenfolge dieser Sachen kann man auffassen als eine Abbildung

$\{1,2,\ldots ,16\}\longrightarrow \{W,K,T,S\},$

wobei die Fresssachen so oft getroffen werden, wie sie da sind. Somit gibt es

${}{\binom {16}{3,4,7,2}}={\frac {16\cdot 15\cdots 8}{3!4!2!}}=15\cdots 10\cdot 4\,.$

 

Aufgabe

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 dem Wort „Eisenbeis“ Wörter bilden?

Aufgabe

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

${}n\geq r_{1}+\cdots +r_{k}\,$

definierte Funktion

$n\longmapsto {\binom {n}{r_{1},\ldots ,r_{k},n-r_{1}-\cdots -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},\ldots ,r_{k}$ fixiert. Zeige, dass die für

${}n\geq r_{1}+\cdots +r_{k}\,$

definierte Funktion

$n\longmapsto {\binom {n}{r_{1},\ldots ,r_{k},1,\ldots ,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},\ldots ,x_{k}\in R$ Elemente und ${}n\in \mathbb {N}$. Zeige

${}{\left(x_{1}+\cdots +x_{k}\right)}^{n}=\sum _{r_{1}+\cdots +r_{k}=n}{\binom {n}{r_{1},\dotsc ,r_{k}}}x_{1}^{r_{1}}\cdots x_{k}^{r_{k}}\,.$

Aufgabe

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

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

Aufgabe

Zeige

${}k^{n}=\sum _{r_{1}+\cdots +r_{k}=n}{\binom {n}{r_{1},\dotsc ,r_{k}}}\,$

für ${}k,n\in \mathbb {N}$.

Aufgabe

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

${}xz=xy^{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]/(XZ,XY^{2},Y^{2}Z^{2})$

betrachten, wobei ${}(XZ,XY^{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 ${}\mathbb {Z}$ angeben, wo solche Nullteilereigenschaften gelten. Beispielsweise kann man

${}n=2^{2}\cdot 3^{2}\cdot 5^{4}\cdot 7\cdot 11^{2}\cdot 13^{2}\,$

und in ${}\mathbb {Z} /(n)$ die Elemente

${}x=2^{2}\cdot 5^{3}\cdot 7\cdot 11^{2}\cdot 13^{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 ${}xy$ oder ${}yz^{3}$ nicht ${}0$ sind).

Der Multinomialsatz liefert allgemein

${}{\left(x+y+z\right)}^{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,yz^{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$)

${}{\left(x+y+z\right)}^{n}=x^{n}+y^{n}+z^{n}+nx^{n-1}y+ny^{n-1}z+nyz^{n-1}\,.$

 

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}],\ldots ,R[X_{1},\ldots ,X_{n-1},X_{n}]:=(R[X_{1},\ldots ,X_{n-1}])[X_{n}].$

Dies ist äquivalent zur Menge aller Linearkombinationen von Monomen:

$\sum _{(\nu _{1},\ldots ,\nu _{n})}a_{(\nu _{1},\ldots ,\nu _{n})}X_{1}^{\nu _{1}}\cdots X_{n}^{\nu _{n}}.$

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

${}X^{\nu _{j}}=X_{1}^{\nu _{j1}}\cdots X_{k}^{\nu _{jk}}\,$

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

Aufgabe

Es sei ${}K$ ein Körper und

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

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

Aufgabe

Es sei ${}K$ ein Körper und

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

ein monomiales Ideal. Zeige, dass ein Polynom ${}P\in K[X_{1},\ldots ,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,XYZ)$

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

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 \mathbb {N}$ bezeichne ${}\operatorname {Surj} (n,k)$ die Anzahl der surjektiven Abbildungen einer ${}n$-elementigen Menge in eine ${}k$-elementige Menge. Zeige, dass die Rekursionsformel

${}\operatorname {Surj} (n+1,k)=k\cdot \operatorname {Surj} (n,k)+k\cdot \operatorname {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.

 

Aufgabe *

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

$f\colon M\longrightarrow N$

eine surjektive Abbildung. Wie viele Abbildungen

$s\colon N\longrightarrow M$

mit

${}f\circ s=\operatorname {Id} _{N}\,$

gibt es?

Aufgabe *

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

$f\colon M\longrightarrow N$

eine Abbildung. Wie viele Abbildungen

$s\colon N\longrightarrow M$

mit

${}f\circ s=\operatorname {Id} _{N}\,$

gibt es?

Aufgaben zum Abgeben

Straßenszene von Ouagadougou

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

${}xyz=x^{2}w=xz^{2}=y^{2}zw=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^{\nu }=X_{1}^{\nu _{1}}\cdots X_{k}^{\nu _{k}}\,$

mit gewissen Exponententupeln ${}\nu$ derart an, dass es keinen Restklassenring ${}\mathbb {Z} /(n)$ und keine Realisierung ${}\varphi :X_{i}\mapsto a_{i}\in \mathbb {Z} /(n)$ gibt, bei der ${}\varphi (X^{\mu })=0$ genau dann gilt, wenn ${}X^{\mu }$ zu dem von den Monomen ${}X^{\nu }$ erzeugten Ideal in ${}\mathbb {R} [X_{1},\ldots ,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)

Sei ${}k\in \mathbb {N} _{+}$ fixiert. Bestimme den Grenzwert der Folge

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