Kombinatorik - Theoretical Computer Science · Kombinatorik c Javier Esparza und Michael Luttenberger Chair for Foundations of Software Reliability and Theoretical Computer Science

Kombinatorik

c©Javier Esparza und Michael Luttenberger

Chair for Foundations of Software Reliability and Theoretical Computer ScienceTechnische Universitat Munchen

2018/02/06

Kombinatorik 2

• Kombinatorik beschaftigt sich mit dem (effizienten) Abzahlen komplizierterMengen.

• Enstanden aus der Untersuchung von Glucksspielen

• Einfachster Wahrscheinlichkeitsbegriff |A||Ω| mit

Ω Menge aller moglichen Spielverlaufe (”Elementarereignisse“),

A ⊆ Ω Teilmenge aller Spielverlaufe, an denen man interessiert ist.

• Z.B.:

Wahrscheinlichkeit, dass funf beliebig gewahlte Karten ein”Straight Flush“

sind.

Kombinatorik 3

• Schwierigkeit bei Kombinatorik: Modellierung

Naturlichsprachliche Beschreibung muss formalisiert werden.

• Meistens mehrere aquivalente Formalisierungen moglich, manche einfacherabzuzahlen als andere.

• Beispiel: wieviele Poker-Hande sind moglich?

• Karten K = 2, 3, . . . , 10, J,Q,K,A♥,♦,♣,♠

• Anzahl Karten: |K| = 13 · 4 = 52.

• Eine Poker-Hand besteht aus 5 Karten.

• Modellierung als 5-Tupel oder als 5-elementige Menge moglich.

Kombinatorik 4

• Hand als 5-Tupel: Ωg = (k1, . . . , k5) ∈ K5 : |k1, . . . , k5| = 5.

• “Geordnete Hand”

• Fur i-te Karte ki nur noch |K| − (i− 1) Karten verfugbar.

• Insgesamt: 52 · 51 · 50 · 49 · 48 Hande

• Hand als 5-elementige Menge: Ωu = S ⊆ K : |S| = 5

• “Ungeordnete Hand”

• Jede ungeordnete Hand k1, . . . , k5 lasst sich zu 5 · 4 · 3 · 2 · 1 =: 5!geordneten Handen anordnen/auflisten.

• D.h. je 5! geordnete Hande entsprechen einer ungeordneten Hand.

• Also insgesamt:52 · 51 · 50 · 49 · 48

5!=

52!

5! · 47!=:

(52

5

).

Kombinatorik 5

• Prinzipielles Vorgehen sobald Modellierung fixiert: Zahlproblem schrittweisezuruckfuhren auf bereits bekannte bzw. leicht abzuzahlende Mengen.

• Beispiel: Berechnung der Wahrscheilichkeit eines “Straight Flush”.

• Ungeordnete Hand als 5-elementige Menge:

Ωu = H ⊆ K : |H| = 5

”Straight Flush“ entspricht dann der Menge

Au = 2♥, 3♥, 4♥, 5♥, 6♥, 2♥, 3♥, 4♥, 5♥, 6♥,. . . , 10♠, J♠, Q♠,K♠, A♠

Jeder”Straight Flush“ ist eindeutig durch die Farbe und die niedrigste Karte

bestimmt, daher:

|Au| = |2, 3, . . . , 10 × ♥,♦,♣,♠| = 36

Damit W’keit fur”Straight Flush“

|Au||Ωu|

=36(

52·51·...·485!

)(Wenn A♥, 2♥, 3♥, 4♥, 5♥, . . . , A♠, 2♠, 3♠, 4♠, 5♠ auch als

”Straight

Flush“ betrachtet, dann 40 statt 36.)

Kombinatorik 6

• Prinzipielles Vorgehen sobald Modellierung fixiert: Zahlproblem schrittweisezuruckfuhren auf bereits bekannte bzw. leicht abzuzahlende Mengen.

• Beispiel: Berechnung der Wahrscheilichkeit eines “Straight Flush”.

• Geordnete Hand als 5-Tupel mit 5 verschiedenen Eintragen:

Ωg = (k1, . . . , k5) ∈ K5 : |k1, . . . , k5| = 5

”Straight Flush“ entspricht dann der Menge

Ag = (k1, . . . , k5) | k1, . . . , k5 ∈ Au

Fur jedes Element von Au gibt es 5 · 4 · 3 · 2 · 1 := 5! Elemente in Ag. Daher:

|Ag| = |Au| · 5!

Damit W’keit fur”Straight Flush“

|Ag||Ωg|

=36 · 5!

52 · 51 · . . . · 48

Kombinatorik 7

• Jede endliche Menge A lasst sich mit [|A|] = 1, . . . , |A|”identifizieren“,

jeder abzahlbare Menge mit einer Teilmenge von N0.

• Damit lassen sich viele Abzahlprobleme auf Teilmengen von [n]k oder Nk0

zuruckfuhren, inbesondere (fur n, k ∈ N0):

• (s1, . . . , sk) ∈ [n]k : |s1, s2, . . . , sk| = k

• (s1, . . . , sk) ∈ [n]k : s1 < s2 < . . . < sk

• (s1, . . . , sk) ∈ [n]k : s1 ≤ s2 ≤ . . . ≤ sk

• (s1, . . . , sk) ∈ Nk0 : s1 + s2 + . . . + sk = n

• (s1, . . . , sk) ∈ Nk0 : s1 + s2 + . . . + sk ≤ n

• Wir bestimmen die Machtigkeit dieser Mengen in Abhangigkeit von n, k.

• Bevor wir auf die einzelnen Mengen genauer eingehen, erwahnen wir mehrereeinfache Vorgehensweisen/Regeln, um das Abzahlen von Mengen zuvereinfachen.

1 Kombinatorik

Einfache Zahlregeln

Das Urnenmodell: Ziehungen

Weitere Verteilungsprobleme

Einfache Zahlregeln

Einfache Zahlregeln 10

• Seien A,B beliebige Mengen.

• Gilt A ∩B = ∅, dann auch |A ∪B| = |A|+ |B|, da jedes Element von A ∪Bin genau einer der beiden Mengen vorkommt. D.h. die beiden Mengen konnenunabhangig voneinander abgezahlt werden.

AB

Ω

A

B

• Analog im Fall einer Partition: wenn X =⊎

i∈N0Ai dann |X| =

∑i∈N0|Ai|.

• Im Fall A ∩B 6= ∅, gilt |A ∪B| < |A|+ |B| und

|A ∪B| = |A|+ |B| − |A ∩B|

da |A|+ |B| jedes Element aus A ∩B zwei Mal zahlt.



