Kombinatorik

Warum wird den Schweizern der «Schieber» auf die Dauer nicht langweilig? Weil es

21\,452\,752\,266\,265\,320\,000

verschiedene Spiele dieser Art gibt!

Warum spielen jede Woche so viele Leute im deutschen Zahlenlotto «6 aus 49»? Weil sie nicht wissen, dass ihre Gewinnchance für sechs Richtige verschwindend klein ist, nämlich nur $1\div13'983'816$ !
Warum verwenden gewöhnliche Bankräuber für das Öffnen eines Safes Schweissbrenner? Weil sie zu viel Zeit bräuchten, sämtliche Kombinationen des Zahlenschlosses durchzuprobieren!

Mit diesen und ähnlichen Zählproblemen beschäftigt sich die Kombinatorik, ein Teilgebiet der Arithmetik. Sie untersucht, auf wie viele Arten bestimmte Objekte ausgewählt und wie diese Objekte angeordnet werden können. Wir wollen uns auf die Auswahl aus endlichen Mengen beschränken; Kombinatorik ist im Wesentlichen finite Mathematik. Die zwei wichtigsten Probleme für die Kombinatorik sind:

das Existenzproblem: Welche Möglichkeiten gibt es, Elemente einer endlichen Menge nach bestimmten Bedingungen auszuwählen oder anzuordnen?
das Aufzählungsproblem: Wie viele Möglichkeiten gibt es dafür insgesamt?

Dabei kann sich durchaus ergeben, dass unter den gestellten Bedingungen gar keine Lösung existiert. Bei praktischen Aufgaben stellt sich zudem oft die Frage, wie die Lösungen am besten klassifiziert werden können bzw. welche Lösung ein Optimum für bestimmte Zwecke darstellt.

Mit den folgenden fünf Aufgaben sollen zunächst die wesentlichen Aufgabentypen der Kombinatorik, die in der Schulmathematik ihren Platz gefunden haben, vorgestellt werden. Diese Aufgaben werden später auf ein gemeinsames Modell, das Urnenmodell, zurückgeführt.

Exercise 1: Arrangieren

Wie viele verschiedene Buchstabenfolgen kann man mit den Buchstaben

a) T, O, R

b) S, I, S, S, I

bilden, wenn jeweils alle Buchstaben zu verwenden sind?

Solution

a) An den ersten drei Positionen kann man aus $3$ Buchstaben wählen, bei der nächsten noch aus $2$ und danach setzt man noch den übrig gebliebenen Buchstaben; also kann dies auf $3\cdot2\cdot1 = 3! = 6$ Arten geschehen.

b) Hier ist es kniffliger, da man gleichartige Buchstaben hat. Man denke sich die gleichartigen nummeriert (z. B. $I_{1}$ , $I_{2}$ ). Jetzt berechnet man die Kombinationen, als hätte man lauter Individuen. Abschliessend muss durch die Anzahl Kombinationsmöglichkeiten aller nummerierten, gleichartigen dividiert werden, da sie sich ja eigentlich nicht unterscheiden lassen. Für SISSI gibt es also $\frac{5!}{2!\cdot3!} = 10$ Möglichkeiten.

Exercise 2: Wer kennt Toto?

Wie viele Prognosen können für die beiden ersten Fussballspiele eines Totozettels gegeben werden?

Solution

Das sind $3\cdot3 = 9$ .

Exercise 3: Öpfuchueche

Für eine kleine Apfelwähe lässt sich Frau Gschwind von ihrem Kaufmann, der die Sorten Gravensteiner und Delicious – gemischt in einer grossen Kiste – verkauft, vier beliebige Äpfel geben. Wie viele verschiedene Apfelwähen könnten so entstehen?

Solution

Das sind $5$ . Man stelle sich die vier Äpfel in einer Reihe ausgelegt vor. Nun kann man mit einer Trennwand die beiden Sorten aufteilen. Diese Trennwand kann an $5$ verschiedenen Stellen ( $\_$ ) positioniert werden: $\_\ \text{A}\ \_\ \text{A}\ \_\ \text{A}\ \_\ \text{A}\ \_$

Aus der Mannigfaltigkeit der kombinatorischen Aufgaben seien hier noch erwähnt:

In any calendar year how many Friday the thirteenths can there be? (Minimum: 1, Maximum: 3)
Wie viele «Gesichter» hat der Zauberwürfel (Rubik's Cube)? ( $43'252'003'274'489'856'000$ )
Auf wie viele Arten lässt sich ein Franken in Kleingeld ( $1\,\mathrm{Rp}$ , $2\,\mathrm{Rp}$ , $5\,\mathrm{Rp}$ , $10\,\mathrm{Rp}$ , $20\,\mathrm{Rp}$ , $50\,\mathrm{Rp}$ ) umwechseln? ( $4562$ )

Aus den bisherigen Aufgaben mag der Eindruck entstehen, dass es sich bei der Kombinatorik um eine «gehobene Unterhaltungsmathematik» handelt. Tatsächlich gab es erst um 1900 ein erstes ernst zu nehmendes Lehrbuch der Kombinatorik, das Lösungsmethoden für sämtliche klassischen Aufgaben bereitstellte. Seit etwa 1950 ist die Kombinatorik zu einer anerkannten und selbstständigen Disziplin innerhalb der Mathematik geworden. In anderen mathematischen Disziplinen (Wahrscheinlichkeitsrechnung, Zahlentheorie, Graphentheorie etc.), aber auch in anderen Wissenschaften (Linguistik, Biologie, Physik, Nachrichtentechnik etc.) tauchten immer mehr Probleme auf, die nur mit kombinatorischen Mitteln zu lösen waren. Insbesondere erlaubten seit 1950 die Computer ein experimentelles Arbeiten, das ganz neue Lösungswege eröffnete; ein schönes Beispiel dazu ist der Beweis des Vierfarbensatzes.

Vier-Farben-Satz

1852 wurde folgendes Problem formuliert:

Jede auf einem Stück Papier gezeichnete Landkarte lässt sich mit nur vier Farben so färben, dass niemals zwei aneinandergrenzende Länder dieselbe Farbe erhalten.

Erst 1976 konnte nach jahrelanger ständiger Verbesserung der Methoden mit 1200 Stunden Rechenzeit an drei Computern der Satz bewiesen werden.

Summen- und Produktregel

Will man die Anzahl der Schüler einer Schule ermitteln, so könnte man an einem bestimmten Morgen jeden Schüler, der durch die Eingangstüre kommt, einzeln zählen. Einfacher wäre es, die einzelnen Klassenbestände zu ermitteln und zu addieren. Die Idee ist folgende: Um die Anzahl der Elemente einer Menge $G$ zu ermitteln, ist es oft einfacher, diese Menge zuerst in elementfremde Teilmengen $A_1, A_2, A_3, \dots, A_r$ zu zerlegen und dann die entsprechenden Zahlen zu addieren.

Theorem 1

\text{card}(G) = \text{card}(A_1)+\text{card}(A_2)+\dots+\text{card}(A_r)

wobei $A_i\cap A_j = \emptyset, i,j=1,2,\dots,r$ .

Verallgemeinerung: Kann ein Vorgang auf $n_1$ verschiedene Arten ausgeführt werden, danach ein weiterer auf $n_2$ verschiedene Arten, dem folgend ein dritter auf $n_3$ verschiedene Arten und so weiter, dann gibt es $n_1\cdot n_2\cdot n_3\cdot\dots\cdot n_k$ verschiedene Möglichkeiten, den so beschriebenen Gesamtvorgang auszuführen.

Theorem 2

\text{Anzahl} = n_1\cdot n_2\cdot n_3\cdot\dots\cdot n_k

Zur Visualisierung kann ein Baumdiagramm gezeichnet werden.

Exercise 4: Vierstellige Zahlen

Wie viele vierstellige Zahlen mit lauter ungeraden Ziffern gibt es?

Solution

Pro Stelle hat man $5$ ungerade Ziffern zur Verfügung, also gibt es $5^{4}=625$ Möglichkeiten.

Exercise 5: Wörter

Wie viele «Wörter» der Form KVKVK (K: Konsonant, V: Vokal) gibt es, wenn ein Buchstabe

a) mehrfach

b) nur einmal verwendet werden darf?

Solution

Es gibt $21$ Konsonanten und $5$ Vokale.

a) $21\cdot 5\cdot21\cdot 5\cdot21 = 21^{3}\cdot5^{2} = 231'525$

b) $21\cdot5\cdot20\cdot4\cdot19 = 159'600$

Exercise 6: Nummernschild