• Es gilt |AB| = |A×B| = |A| · |B|, da wir fur jede der beidenBuchstaben/Komponenten unabhangig voneinander aus A bzw. B wahlendurfen.

• Z.B. Anzahl geordnete Hande 2, 3, . . . , J,Q,K,A♥,♦,♣,♠:

♥ ♦ ♣ ♠

2 2♥ 2♦ 2♣ 2♠3 3♥ 3♦ 3♣ 3♠...A A♥ A♦ A♣ A♠

Analog |A1 × . . .×An| = |A1| · · · |An|, z.B. |a, bn| = 2n.

• In Kombination mit erster Regel z.B. |A× (B ∪ C)| = |A| · (|B|+ |C|), fallsB ∩ C = ∅.



• Gilt f : A→ B mit∣∣f−1(b)

∣∣ = m konstant fur alle b ∈ B, d.h. jedes Elementaus b hat genau m Urbilder bzgl. f , dann gilt |A| = m |B|; d.h. es reicht, dieeinfachere der beiden Mengen abzuzahlen.

a1

a2

a3

a4

a5

a6

b1

b2

b3

Ist f bijektiv, dann gilt naturlich |A| = |f(A)| = |B| entsprechend derDefinition der Kardinalitat von Mengen.

• Das ist ein Spezialfall der ersten Regel fur A =⊎

b∈B f−1(b), z.B.:

A = f−1(b1) ∪ f−1(b2) ∪ f−1(b3) = a1, a6 ∪ a2, a4 ∪ a3, a5

1 Kombinatorik

Einfache Zahlregeln


Ziehen ohne Zurucklegen, mit Beachtung der Reihenfolge

Ziehen ohne Zurucklegen, ohne Beachtung der Reihenfolge

Ziehen mit Zurucklegen, ohne Beachtung der Reihenfolge

Beispiele



Ziehen aus einer Urne 15

• Urne: fiktives Gefaß mit n Kugeln, die mit den Zahlen 1, . . . , n beschriftetsind.

• Es werden k Kugeln hintereinander gezogen. Verschiedene Regeln fur dieZiehung fuhren zu verschiedenen Ergebnismengen.

• Ziehen ohne Zurucklegen, mit Beachtung der Reihenfolge.

An,k := (s1, . . . , sk) ∈ [n]k | |s1, s2, . . . , sk| = k

• Ziehen ohne Zurucklegen, ohne Beachtung der Reihenfolge.

Bn,k := (s1, . . . , sk) ∈ [n]k : s1 < s2 < . . . < sk

N.B.:”ohne Beachtung der Reihenfolge”’ aquivalent zu

”darf beliebige

Anordnung fixieren“.

• Ziehen mit Zurucklegen, ohne Beachtung der Reihenfolge.

Cn,k := (s1, . . . , sk) ∈ [n]k : s1 ≤ s2 ≤ . . . ≤ sk

• (Ziehen mit Zurucklegen, mit Beachtung der Reihenfolge: [n]k)

Ziehen aus einer Urne 16

• Wie viele mogliche Lottoziehungen gibt es?

49 Balle und 6 Ziehungen. Ziehen ohne Zurucklegen, ohne Beachtung derReihenfolge.

• Ein Wettbewerb vergibt einen ersten, einen zweiten, . . . , und einen k-tenPreis. Wie viele Moglichkeiten gibt es, die Preise unter den nWettbewerbsteilnehmer zu verteilen?

n Balle und k Ziehungen. Ziehen ohne Zurucklegen, mit Beachtung derReihenfolge.

• Wie viele Moglichkeiten gibt es, k Fußballspiele auf n Austragungsorte zuverteilen?

n Balle und k Ziehungen. Ziehen mit Zurucklegen, mit Beachtung derReihenfolge.

• Wie viele Moglichkeiten gibt es, k Euro unter n Personen zu verteilen?

n Balle und k Ziehungen. Ziehen mit Zurucklegen, ohne Beachtung derReihenfolge.


Ziehen ohne Zurucklegen, mit Beachtung der

Reihenfolge

− Zurucklegen, + Reihenfolge 18

An,k := (s1, . . . , sk) ∈ [n]k | |s1, s2, . . . , sk| = k

”k-Tupel mit k verschiedenen Eintragen aus [n] = 1, 2, . . . , n“

• Bsp.: (geordnete) Poker-Hande: (k1, . . . , k5) ∈ [52]5 | |k1, . . . , k5| = 5.

• Mogliche Falle in Abhangigkeit von n, k:

• Falls k > n, ist die Menge leer, da die Anforderungen nicht erfullt werdenkonnen, also |An,k| = 0.

• Falls k = 0 < n, dann erfullt nur das leere Tupel die Anforderungen, also|An,0| = 1.


An,k := (s1, . . . , sk) ∈ [n]k | |s1, s2, . . . , sk| = k



• Falls 0 < k ≤ n, dann konnen wir rekursiv vorgehen, d.h. das Problem auf sichselbst zuruckfuhren, nur mit kleineren Parameterwerten:

Jedes k-Tupel (s1, . . . , sk) ∈ An,k unterteilt sich in s1 und in ein Tupel(s2, . . . , sk−1) von k − 1 verschiedenen Eintrangen aus [n] \ s1.

Daher |An,k| = n · |An−1,k−1|, wobei wir bereits |An,0| = 1 wissen.


An,k := (s1, . . . , sk) ∈ [n]k | |s1, s2, . . . , sk| = k



• Mittels der Rekursionsgleichung

|An,k| = n · |An−1,k−1| mit An,0 = 1

erhalten wir z.B. fur die Anzahl der moglichen Hande beim Poker:

|A52,5| = 52 · |A51,4| = 52 ·51 · |A50,3| = . . . = 52 ·51 ·50 ·49 ·48 · |A47,0| =52!

47!

Im Allgemeinen: |An,k| = n · (n− 1) · . . . · (n− k + 1) =n!

(n− k)!.


cache = dict()def aufzaehlen(n,k):

if n < 0 or k < 0 or k > n:return tuple()

if k == 0:return tuple([tuple()])

ret = cache.get((n,k))if ret is not None:

return retret = list(aufzaehlen(n-1,k))for x in aufzaehlen(n-1,k-1):

for i in range(0,k):ret.append(x[:i] + (n,) + x[i:])

ret = tuple(ret)cache[(n,k)] = retreturn ret

https://www.python.org/



Ziehen ohne Zurucklegen, ohne Beachtung der

Reihenfolge

− Zurucklegen, − Reihenfolge 23

• Die Menge aller moglichen Ziehungen ist

s1, . . . , sk ∈ [n]k | |s1, . . . , sk| = k =:

([n]

k

)

”k-elementige Teilmengen von [n]“