In der Schweiz enthalten die Nummernschilder der Autos in der Regel zwei Buchstaben (Kantonszeichen), denen sechs Ziffern folgen, wobei die erste nicht Null ist. Wie viele Schilder gibt es?

Solution

Es gibt theoretisch $26\cdot9\cdot10^{5} = 23'400'000$ verschiedene Schilder.

Permutationen

In einer obigen Aufgabe hat man gesehen, dass die Buchstaben T, O und R auf sechs verschiedene Arten TOR, TRO, ORT, OTR, RTO, ROT angeordnet (permutiert) werden können. Auf die Anzahl 6 schliesst man mit der Produktregel: Für den ersten Buchstaben stehen drei Möglichkeiten (T, O oder R) zur Verfügung, für den zweiten bleiben noch zwei Möglichkeiten, für den dritten bleibt nur noch eine Möglichkeit. Insgesamt gibt es also

3\cdot2\cdot1 = 6

verschiedene Möglichkeiten der Anordnung. Allgemein gilt:

Theorem 3

Die Anzahl aller Permutationen von $n$ verschiedenen Elementen ist

P_n = n\cdot(n-1)\cdot(n-2)\cdot\dots\cdot3\cdot2\cdot1 \stackrel{\text{Def.}}{=:} n!

Note 1

$n!$ spricht man « $n$ Fakultät» aus.

Exercise 7: Fakultäten

Berechne bzw. vereinfache:

a) $\frac{10!}{3!}$

b) $\frac{3\cdot4!}{4\cdot3!}$

c) $n(n-1)!$

d) $\frac{(n+3)!}{n!}\div\frac{(n+1)!}{(n-1)!}$

Solution

a) $604'800$

b) $3$

c) $n\cdot(n-1)! = n!$

d) $\frac{(n+3)!}{n!}\div\frac{(n+1)!}{(n-1)!} = \frac{(n+3)!(n-1)!}{n!(n+1)!} = \frac{(n+3)(n+2)}{n}$

Exercise 8: Bücher

$3$ Physikbücher, $4$ Informatikbücher und $5$ Mathematikbücher sollen auf ein Regal gestellt werden. Auf wie viele Arten geht dies, wenn die Bücher des gleichen Fachgebiets nebeneinander stehen sollen und alle Bücher verschieden sind?

Solution

Die Fächer kann man paketweise auf $3!$ Arten anordnen. Innerhalb dieser Fächer sind dann insgesamt $3!\cdot4!\cdot5!$ Anordnungen möglich. Das ergibt ein Total von sagenhaften $103'680$ verschiedenen Anordnungen.

Exercise 9: In Reihe

a) Auf wie viele Arten können sich elf Personen in eine Reihe setzen?

b) Wie viele Möglichkeiten gibt es, wenn zwei Personen unbedingt nebeneinander sitzen wollen?

c) Löse a) und b) für die Sitzordnungen an einem runden Tisch.

Solution

a) $11!\approx40\,\mathrm{Mio.}$

b) Die beiden Personen können auf $2$ Arten nebeneinander sitzen. Nun kann dieses Pärchen sich zwischen und um die $9$ verbliebenen Personen setzen, die sich permutieren können: $2!\cdot10\cdot 9!=7\,257\,600$ .

c) $11!/11=10!=3\,628\,800$ und $10!/10\cdot2!=725\,760$

Gegeben seien $n$ Elemente, von denen genau $k$ untereinander gleich sind. Diese $k$ gleichen Elemente werden für einen Moment mit Indizes versehen, sodass man sie voneinander unterscheiden kann. Die Anzahl aller Permutationen ist dann $n!$ , wobei aber jeweils $k!$ Permutationen sich nur in den Stellungen der extra verschieden bezeichneten Elemente unterscheiden. Macht man die Indizierung rückgängig, so sind jeweils $k!$ Permutationen nicht mehr voneinander verschieden. Also ist in diesem Fall die Anzahl der Permutationen $\frac{n!}{k!}$ . Allgemein gilt:

Theorem 4

Die Anzahl der Permutationen von $n$ Elementen, unter denen ein Element $k_1$ -mal, ein zweites Element $k_2$ -mal, ... , ein $r$ -tes Element $k_r$ -mal vorkommt, ist

P_{n,k_1,\dots,k_r} = \frac{n!}{k_1!\cdot k_2!\cdot k_3!\cdot\dots\cdot k_r!}

Exercise 10: Mississippi

Auf wie viele Arten kann man die Buchstaben von

a) OTTO

b) MISSISSIPPI

c) deinen Namen für ein Anagramm permutieren?

Solution

a) $\frac{4!}{2!\cdot2!} = 6$

b) $\frac{11!}{(4!)^{2}\cdot2!} = 34'650$

c) Jorma $5!=120$

Exercise 11: Fahnen

Ein Signal kann durch sechs Fahnen, die untereinander hängen, gegeben werden. Wie viele verschiedene Signale kann man mit vier gleichen roten und zwei gleichen blauen Fahnen bilden?

Solution

$\frac{6!}{4!\cdot 2!} = 15$

Stichproben

Die ersten Aufgaben aus dem Einführungskapitel sollen auf das Urnenmodell übertragen werden: In einer Urne sind $n$ Lose, die irgendwie gekennzeichnet sind. Aus dieser Urne werden $k$ Lose gezogen: eine Stichprobe vom Umfang $k$ .

Diese Ziehung kann auf vier verschiedene Arten erfolgen:

A Geordnete Stichprobe mit Zurücklegen. Jedes Los wird einzeln gezogen und nach einer Notiz wieder zurückgelegt. Es ergibt sich eine natürliche Ordnung; jedes Los kann mehrmals gezogen werden.
B Geordnete Stichprobe ohne Zurücklegen. Wie in A, jedoch wird das gezogene Los jeweils nicht zurückgelegt.
C Ungeordnete Stichprobe (ohne Zurücklegen). Die $k$ Lose werden mit einem Griff gezogen, d. h. die natürliche Anordnung wie in A und B geht verloren.
D Ungeordnete Stichprobe (mit Wiederholung). Wie in A, jedoch verzichtet man auf die sich ergebende Ordnung. Wenn in einer Urne von jedem Los mindestens $k$ Exemplare vorhanden sind, kann man auch wie in C mit einem Griff $k$ Lose ziehen.

Geordnete Stichprobe mit Zurücklegen

Unmittelbar aus der Produktregel ergibt sich für die Anzahl der geordneten Stichproben mit Zurücklegen:

A_{n,k} = n\cdot n\cdot n\cdot\dots\cdot n = n^k

Bei der dualen Version werden nicht $k$ Lose aus einer Urne gezogen, sondern $k$ unterscheidbare Dinge auf $n$ unterscheidbare Urnen beliebig verteilt. Dazu gibt es $n\cdot n\cdot n\cdot\dots\cdot n=n^k$ Möglichkeiten.

Exercise 12: Werfen und Würfeln

Wie viele Ergebnisse sind möglich, wenn man

a) eine Münze

b) einen Würfel

fünfmal wirft?

Solution

a) $2^{5} = 32$

b) $6^{5} = 7776$

Exercise 13: Safe

Bei einem Safeschloss sind fünf Einstellungen einer Ziffer von 1 bis 9 möglich. Wie viel Zeit benötigt man, um alle Einstellungen auszuprobieren, wenn man für eine Einstellung durchschnittlich vier Sekunden braucht?

Solution

Man braucht $9^{5}\cdot4=236'196\,\mathrm{s}$ . Das sind ca. $65$ Stunden.

Geordnete Stichprobe ohne Zurücklegen

Auch in diesem Fall ergibt sich die Anzahl der geordneten Stichproben ohne Zurücklegen unmittelbar aus der Produktregel:

A_{n,k} = n\cdot(n-1)\cdot(n-2)\cdot\dots\cdot(n-k+1) = \frac{n!}{(n-k)!}

mit $k \leq n$ .

Bei der dualen Version werden $k$ unterscheidbare Dinge so auf $n$ unterscheidbare Urnen verteilt, dass in jeder Urne höchstens ein Ding zu liegen kommt ( $k\leq n$ ). Dazu gibt es $n\cdot(n-1)\cdot(n-2)\cdot\dots\cdot(n-k+1)$ Möglichkeiten. Statt «Urne» sagt man bei dieser Version besser «Platz». Die Permutationen von $n$ verschiedenen Elementen sind ein Spezialfall der geordneten Stichprobe ohne Zurücklegen ( $k=n$ ). Damit gibt es auch $n!$ verschiedene Möglichkeiten, $n$ voneinander verschiedene Dinge auf $n$ Plätze zu verteilen.