• Jede k-elementige Teilmenge von [n] lasst sich durch Sortieren eindeutig miteinem sortierten k-Tupel identifizieren, z.B.

3, 4, 2, 6 7→ (2, 3, 4, 6)

• D.h. es gibt eine Bijektion zwischen der Menge([n]k

)der k-elementigen

Teilmengen von [n] und der Menge

Bn,k := (s1, . . . , sk) ∈ [n]k : s1 < s2 < . . . < sk

”Aufsteigend sortierte k-Tupel mit k verschiedenen Eintragen aus [n]“

• Beide Mengen sind somit gleichmachtig, und es reicht Bn,k abzuzahlen.


Bn,k := s1, . . . , sk) ∈ [n]k : s1 < s2 < . . . < sk

• Bsp.: Anzahl der ungeordneten Hande beim Poker mit 52 Karten.

Fixiere beliebige Aufzahlung β : Kbij.−−→ [52], z.B.:

β(2♥) = 1, . . . , β(A♥) = 13, β(2♦) = 14, . . . , β(2♣) = 27, . . . , β(A♠) = 52

Damit: Ungeordnete Handbij.−−→ Teilmenge von [52]

bij.−−→ sortiertes Tupel.

8♦, A♠, 2♥, 3♥, 4♦ 7→ 20, 52, 1, 2, 16 7→ (1, 2, 16, 20, 52)


Bn,k := s1, . . . , sk) ∈ [n]k : s1 < s2 < . . . < sk

• Jedes (s1, . . . , sk) ∈ Bn,k kann auf k! unterschiedliche Arten umsortiertwerden.

• Gegeben ein sortiertes Tupel (s1, . . . , sk) ∈ Bn,k setze S := s1, . . . , sk undbetrachte die Menge T := (t1, . . . , tk) ∈ Sk : |t1, . . . , tk| = k

• Das sind gerade alle moglichen Permutationen der Eintrage von (s1, . . . , sk).

• T steht in Bijektion mit Ak,k; also |T | = |Ak,k| = k!.

• Umgekehrt entsprechen jeweils k! Tupel aus An,k genau einem Tupel aus

Bn,k, also |Bn,k| =|An,k|k!

(mit 0! := 1).

• Bsp.:52!

47!geordnete Hande,

52!

47! · 5!ungeordnete Hande.


Bn,k := s1, . . . , sk) ∈ [n]k : s1 < s2 < . . . < sk

• Mit |An,k| =n!

(n− k)!fur 0 ≤ k ≤ n erhalt man insgesamt

|Bn,k| =n!

(n− k)! k!.

• Allgemein definiert man den Binomialkoeffizienten(n

k

):=

n!

(n− k)! k!falls 0 ≤ k ≤ n

0 sonst

so dass |Bn,k| =(n

k

), d.h.

(n

k

)ist die Anzahl der k-elementigen

Teilmengen einer n-elementigen Menge.

• Wichtiger Ansatz hier: Falls f : X → Y bekannt mit∣∣f−1(y)

∣∣ = m konstantfur alle y ∈ Y , dann |X| = m · |Y |, und es reicht die einfachere der beidenMengen X,Y zu zahlen.


Bn,k := s1, . . . , sk) ∈ [n]k : s1 < s2 < . . . < sk

• Wir betrachten noch einen alternativen Weg zur Bestimmung von |Bn,k|mittels einer Rekursionsgleichung.

• Jedes sortierte k-Tupel (s1, . . . , sk) ∈ Bn,k mit Eintragen aus [n] fallt ingenau eine der beiden Klassen:

• n kommt nicht vor, d.h. sk ≤ n− 1, also (s1, . . . , sk) ∈ Bn−1,k.

• n kommt vor, d.h. sk = n und damit (s1, . . . , sk−1) ∈ Bn−1,k−1.

(D.h. (s1, . . . , sk−1, n) ∈ Bn,k steht in Bijektion mit Bn−1,k−1.)

Damit konnen wir statt Bn,k die beiden Mengen Bn−1,k und Bn−1,k−1jeweils zahlen und einfach addieren:

|Bn,k| = |Bn−1,k|+ |Bn−1,k−1| mit |Bn,0| = 1


Bn,k := s1, . . . , sk) ∈ [n]k : s1 < s2 < . . . < sk

• Damit erhalt man die Rekursionsgleichung fur die Binomialkoeffizienten:(n

k

)=

(n− 1

k

)+

(n− 1

k − 1

)

die eine einfache rekursive Berechnung von

(n

k

)erlaubt (siehe dynamische

Programmierung in Info 1).

• Wichtiger Ansatz hier: Statt A direkt zu zahlen, partitioniere A =⊎m

i=1Ai indisjunkte einfachere Mengen A1, . . . , Am, dann gilt

|A| =m∑i=1

|Ai| .

Entsprechend auch A =⊎

i∈N0Ai mit |A| =

∑i∈N0|Ai|.

Binomialkoeffizienten 29

cache = dict()def aufzaehlen(n,k):if n < 0 or k < 0 or k > n:

return tuple()if k == 0:

return tuple([tuple()])ret = cache.get((n, k))if ret is not None:

return retret = list(aufzaehlen(n - 1, k))for x in aufzaehlen(n - 1, k - 1):

new_x = list(x)new_x.append(n)ret.append(tuple(new_x))

ret = tuple(ret)cache[(n, k)] = retreturn ret



Exkurs: Die Binomialformel

• Die Binomialformel, gultig fur alle x, y ∈ R, n ∈ N0, lautet:

(x+ y)n =

n∑k=0

(n

k

)xkyn−k

Begrundung: Multiplizert man mechanisch

n︷︸︸︷(x+ y) · · · (x+ y) aus, so gilt

(x+ y)n =∑

(a1,...,an)∈x,yna1a2 · · · an

d.h. man erhalt jedes Wort aus x, yn genau einmal als Summanden, daman aus jedem der n Faktoren (x+ y) entweder x oder y wahlen darf.

• Es gilt a1 · · · an = xkyn−k gdw. x genau k-mal in a1 · · · an vorkommt.Damit gibt es eine Bijektion zwischen den Tupeln (a1, . . . , an) mita1 · · · an = xkyn−k und den k-elementigen Untermengen von [n].

• Es folgt: es gibt

(n

k

)Summanden mit Betrag xkyn−k.

Exkurs: Einige Anwendungen der Binomialformel. 31

• Mit y := 1 ergibt sich:

(1 + x)n =

n∑k=0

(n

k

)xk

Leitet man beide Seiten nach x ab, so erhalt man hiermit:

n(1 + x)n−1 =

n∑k=1

(n

k

)kxk−1

Insbesondere fur x = 1 folgt daher:

n · 2n−1 =

n∑k=1

(n

k

)k


• Entsprechend ergibt sich einerseits

(1 + x)m(1 + x)n = (1 + x)m+n =

m+n∑k=0

(m+ n

k

)xk

und andererseits

(1 + x)m(1 + x)n =

(m∑i=0

(m

i

)xi

) n∑j=0

(n

j

)xj

︸︷︷︸

∗

Der Koeffizient von xk in ∗ ergibt sich durch Summation der Koeffizientenvon xi und xj fur i+ j = k:(

m+ n

k

)xk =

k∑i=0

(m

i

)xi(

n

k − i

)xk−i


• Mit x := 1 erhalt man die Vandermondesche Identitat:(m+ n

k

)=

k∑i=0

(m

i

)(n

k − i

)

• Alternative Ableitung der Vandermondesche Identitat:

Um k Elemente aus [m+ n] ohne Zurucklegen und ohne Beachtung derReihenfolge zu ziehen, kann folgendermaßen vorgegangen werden:

• Wahle eine Zahl 0 ≤ i ≤ k.

• Ziehe i Elemente aus [m].

• Ziehe die verbleibenden k − i Elemente aus [m + n] \ [m].

Fur jedes i gibt es

(m

i

)(n

k − i

)moglichen Ziehungen.


• Ebenfalls mittels der Binomialformel erhalt man

0 =

n∑k=0

(n

k

)(−1)k

und

2n =

n∑k=0

(n

k

)

Letzteres bedeutet gerade, dass [n] genau 2n Teilmengen besitzt, da

(n

k

)die

Anzahl der k-elementigen Teilmengen von [n] ist.


Ziehen mit Zurucklegen, ohne Beachtung der

Reihenfolge

+ Zurucklegen, − Reihenfolge 36

Cn,k := (s1, . . . , sk) ∈ [n]k : s1 ≤ s2 ≤ . . . ≤ sk

”Aufsteigend sortierte k-Tupel uber [n] mit Wiederholungen“

• Bsp.: 5 Karten ziehen mit Zurucklegen in Stapel nach jeder Ziehung

Karten wieder mit [52] identifiziert.

Geordnete Hand:∣∣(s1, s2, . . . , s5) ∈ [52]5

∣∣ = 525.

Ungeordnete Hand:∣∣(s1, s2, . . . , s5) ∈ [52]5 : s1 ≤ s2 ≤ . . . ≤ s5∣∣ = |C52,5| =?

(Erinnerung:”ungeordnet“ entspricht

”fixiere bel. Anordnung“)


Cn,k := (s1, . . . , sk) ∈ [n]k : s1 ≤ s2 ≤ . . . ≤ sk

”Aufsteigend sortierte k-Tupel uber [n] mit Wiederholungen“

• Beobachtung: Da die Anordnung vorgegeben ist, reicht es zu wissen, wiehaufig jeder Wert s ∈ [n] in (s1, . . . , sk) vorkommt.

• Dk,n := (k1, . . . , kn) ∈ Nn0 | k1 + k2 + . . .+ kn = k Zahlvektoren mit

Summe k.

Eintrag ki zahlt Vorkommen von Wert i (d.h., wie oft der Wert i gezogenwurde).

• Bsp.: n = 5, k = 6