Exercise 14: Sprinter

Acht Sprinter kämpfen bei den Olympischen Spielen um die Gold-, Silber- und Bronzemedaille. Auf wie viele Arten kann die Siegerehrung erfolgen?

Solution

$8\cdot7\cdot6 = 336$

Exercise 15: 0!

Wie sollte $0!$ definiert werden?

Solution

Mit der Kombinatorik-Interpretation möchte man $0$ Elemente permutieren. Dies geht auf $1$ Art, nämlich nicht. Ferner gilt $(n-k)! = \frac{n!}{n\cdot(n-1)\cdot\dots\cdot(n-k+1)}$ , also im Falle $n=k$ :

0! = (n-n)! = \frac{n!}{n\cdot(n-1)\cdot\dots\cdot(n-n+1)} = \frac{n!}{n\cdot(n-1)\cdot\dots\cdot1} = \frac{n!}{n!} = 1.

Somit setzt man $0! := 1$ .

Ungeordnete Stichprobe ohne Zurücklegen

Für die Anzahl der ungeordneten Stichproben ohne Zurücklegen betrachte man noch einmal die Lösungen der Aufgaben aus dem Einführungskapitel.

Allgemein gilt: Jede der Stichproben vom Umfang $k$ , die man mit einem Griff zieht, kann man auf $k!$ Arten ordnen. Nach dieser aufoktroyierten Ordnung hat man gerade den Fall der geordneten Stichproben ohne Zurücklegen. Deshalb gibt es $k!$ -mal mehr geordnete als ungeordnete Stichproben. Die Anzahl der ungeordneten Stichproben ohne Zurücklegen beträgt demnach:

A_{n,k} = \frac{n!}{(n-k)!}\div k! = \frac{n!}{k!(n-k)!} \stackrel{\text{Def.}}{=:} \binom{n}{k}

wobei $k\leq n$ .

Exercise 16: Binomialkoeffizienten

Zeige durch Rechnung:

a) $\binom{n}{0} = \binom{n}{n}=1$

b) $\binom{n}{k} = \binom{n}{n-k}$

c) $\binom{n}{2} = \frac{n(n-1)}{2}$

Solution

a) $\binom{n}{0} = \frac{n!}{0!\cdot n!} = \frac{n!}{1\cdot n!} = 1$

b) $\binom{n}{k} = \frac{n!}{k!\cdot (n-k)!} = \frac{n!}{(n-k)!\cdot k!} = \frac{n!}{(n-k)!\cdot (n-(n-k))!} = \binom{n}{n-k}$

c) $\binom{n}{2} = \frac{n!}{2!\cdot(n-2)!} = \frac{n!}{2\cdot(n-2)!} = \frac{n(n-1)}{2}$

Exercise 17: Schülerdelegation

Aus zehn Schülern soll eine Delegation von vier Mitgliedern und innerhalb der Delegation ein Sprecher bestimmt werden. Auf wie viele Arten geht dies? Verallgemeinere auf $n$ Schüler und $k$ Delegationsmitglieder und leite so eine allgemeine Beziehung her.

Solution

Aus $n$ Schülern die geforderten $k$ Delegationsmitglieder auswählen kann man auf $\binom{n}{k}$ Arten. Aus den jeweils $k$ Delegierten gibt es $k$ mögliche Sprecher: $k\cdot\binom{n}{k}$ .

Exercise 18: Handshake

Wie viele Händedrücke gibt es, wenn sich $n$ Personen begrüssen und jeder jedem nur einmal die Hand gibt?

Solution

Es sind $\binom{n}{2}$ oder anders formuliert: Eine Person grüsst $(n-1)$ Leute. Da es $n$ Personen sind und egal ist, ob beispielsweise A B grüsst oder B A, gibt es $\frac{n(n-1)}{2}$ Begrüssungen.

Exercise 19: Jasskarten verteilen

Auf wie viele Arten kann man die 36 Jasskarten an

a) zwei

b) drei

c) vier

Spieler verteilen?

Solution

a) $\binom{36}{18}\cdot\binom{18}{18} \approx 9\cdot10^{9}$

b) $\binom{36}{12}\cdot\binom{24}{12} \approx 3.4\cdot10^{15}$

c) $\binom{36}{9}\cdot\binom{27}{9}\cdot\binom{18}{9} \approx 2.1\cdot10^{19}$

Ungeordnete Stichprobe mit Zurücklegen

Für den schwierigsten Fall der ungeordneten Stichproben mit Zurücklegen formulieren wir die Apfelkuchen-Aufgabe ein wenig um: Auf wie viele Arten kann man Äpfel aus der Menge $\{\text{Delicious, Gravensteiner}\}$ eine ungeordnete Stichprobe vom Umfang vier entnehmen?

Bezeichnet man mit $x_1\in\mathbb{N}_0$ die Anzahl $D$ und mit $x_2\in\mathbb{N}_0$ die Anzahl $G$ , so muss die Anzahl der Lösungen der Gleichung

x_1+x_2=4

ermittelt werden. Jede Lösung erhält man, wenn man in der Figur 1111 an geeigneter Stelle einen Trennstrich einsetzt. Zum Beispiel entspricht der Figur

111|1

die Lösung drei Delicious und ein Gravensteiner. Für die Setzung des Trennstriches gibt es fünf Möglichkeiten, da der Trennstrich sowohl am Anfang als auch am Ende der Figur gesetzt werden kann. Es gibt demnach $\binom{5}{1}=5$ Stichproben.

Bevor auf $m$ Sorten und $k$ Äpfel verallgemeinert wird, betrachten wir noch ein weiteres Beispiel mit $m=4$ und $k=10$ . Die zugehörige Gleichung lautet:

x_1+x_2+x_3+x_4=10

Aus der mit vertikalen Trennstrichen versehenen Figur

111|11||11111

kann man die spezielle Lösung $x_1 = 3, x_2 = 2, x_3 = 0$ und $x_4 = 5$ ablesen. In diesem Beispiel hat man drei Trennstriche anzubringen. Die vollständige Figur besteht dann aus zehn Einsen und drei Trennstrichen. Man hat aus 13 Plätzen 10 Plätze für die Einsen oder 3 Plätze für die Trennstriche auszuwählen, um alle gewünschten Stichproben zu erhalten. Dies geht auf $\binom{13}{10}=\binom{13}{3}=286$ Arten.

Im allgemeinen Fall sind $(m-1)$ Trennstriche anzubringen; die vollständige Figur besteht aus $k$ Einsen und $(m-1)$ Trennstrichen. Schliesslich sind aus $k+(m-1)$ Plätzen deren $k$ für die Einsen oder deren $(m-1)$ für die Trennstriche auszuwählen. Die Anzahl der ungeordneten Stichproben mit Zurücklegen beträgt also

A_{m,k} = \binom{m+k-1}{k} = \binom{m+k-1}{m-1}

Exercise 20

Wie viele Lösungen hat die Gleichung

x_1+x_2+x_3+\dots+x_{10} = 13\quad (x\in\mathbb{N}_0)?

Solution

$\binom{13+9}{9}=497'420$

Bei der dualen Version sind $k$ ununterscheidbare Dinge in $m$ Urnen zu legen. Bezeichnet man die Dinge mit Einsen, so müssen in der Figur

11111\dots111

$(m-1)$ Trennstriche als Markierungen für die Urnen gesetzt werden. Dazu gibt es, wie oben gezeigt,

\binom{m+k-1}{k} = \binom{m+k-1}{m-1}

Möglichkeiten.

Exercise 21: Parlamentssitze

Auf wie viele Arten können 60 Parlamentssitze auf drei Parteien verteilt werden?

Solution

$\binom{60+2}{2} = 1891$

Exercise 22: Kaninchen

Zehn ununterscheidbare Kaninchen sollen auf drei Käfige verteilt werden. Auf wie viele Arten geht dies, wenn

a) keine Einschränkungen vorgeschrieben sind

b) kein Käfig leer sein darf

c) kein Kaninchen allein und kein Käfig leer sein darf

Solution

a) $\binom{10+2}{2} = 66$

b) Man stecke in jeden Käfig ein Kaninchen und verteile die restlichen $7$ nach Belieben: $\binom{7+2}{2} = 36$ .

c) $\binom{4+2}{2} = 15$

Vermischte Aufgaben

Exercise 23: Zahlen bilden

Gegeben seien die Ziffern 1, 2, 3, 4, 5, 6 und 7.

a) Wie viele dreistellige Zahlen mit verschiedenen Ziffern lassen sich bilden?