C5,6 3 (1, 1, 2, 4, 5, 5) 7→← [ (2, 1, 0, 1, 2) ∈ D6,5

• Da |Cn,k| = |Dk,n| (Positionen von n und k beachten!) zahlen wir Dn,k stattCn,k.


Dn,k := (s1, . . . , sk) ∈ Nk0 : s1 + s2 + . . .+ sk = n

”Zahlvektoren mit k Eintragen und Summe n“

• Eselsbrucke: Komponenten des Zahlvektors unar statt dezimal darstellen

Aus 0 wird ε, aus 1 wird |, aus 2 wird ||, aus 10 wird ||||||||||, usw.

• Beispiel:

(1, 1, 2, 4, 5, 5) 7→← [ (2, 1, 0, 1, 2) 7→← [ ||, |, , |, ||

• Dn,k entspricht die Menge der Worter, die aus genau n Strichen und k − 1Kommata bestehen.


Dn,k := (s1, . . . , sk) ∈ Nk0 : s1 + s2 + . . .+ sk = n

”Zahlvektoren mit k Eintragen und Summe n“

• Jedes Wort der Lange n+ k− 1 mit genau n Strichen und k− 1 Kommata istdurch die Positionen der Striche bzw. der Kommata vollstandig beschrieben.

• Beispiel:

(1, 1, 2, 4, 5, 5) 7→←[ (2, 1, 0, 1, 2) 7→←[ ||, |, , |, || 7→←[ 1, 2, 4, 7, 9, 10

• Es gibt

(n+ k − 1

n

)Moglichkeiten, um die Positionen der Striche zu wahlen.

• Wir erhalten: |Dn,k| =(n+ k − 1

n

)= |Ck,n| und |Cn,k| =

(n+ k − 1

k

).

Eine Variante 40

En,k := (s1, . . . , sk) ∈ Nk0 : s1 + s2 + . . .+ sk ≤ n

”Zahlvektoren mit k Eintragen und Summe hochstens n“

• Z.B. Ziehen von maximal 5 Karten mit Zurucklegen und ohne Beachtung derReihenfolge.

• Ansatz: En,k steht in Bijektion mit Dn,k+1 (”Zahlvektoren mit k + 1

Eintragen und Summe n“)

Eintrag sk+1 = n− (s1 + . . .+ sk) sammelt den”Rest“:

En,k 3 (s1, . . . , sk) 7→← [ (s1, . . . , sk, n− (s1 + s2 + . . .+ sk)) ∈ Dn,k+1

Damit: |En,k| = |Dn,k+1| =(n+ k

n

).

Eine Variante 41

• Alternativer Ansatz (zum Vergleich): fur jedes 0 ≤ m ≤ n gibt es |Dm,k|Zahlvektoren mit Summe m.

Es folgt

|En,k| =n∑

m=0

|Dm,k| =n∑

m=0

(m+ k − 1

m

)Also

n∑m=0

(m+ k − 1

m

)=

(n+ k

n

)


Beispiele

Drei einfache Aufgaben 43

• Wie viele Moglichkeiten gibt es, die Buchstaben ABCDEFGH so anzuordnen,dass die Buchstabenfolge ABC enthalten ist?

• Wir fuhren das das Problem aus das Ziehen von 6 Elementen ohneZurucklegen aus der 6-elementigen Menge ABC,D,E,F,G,H . Damit gibtes 6! = 720 Moglichkeiten.

• Wie viele verschiedene Worter erhalt man durch Permutation der Buchstabenvon “hallo” ?

• Wenn die zwei “l” unterscheidbar waren (hal1l2o), dann gabe es 5! = 720Worter.

• Dadurch wird jedes Wort jedoch genau zweimal gezahlt: Z.B. ist ohlal mitohl1al2 und ohl2al1 zweimal vertreten. Man erhalt also 720/2 = 360 Worter.

• Wie viele verschiedene Worter erhalt man durch Permutation der Buchstabenvon “bewundernswert”?

• Das Wort enthalt drei “e”, zwei “w”, zwei “n” und zwei “r”. Mit 14! wirdjedes Wort 3! · 2! · 2! · 2! = 48 Mal gezahlt. Man erhalt also14!/48 = 1.816.214.400 Worter.

Die Lottosensation am 29.6.1995 44

Stuttgart(dpa/lsw). Die Staatliche Toto-Lotto GmbH inStuttgart hat eine Lottosensation gemeldet: Zum ersten Malin der 40jahrigen Geschichte das deutschen Zahlenlottoswurden zwei identische Gewinnreihen festgestellt. Am 21. Junidieses Jahres [3016te Ausspielung] kam im Lotto am Mittwochin der Ziehung A die Gewinnreihe 15-25-27-30-42-48 heraus.Genau die selben Zahlen wurden bei der 1628. Ausspielung imSamstaglotto schon einmal gezogen, namlich am 20.Dezember 1986. Welch ein Lottozufall!

• Wirklich eine Sensation?


• Es gibt M :=

(49

6

)= 13.983.816 mogliche (Sechser-)Ziehungen.

• Wie viele Sequenzen von 3016 Ziehungen gibt es, und wie viele davonenthalten irgendeine Ziehung mindestens zweimal?

• Sei Z die Menge aller Sechser-Ziehungen, |Z| = M . Wir ziehen 3016Elemente aus Z mit Zurucklegen und mit Beachtung der Reihenfolge. DieAnzahl S der moglichen Tupeln von Sechser-Ziehungen betragt S = M3016.

• Wie viele von diesen Tupeln enthalten irgendeine Sechser-Ziehung mindestenszweimal?

Trick: wir berechnen die Anzahl HE der Tupeln, in denen jedeSechser-Ziehung hochstens einmal vorkommt, und substrahieren sie von S.

Fur die Berechnung von HE ziehen wir 3016 Elemente aus Z ohneZurucklegen mit Beachtung der Reihenfolge. Wir erhalten:

HE =M !

(M − 3016)!


• Unter der Annahme, dass alle Sequenzen genau so wahrscheinlich sind, habenwir fur die W‘keit p, nach 3016 Ziehungen mindestens eine Wiederholunggesehen zu haben:

p =S − HE

S= 1−

M3016 − M !(M−3016)!

M3016= 1−

3016∏j=1

M − j + 1

M

• Mit der Abschatzung 1− x ≤ e−x erhalten wir

p = 1−3016∏j=1

M − j + 1

M= 1−

3016∏j=1

1− j − 1

M

≥ 1−3016∏j=1

e−j−1M = 1− e−

1M

∑3016j=1 j

= 1− e− 3016·30152·M

= 1− e−0.325 ≈ 0, 278 = 27, 8%

Die Kiffen-Umfrage vom 17.10.2017 47

Am 17.10.2017 werden n Studierende mit Hilfe des“Lugen-Protokolls” gefragt, ob sie seit dem 1.09.2017 gekiffthaben. Sei j die Anzahl der Studierenden, die tatsachlichgekifft haben. Mit welcher W’keit antworten m Studierendemit “ja” (m ≥ j)?

• Das ist die W’keit, dass bei (n− j) Wurfe einer Munze genau (m− j)-mal“Zahl” vorkommt.

• Anzahl der moglichen Wurfsequenzen: 2n−j

• Anzahl der Wurfsequenzen mit mindestens (m− j)-mal “Zahl”:

• W’keit:1

2n−j

(n− jm− j

)

Die Kiffen-Umfrage vom 17.10.2017 48

• W’keit fur n = 720 und m = 453 als Funktion von j:

• Viel mehr dazu in DWT im 4. Semester!

1 Kombinatorik

Einfache Zahlregeln



Stirling-Zahlen 2. Art

Die Siebformel

Partitionsfunktion/Zahlpartitionen

Anwendungsbeispiel: Lastverteilung in peer-to-peer Netzwerke

Zusammenfassung


Verteilungsprobleme 51

• Wir haben schon einige “Verteilungsprobleme” gelost, wie die Berechnungder Moglichkeiten, k Fußball-Spiele auf n Austragungsorte oder kEuromunzen unter n Menschen zu verteilen.

• Wir betrachten nun weitere Probleme dieser Art:

• Wie viele Moglichkeiten gibt es, k Weihnachtsgeschenke unter n Kindern zuverteilen, so dass jedes Kind mindestens ein Geschenk erhalt?

Sowohl die Kinder als auch die Geschenke sind unterscheidbar!

• Wie viele Moglichkeiten gibt es, k Weihnachtsgeschenke in n Packchenaufzuteilen, so dass jedes Packchen mindestens ein Geschenk enthalt?

Die Packchen sind nicht unterscheidbar, die Geschenke schon.

• Wie viele Moglichkeiten gibt es, n Euromunzen unter k Kinder zu verteilen, sodass jedes Kind mindestens 1 Munze erhalt?

Die Munzen sich nicht unterscheidbar, die Kinder schon.

• Wie viele Moglichkeiten gibt es, n Euromunzen in k Packchen aufzuteilen, sodass jedes Packchen mindestens 1 Munze enthalt?


Stirling-Zahlen 2. Art

Stirling-Zahlen 2. Art 53

• Wie viele Moglichkeiten gibt es, k (Weihnachts)-Geschenke unter n Kindernzu verteilen, so dass jedes Kind mindestens ein Geschenk erhalt?

• Sowohl die Kinder als auch die Geschenke sind unterscheidbar!

• Die Menge der Moglichkeiten ist

Fn,k := (s1, . . . , sk) ∈ [n]k : |s1, s2, . . . , sk| = n .

Hier ist si das Kind, welches das i-te Geschenk erhalt.

• Z.B. fur k = 6, n = 4 beschreibt die Tupel (3, 1, 3, 2, 2, 4) das die Geschenke1, 2, 3, 4, 5, 6 jeweils an die Kinder 3, 1, 3, 2, 2, 4 ausgehandigt werden.

Es gilt z.B. (3, 3, 2, 2, 4, 4) /∈ Fn,k denn Kind 1 geht leer aus.

• Fn,k ist fur k ≥ n nicht leer; fur k < n jedoch Fn,k = ∅. Es gilt |Fn,n| = n!.


• Aquivalente Darstellung: wir geben fur jedes Kind an, welche Untermenge derGeschenke es erhalt.

• Mathematisch: Ordne dem k-Tupel (s1, . . . , sk) ∈ Fn,k diejenige geordnetePartition von [k] in genau n Klassen zu, die gegeben wird durch: i, j ∈ [k]liegen in derselben Klasse, falls si = sj .

• Z.B. fur n = 4, k = 6:

(3, 1, 3, 2, 2, 4) 7→ (2, 4, 5, 1, 3, 6)(3, 1, 3, 4, 2, 4) 7→ (2, 5, 1, 3, 4, 6)


• Wieviele Moglichkeiten gibt es, k Geschenke in n Packchen aufzuteilen, sodass jedes Packchen mindestens ein Geschenk enthalt?

• Die Packchen sind nicht unterscheidbar!

• Eine Aufteilung entspricht nun einer (ungeordneten) Partition von [k] in [n]Aquivalenzklassen:

2, 4, 5, 1, 3, 6 = 1, 3, 2, 6, 4, 5

• Die Anzahl der Partitionen von n Elementen in k (nicht leere) Klassenbezeichnet man als Stirling-Zahl zweiter Art Sn,k.

• Achtung!:

• In Fn,k bezeichnet n die Anzahl der Klassen und k die Anzahl der Objekte.

• In Sn,k bezeichnet n die Anzahl der Objekte und k die Anzahl der Klassen.


• Fur jede Partition von n Elementen in k (nicht leere) Klassen gibt es genauk! geordnete Partitionen. Z.B. fur n = 4, k = 3 haben wir

2, 1, 4, 3 7→

(2, 1, 4, 3) , (2, 3, 1, 4)(1, 4, 2, 3) , (1, 4, 3, 2)(3, 1, 4, 2) , (3, 2, 1, 4)

• Somit gilt

|Fn,k| = n! · Sk,n

• Wir bestimmen Sk,n mit Hilfe einer Rekursionsgleichung.

Rekursionsgleichung fur die Stirling-Zahlen 2. Art: Idee 57

• Betrachten wir die Partitionen von [5] in 4 Klassen:

1, 2, 3, 4, 5 1, 5, 2, 3, 41, 2, 3, 4, 5 1, 2, 5, 3, 41, 2, 4, 3, 5 1, 2, 3, 5, 41, 2, 3, 4, 5 1, 2, 3, 4, 51, 3, 2, 4, 51, 4, 2, 3, 5

• Wir teilen sie auf in Partitionen, in denen 5 eine eigene Klasse bildet(6 Stuck, links) und den Rest (4 Stuck, rechts).

• Wenn wir “die 5 entfernen” erhalten wir links alle Partitionen von [4] in 3Klassen und rechts alle Partitionen von [4] in 4 Klassen

1, 2, 3, 4 1, 2, 3, 41, 2, 3, 41, 2, 4, 31, 2, 3, 41, 3, 2, 41, 4, 2, 3

Rekursionsgleichung fur die Stirling-Zahlen 2. Art: Idee 58

• Jede Partition von [4] in 3 Klassen ergibt eine Partition von [5] in 4 Klassen:

1, 2, 3, 4 7→ 1, 2, 3, 4, 5

• Jede Partition von [4] in 4 Klassen ergibt 4 Partitionen von [5] in 4 Klassen:

1, 2, 3, 4 7→ 1, 5, 2, 3, 41, 2, 5, 3, 41, 2, 3, 5, 41, 2, 3, 4, 5

• Es gilt also: S5,4 = S4,3 + 4 · S4,4

Rekursionsgleichung fur die Stirling-Zahlen 2. Art 59

• Ahnlich zu der Rekursionsgleichung

(n

k

)=

(n− 1

k

)+

(n− 1

k − 1

)fur die

Binomialzahlen partitioniert man nach n.

• Sei P = P1, . . . , Pk eine Partition von [n] in k Klassen.

Falls n ∈ P, dann ist P \ n eine Partition von [n− 1] in k− 1 Klassen.

Ansonsten ist P \ n : P ∈ P eine Partition von [n− 1] in k Klassen.

• Dabei lasst sich jede Partition von [n− 1] in k Klassen auf k Arten zu einerPartition von [n] in k Klassen erweitern: man muss nur die Klasse wahlen,welche um n erganzt werden muss.

• Damit gilt fur n ≥ k ≥ 0:

Sn,k = Sn−1,k−1 + k · Sn−1,k fur n > k > 0Sn,0 = 0 fur n > 0Sn,n = 1


Die Siebformel

Eine geschlossene Form fur |Fn,k| und Sn,k 61

• Fn,k := (s1, . . . , sk) ∈ [n]k : |s1, s2, . . . , sk| = n .

• Um eine geschlossene Formel fur |Fn,k| und Sn,k zu erhalten, betrachten wireinen zweiten Ansatz, um Fn,k abzuzahlen. Wir verwenden zwei Techniken:

• Abzahlen des Komplements.Problem: Bestimmung von |X| fur eine Menge X ⊆ U .Statt |X| direkt zu berechnen kann es einfacher sein, |U | und |Xc| furXc = U \X zu bestimmen und |X| = |U | − |Xc| zu setzen.

• Prinzip der Inklusion und Exklusion (kurz: Siebformel).Eine Formel fur die Bestimmung von |X| wenn X =

⋃ni=1 Yi und die Yi nicht

notwendigerweise disjunkt sind.

• Das Komplement F cn,k := [n]k \ Fn,k besteht gerade aus allen k-Tupeln, in

welchen mindestens ein Element aus [n] nicht vorkommt.

• Offensichtlich gilt nk =∣∣∣F c

n,k

∣∣∣+∣∣∣Fn,k

∣∣∣, es reicht also∣∣∣F c

n,k

∣∣∣ zu bestimmen.

Bestimmung von∣∣F c

n,k

∣∣ 62

• Erinnerung: F cn,k enthalt alle k-Tupeln, in welchen mindestens ein Element

aus [n] nicht vorkommt.

• Damit gilt

F cn,k =

⋃x∈[n]

([n] \ x)k

• ([n] \ x)k ist die Menge aller k-Tupeln, in denen x nicht vorkommt.

• Es folgt: Jedes k-Tupel, in welchem mindestens ein Element aus [n] nichtvorkommt, gehort zu mindestens einer der Mengen ([n] \ x)k.

• Problem: I.A. gilt nur∣∣∣F c

n,k

∣∣∣ < ∑x∈[n]

|[n] \ x|k = n · (n− 1)k, da z.B. alle

Tupel ([n] \ 1, 2)k sowohl fur x = 1 als auch fur x = 2 mitgezahlt werden.

• Die Siebformel erlaubt, die Summation zu korrigieren.

Die Siebformel 63

• Fur die Vereinigung zweier Mengen A,B gilt:

|A ∪B| = |A|+ |B| − |A ∩B| .

AB

Ω

A

B

Die Siebformel 64

• Fur die Vereinigung dreier Mengen A,B,C ist zu berucksichtigen, dass|A|+ |B|+ |C| jedes Element in genau zwei der Mengen zweimal zahlt, undjedes Element in den drei Mengen dreimal zahlt.

• Damit gilt:

|A ∪B ∪ C| = + |A|+ |B|+ |C|− |A ∩B| − |A ∩ C| − |B ∩ C|+ |A ∩B ∩ C| .

A

B C

A

B

C

Die Siebformel 65

• Fur die Vereinigung vierer Mengen A,B,C,D gilt:

+ |A ∪B ∪ C ∪D|

= + |A|+ |B|+ |C|+ |D|− |A ∩B| − |A ∩ C| − |A ∩D| − |B ∩ C| − |B ∩D| − |C ∩D|+ |A ∩B ∩ C|+ |A ∩B ∩D|+ |A ∩ C ∩D|+ |B ∩ C ∩D|− |A ∩B ∩ C ∩D| .

• Fur X =⋃m

i=1 Yi gilt die Siebformel:

|X| =m∑r=1

(−1)r−1∑

I⊆[m] : |I|=r

∣∣∣∣∣⋂i∈I

Yi

∣∣∣∣∣

Die Siebformel 66

• Die Siebformel lasst sich dabei mittels Induktion nach m beweisen.

• Ansatz fur den Beweis des Induktionsschritts:

m+1⋃i=1

Yi = Ym+1 ∪m⋃i=1

Yi︸︷︷︸=:Z

Dann zuerst Formel fur m = 2 auf Ym+1 ∪ Z und induktiv Formel fur m aufYm+1 ∩ Z =

⋃mj=1(Yj ∩ Ym+1) anwenden.

Bestimmung von∣∣F c

n,k

∣∣ mit Hilfe der Siebformel 67

• Damit die Siebformel sinnvoll eingesetzt werden kann, mussen die Schnitte⋂i∈I Yi einfach(er) abzuzahlen sein.

• Im Fall von X = F cn,k und Yi = ([n] \ i) ist

⋂i∈I Yi die Menge aller

k-Tupeln mit Elementen aus [n] \ I.

• Es folgt:∣∣⋂

i∈I Yi∣∣ =

∣∣([n] \ I)k∣∣ = (n− |I|)k.

Insbesondere, wenn |I1| = |I2| dann gilt∣∣⋂

i∈I1 Yi∣∣ =

∣∣⋂i∈I2 Yi

∣∣.• [n] enthalt genau

(nm

)Teilmengen I mit |I| = m. Durch Einsetzen in die

Siebformel erhalt man:∣∣F cn,k

∣∣ =

n∑|I|=1

(−1)|I|+1

(n

|I|

)(n− |I|)k

Mittels elementarer Umformungen erhalt man hieraus:

n!Sk,n = |Fn,k| =n∑

i=0

(−1)i(n

i

)(n− i)k =

n∑i=0

(−1)n−i(n

i

)ik

Stirling-Zahlen 2. Art und Binomialzahlen 68

• Fur die Stirling-Zahlen 2. Art schreibt man auch Sn,k =

nk

:

n+ 1k

=

n

k − 1

+ k ·

nk

mit

00

= 1,

n+ 1

0

= 0,

nn

= 1

und nk

=

1

k!

k∑i=0

(−1)k−i(k

i

)in

• Vergleich mit den Binomialkoffizienten:(n+ 1

k

)=

(n

k − 1

)+

(n

k

)mit

(0

0

)= 1,

(n+ 1

0

)= 0,

(n

n

)= 1

Stirling-Zahlen 2. Art und Binomialzahlen 69

cache = dict()def aufzaehlen(n,k):

if n < 0 or k < 0 or k > n:return tuple()

if n == 0:return tuple([tuple()])

if k == 0:return tuple()

ret = cache.get((n, k))if ret is not None:

return retret = [ pi + ((n,),) for pi in aufzaehlen(n-1,k-1)]for pi in aufzaehlen(n - 1, k):

for i in range(0,k):ret.append(pi[:i] + (pi[i]+(n,),) + pi[i+1:])pass

passret = tuple(ret)cache[(n, k)] = retreturn ret




Partitionsfunktion/Zahlpartitionen

Geordnete Zahlpartitionen 71

• Wieviele Moglichkeiten gibt es, n Euro unter k Kinder zu verteilen, so dassjedes Kind mindestens 1 Euro erhalt?

• Die Euros sind nicht unterscheidbar, die Kinder schon!

Gn,k := (s1, . . . , sk) ∈ Nk : s1 + . . .+ sk = n

”sortierte Zahlvektoren mit k Komponenten und Summe n“

• Jedes Tupel (s1, . . . , sk) kann geschrieben werden als

n =

n︷︸︸︷1 + · · ·+ 1︸︷︷︸

s1

+ 1 + · · ·+ 1︸︷︷︸s2

+ · · ·+ 1 + · · ·+ 1︸︷︷︸sk

Damit wird das Tupel eindeutig durch die Plus-Zeichen bestimmt, die die sitrennen.

Geordnete Zahlpartitionen 72

• Die Anzahl der geordneten Partitionen ist damit gleich der Anzahl derMoglichkeiten, k − 1 Plus-Zeichen aus den insgesamt n− 1 Plus-Zeichenauszuwahlen.

|Gn,k| =(n− 1

k − 1

)• Aus

• Eine (n− 1)-elementige Menge hat

(n− 1

k − 1

)Teilmengen mit

(k − 1)-Elementen.

• Eine (n− 1)-elementige Menge hat 2n−1 Teilmengen.

folgt:

|Gn| =n∑

k=1

|Gn,k| =n∑

k=1

(n− 1

k − 1

)= 2n−1

(Ungeordnete) Zahlpartitionen 73

• Wieviele Moglichkeiten gibt es, n Euro in k Packchen aufzuteilen, so dassjedes Packchen mindestens 1 Euro enthalt?

• Sowohl die Euros als die Packchen sind nicht unterscheidbar!

• Das ist die Anzahl der Zahlpartitionen von n in k positive Summanden

Pn,k := (s1, . . . , sk) ∈ Nk : s1 + . . .+ sk = n, s1 ≤ s2 ≤ . . . ≤ sk

• |Pn,k| wurde u.a. von Hardy und Ramanujan untersucht.

https://de.wikipedia.org/wiki/Godfrey_Harold_Hardy

https://de.wikipedia.org/wiki/S._Ramanujan

Kombinatorik: Grundlagen 74

Pn,k = (s1, . . . , sk) ∈ Nk : s1 + . . .+ sk = n, s1 ≤ . . . ≤ sk

”Partitionen von n“

• Wir leiten fur |Pn,k| wieder eine Rekursionsgleichung her, indem wir danachunterscheiden, ob s1 = 1 gilt:

• (s1, s2, . . . , sk) ∈ Pn,k : s1 = 1 steht in Bijektion mit Pn−1,k−1 mittels

(1, s2, . . . , sk) 7→ (s2, . . . , sk)

• (s1, s2, . . . , sk) ∈ Pn,k : s1 > 1 steht in Bijektion mit Pn−k,k mittels

(s1, . . . , sk) 7→ (s1 − 1, . . . , sk − 1)

• Es folgt somit fur 0 ≤ k ≤ n

|Pn,k| = |Pn−1,k−1|+ |Pn−k,k| fur k > 0|Pn,0| = 0 fur n > 0|P0,0| = 1

Kombinatorik: Grundlagen 75

• Wieviele Moglichkeiten gibt es, n Euro in k Packchen aufzuteilen, wennPackchen auch 0 Euro enthalten durfen?

Hn,k = (s1, . . . , sk) ∈ N0k : s1 + . . .+ sk = n, s1 ≤ . . . ≤ sk

• Hn,k und Pn+k,k in Bijektion mittels:

Hn,k 3 (s1, . . . , sk) 7→ (s1 + 1, . . . , sk + 1) ∈ Pn+k,k

also |Hn,k| = |Pn+k,k|.


Anwendungsbeispiel: Lastverteilung in peer-to-peer

Netzwerke

Lastverteilung in peer-to-peer Netzwerke 77

• n Dateien werden zufallig in n Server gespeichert. Gesucht wird eine Zahl k,so dass mit großer W’keit kein Server mehr als k Dateien bekommt.

• Modellierung: n unterscheidbare Balle (Dateien) und n unterscheidbareUrnen (Server).

• Gesamtzahl aller moglichen Verteilungen: nn

• Wie viele Verteilungen gibt es, in denen mindestens eine Urne mindestens kBalle enthalt?

• Sei M die Anzahl der Moglichkeiten, in denen eine fixe Urne mindestens kBalle enthalt. Es gilt:

M ≤(n

k

)nn−k

(Wir wahlen k Balle fur die fixe Urne, die anderen Balle werden beliebigverteilt.)


• Mit der Abschatzung

(n

k

)≤(enk

)kerhalten wir

M ≤(n

k

)nn−k ≤

(enk

)knn−k =

( ek

)knn

• Die Anzahl der Moglichkeiten, in denen mindestens eine Urne mindestens kBalle enthalt ist nach oben beschrankt durch nM .(Moglichkeiten, in denen u Urnen mindestens k Balle enthalten, werdenu-mal gezahlt.)

• Die W’keit pk in mindestens eine Urne k Balle zu finden erfullt

pk ≤nM

nn≤ n

( ek

)k• Mit k := e lnn erhalt man

pe lnn ≤ n(

1

lnn

)e lnn

= n1−e ln(lnn)


• Tabelle fur pk (in % )

n 100 1000 104 105 106 107

k = 7 13.0k = 8 1.8 18.0k = 9 0.2 2.1 21.9k = 10 0.02 0.2 2.2 22.2k = 11 0.002 0.02 0.2 2.2 22.2k = 12 0.0002 0.002 0.02 0.2 2.2 22.2


Zusammenfassung

Kombinatorik: Zusammenfassung 81

•∣∣(s1, . . . , sk) ∈ [n]k

∣∣ = nk

”Ziehen mit Zurucklegen, unter Beachtung der Reihenfolge“

•∣∣(s1, . . . , sk) ∈ [n]k : |s1, s2, . . . , sk| = k

∣∣ = n!(n−k)!

=: nk

”Ziehen ohne Zurucklegen, unter Beachtung der Reihenfolge“

•∣∣(s1, . . . , sk) ∈ [n]k : s1 < s2 < . . . < sk

∣∣ = n!k!(n−k)!

=(nk

)=(

nn−k

)”Ziehen ohne Zurucklegen, ohne Beachtung der Reihenfolge“

•∣∣(s1, . . . , sk) ∈ [n]k : s1 ≤ s2 ≤ . . . ≤ sk

∣∣ =(k+n−1

k

)”Ziehen mit Zurucklegen, ohne Beachtung der Reihenfolge“

•∣∣(s1, . . . , sk) ∈ Nk

0 : s1 + s2 + . . . + sk = n∣∣ =

(n+k−1

n

)•∣∣(s1, . . . , sk) ∈ Nk

0 : s1 + s2 + . . . + sk ≤ n∣∣ =

(n+kn

)•∣∣(s1, . . . , sk) ∈ [n]k : |s1, s2, . . . , sk| = n

∣∣ = n!Sk,n

mit Sn+1,k = Sn,k−1 + kSn,k, S0,0 = 1, Sn+1,0 = 0, Sn,n = 1

”Striling-Zahlen 2. Art: Anzahl Partitionen von [n] in k Klassen.“

•∣∣(s1, . . . , sk) ∈ Nk

0 : s1 + . . . + sk = n, s1 ≤ s2 ≤ . . . ≤ sk∣∣ = |Pn+k,k|

mit |Pn,k| = |Pn−1,k−1|+ |Pn−k,k−1|, |P0,0| = 1, |Pn+1,0 = 0|, |Pn,n| = 1.

”Anzahl Zahlpartitionen von n in k positive Summanden.“

Kombinatorik: Zusammenfassung 82

• |A1 ×A2 × . . .×An| =∏

i∈[n] |Ai|

”Produktregel“

•∣∣∣⊎i∈N0

Ai

∣∣∣ =∑

i∈N0|Ai|

”Summenregel“

•∣∣∣⋃i∈N0

Ai

∣∣∣ ≤∑i∈N0|Ai|.

”union bound“

•∣∣∣⋃i∈[n] Ai

∣∣∣ =∑

I⊆[n] : I 6=∅(−1)|I|+1∣∣⋂

i∈I Ai

∣∣”Siebformel“

• |A| = m |B|, falls es ein f : A→ B mit∣∣f−1(b)

∣∣ = m konstant gibt.

Documents

Kombinatorik - Theoretical Computer Science · Kombinatorik c Javier Esparza und Michael Luttenberger Chair for Foundations of Software Reliability and Theoretical Computer Science