Wie viele davon sind

b) kleiner als 600

c) kleiner als 600 und grösser als 300

d) gerade

e) ungerade

f) durch 5 teilbar

g) durch 25 teilbar?

Solution

a) $7\cdot6\cdot5=210$

b) $5\cdot6\cdot5=150$

c) $3\cdot6\cdot5=90$

d) $3\cdot6\cdot5=90$

e) $4\cdot6\cdot5=120$

f) $1\cdot6\cdot5=30$

g) $1\cdot2\cdot5=10$

Pascalsches Dreieck

Das Pascalsche Dreieck

Von der Algebra her weiss man, dass die Koeffizienten der Potenzen des Binoms $(a+b)$ in einem interessanten dreieckigen Zahlenschema übersichtlich dargestellt werden können. Potenzen vom Typ $(a+b)$ sehen in der sukzessiven Entwicklung wie folgt aus:

\begin{align*} (a+b)^0&=1\\ (a+b)^1&=a+b\\ (a+b)^2&=a^2+2ab+b^2\\ (a+b)^3&=a^3+3a^2b+3ab^2+b^3\\ \dots\quad &= \quad\dots\\ (a+b)^n&=a^n+na^{n-1}b+\dots+nab^{n-1}+b^n \end{align*}

Das Pascalsche Dreieck gibt die Koeffizienten der zusammengefassten Summanden wieder:

1

1\quad1

1\quad2\quad1

1\quad3\quad3\quad1

1\quad4\quad6\quad4\quad1

1\quad5\quad10\quad10\quad5\quad1

\dots\quad\quad\dots\quad\quad\dots

1\quad n\quad\quad\quad\dots\quad\quad\quad n\quad1

Note 2

Man beachte, dass die Exponenten der Summanden für $a$ von $n$ bis $0$ fallen, die von $b$ steigen von $0$ bis $n$ .

Exercise 24

Berechne die ersten fünf Zeilen des folgenden Schemas:

\binom{0}{0}

\binom{1}{0}\quad\binom{1}{1}

\binom{2}{0}\quad\binom{2}{1}\quad\binom{2}{2}

\binom{3}{0}\quad\binom{3}{1}\quad\binom{3}{2}\quad\binom{3}{3}

\dots\quad\quad\dots\quad\quad\dots

\binom{n}{0}\quad\binom{n}{1}\quad\quad\dots\quad\quad\binom{n}{n-1}\quad\binom{n}{n}

Solution

Man notiere das Pascalsche Dreieck.

Binomialkoeffizient

Theorem 5

Berechnet man die $n$ -te Potenz des Binoms $(a + b)$ , so ist der Koeffizient von $a^{n-k}b^k$ gleich $\binom{n}{k}$ für $0\leq k\leq n$ .

Proof

Um den Term mit $a^{n-k}b^k$ zu bekommen, muss man aus den $n$ Faktoren von $(a + b)^n = (a + b)(a + b)\dots(a + b)$ $k$ -mal den Summanden $b$ auswählen. Aus den restlichen $n-k$ Faktoren wird dann nur noch der Summand $a$ berücksichtigt. Diese Auswahl kann auf $\binom{n}{k}$ Arten erfolgen.

Theorem 6

\begin{align*} (a+b)^n &= \binom{n}{0}a^n+\binom{n}{1}a^{n-1}b+\binom{n}{2}a^{n-2}b^2+\dots\\ & \dots+\binom{n}{n-1}ab^{n-1}+\binom{n}{n}b^n \end{align*}

Note 3

Die aus der Kombinatorik bekannte Zahl $\binom{n}{k}$ nennt man deshalb auch Binomialkoeffizient.

Exercise 25: Binomialkoeffizient

a) Welche Eigenschaft der Binomialkoeffizienten ergibt sich aus der Tatsache, dass jede Zeile im Pascalschen Dreieck symmetrisch ist?

b) Zeige

\binom{n}{k}+\binom{n}{k+1} = \binom{n+1}{k+1}

für $0 \leq k \leq n-1$ . Interpretiere diese Beziehung im Pascalschen Dreieck.

Solution

a) $\binom{n}{k} = \binom{n}{n-k}$

b) Die Summe zweier benachbarter Binomialkoeffizienten ergibt den Binomialkoeffizienten eine Zeile weiter unten mittig.