04.12.2012
Kombinatorik
(vgl. S 42)
Grundprinzipien:
(1) Gleichheitsregel:
wenn für 2 endliche Mengen eine bijektive Abbildung f:A→B existiert, dann gilt |A| = |B|
(2) Summenregel: t
Sind S_1,S_2,... S_t paarweise disjunkte endliche Mengen und ist S = US (Vereinignung aller Mengen) dann gilt |S| = ∑ |S_i|
i=1
(3) Produktregel t
Sind S_1,...S_t endliche Mengen und S = S_1 x S__2 x S_t dann gilt |S| = |S_1| * |S_2| * ... *|S_t| = ρ|S_1|
i=1
⚡
Beispiel 1: Ist |M| = n, dann gilt |ρ(M)|=2^n
Beweis mit vollständiger Induktion nach n:
IA: n=0 M=∅ ρ(M)={∅}
|ρ(M)|=1=2^0
IS: n→n+1
Sei |M|=n+1 und a ein beliebig gewähltes Element aus M
ρ(M)={A|A⊆M}
={A⊆M|a∈A}∪{A⊆M|!∈A} |disjunkte Vereinigung
=S_1 =S_2
|ρ(M)|=|S_1|+|S_2| |Summenregel
S_2=ρ(M\{a}) |nach IV |S_2|=2^n
Behauptung: Es gibt bijektive Abbildung
f:S_1→S_2
A ⟼ A\{a}
A'u{a}↤|A'
|S_1|=|S_2| |Gleichheitsregel
=>|ρ(M)|=|S_1|+|S_2|=2^n+2^n=2*2^n=2^(n+1)
Beispiel2:
Bezeichne (M über k) der Menge aller k-elementigen Teilmenge von M
({a,b,c,d} über 2)={{a,b} {a,c},{a,d},{b,c},{b,d},{c,d}}
Sei |(M über k)| = (n über k) wobei n = |M|
(n über n)=1=(n über 0)
Satz: (n über k) =(n-1 über k-1)+(n-1 über k)
Sei n≥1 und k≤n , |M|=n und a∈M beliebig gewählt
A ⊆ M mit |A|=k
->1 a∈A
->2 a∉A
(M über k)=S_1 ∪ S_2
={A M| |A|=k und a∈A} ∪{A ⊆M| |A|=k und a A}
S_2=(M\{a} über k) |S_2|=(n-1 über k)
Behauptung: Es gibt eine Bijektion
f:S_1→\{a} über k-1)
Ă|⟼ A\{a}
A'u{a}<-| A'
=>|S_1|=(n-1 über k-1)
Summenregel: (n über k)=|(M über k)|=|S_1|+|S_2|=(n-1 über k-1)+(n-1 über k)
(4.) Grundprinzip Regel vom doppelten Abzählen.
Def.: eine Inzidenzstruktur ist eine (Inzidenz-)Relation I zwischen 2 endlichen Mengen A und B
Für alle aA und b€B
r(a)=|{y∈B|(a,y)∈I}| |Rang von a
r(b)=|{x∈A|(x,b)∈I}|
Regel vom doppelten Abzählen
Es gilt ∑r(a)=∑r(b)
Grund ∑r(a)=|I|=∑r(b)
Beispiel: A={1,2,3}, B={u,v,w}
I={(1,u),(2,v),(2,w),(3,u),(3,v)}
r(1)=1 r(2)=2 r(3)=2
r(u)=2 r(v=2 r(w)=1
Anwendungen:
Jede natürliche Zahl n hat Primzahlzerlegung
n=p_1*p_2*...p_k
Wie viele verschiedene Primfaktoren hat n?
p(n)
p(2)=p(3)=p(4)=p(5)=1
p(6)=2
p(10)=2
p(12)=2
p(30)=3...
Frage:∑p(n) (n=1-40) entweder p(1)+p(2)...+p(40)
oder doppeltes Abzählen
A={1,2,..,40}
B={2,3,5,7,11,13...,37}
I={(n,p)|pln} damit ist p(n)=r(n)
∑p(n) (n=1-40)=Σr(p) (p€B)
=[40/2]+[40/3]+[40/5]+[40/7]+[40/11]+[40/13]+[40/17]+[40/19]+[40/23]+[40/29]+[40/31]+[40/[37]
=20+13+8+5+3+3+2+2+1+1+1+1
=60
Inzidenrelaion als bipartiter Graph
(Bild)
Inzidenzrelation als Matrix
(Bild)
Fundamentale (???) Zählkoeffizienten
Was wollen wir abzählen?
M eine n-elementige Menge (n-Menge)
Potenzmenge ρ(M) 2
k-Teilmengen von M (M über k) (k-Kombinationen) (n über k) (Binomialkoeffizient)
k-Variationen von M ohne Wiederholung
(k-Teilmengen mit einer Reihenfolge) n^k
auch k-Permutationen von M
(volle) Permutationen von M n!
Reihung der Elemente von M
k-Partionen von M S_(n,k) |Stirling-Zahlen zweiter Art
(Zerlegung von M in k Blöcke)
k-Zahlpartitionen der Zahl n
(Zerlegung von n in Summe von k Summanden)
...
Anzahl der k-Partitionen (k-Variationen ohne Wiederholung) einer n-Menge M
M={a_1,a_2,...a_n}
k-permutatione hat Form b_1, b_2...,b_k
b_1€M paarweise verschieden
für b_1: n Möglichkeiten
für b_2: n-1 Möglichkeiten
für b_k: n-k+1 Möglichkeiten
=>Anzahl=n*(n-1)*(n-2)*...*(n-k+1)=n^k |k absteigende Faktoren |fallende Faktorielle
n^k =((n*(n-1)*(n-2)*...*(n-k+1))*(n-k))/(1*(n-k))
=n!/(n-k)!
6.12.2012
k-Permutationen einer n-Menge
=k-Variationen ohne Wdh.
=Folgen von k verschiedenen Elementen aus einer n-Menge
=Ziehung von k Objekten aus n Objekten(Urnenmodel) ohne Zurücklegen
Anzahl n^k= n(n-1)...(n-k+1)=(n!)/(n-k)!
(volle) Permutation einer n-Menge, ist eie bijektive Funktion f:M->M ist also eine n-Permutation einer n-Menge
Anzahl: n!
k-Kombination
=k-Untermenge einer n-Menge
Anzahl: (n über k)=|(M über k)| wobei |M|=n
Menge der k-Permutationen von M -> (M über k)*[Permutation einer k-Menge)
Anzahlen: n^k =(n über k)*k!
(n über k)=(n^k)/k!=(n!)/((n-k!)*k!) |Binomialkoeffizient
Anzahl der Tipps bei 6 aus 49
= (49*48*47*46*45(*3)*44)/(1*2*3*4*5*6)
k-Partitionen einer n-Menge
=Zerlegung von M in k Blöcke
Symbol für die Anzahl: S_(n,k) (Stirling-Zahlen zweiter Art)
S_(n,n)=1
S_(n,1)=1
S_(n,2)=2^(n-1)-1 |Übungsaufgabe
S_(n,n-1)=(n über 2) |ein spezieller Block besteht aus 2 Elementen von M, alle anderen sind einelementig
wichtig: k-Partitionen sind ungeordnete Objekte, d.h. die Reihenfolge, in der de Blöcke notiert werden is egal
Bsp: M={a,b,c,d,e} k=3 {{a,e},{b,c},{d}}={{c,b},{d},{a,e}}
Zahlpartitionen
ungeordnete Zahlpartitionen:
ungerade k-Zahlpartition der zahl n ist eine Zerlegung von n in k Summanden, die ≥1, wobei die Reihenfolge egal ist
Bsp: n=7 k=3
1+1+5=1+5+1=5+1+1
1+2+4
1+3+3
2+2+3
Darstellung mit aufsteigend sortierten Summanden möglich
Anzahl:P_(n,k) (symbolisch)
P_(7,3)=4
P_(n,n)=1
P_(n,1)=1
P_(n,n-1)=1 (nämlich 1+1+...+1+2)
P_(n,n-2)=2
P_(n,2)= n div 2 = |_n/2_|
geordnete k-Zahlpartitionen von n
=Zerlegung von n in k Summanden, ≥1, mit Berücksichtigung der Reihenfolge
Anzahl ist gleich (n-1 über k-1)
Beweisidee: n=1+1+1+...+1
k-Zahlpartition n=a_1+a_2+..a_k
=>Auswahl von k-1 Pluszeichen aus n-1
formaler Beweis:
Bijektion zwischen
Menge der k-Zahlpartitionen von n -> ({1,...,n-1} über k-1)
n=a_1+a_2+...+a_k |-> {a_1,a_1+a_2,a_1+a_2+a_3,...,a_1+a_2+...+a_(k-1)}
n=b_1+(b_2-b_1)+(b_3-b_2)+...+(b_(k-1)-b_(k-2))+(n-b_(k-1))<-|{b_1,b_2,b_3,...,b_(k-1)}
Variante: geordnete k-Zahlpartitionen von n wobei auch 0 als Summand zugelassen wird
5=0+0+5
=0+5+0
=1+2+2
usw.
n=a_1+a_2+a_k a_i≥0
n+k=(a_1+1)+(a_2+1)+..+(a_k+1) a'_i≥1
↓
=a'_1 a'_2 a'_k
Anzahl: ((n+k-1) über (k-1))
Abzählung von Funktionen
|N|=n |R|=r
F(N,R)=Menge aller Funktionen N->R
Inj(N,R)=Menge aller injektiven Funktionen N->R
Sur(N,R)=Menge aller surjektiven Funktionen N->R
Bij(N,R)=Menge aller bijektiven Funktionen N->R
|Bij(N,R)|={0 wenn n≠r, n! wenn n=r
|Inj(N,R)|=r^n wobei r^n=0 wenn n>r
|F(N,R)|=r^n
|Sur(N,R)|=r!*S_(n,r) Bijektion zwischen Sur(N,R) und geordneten r-Partition von N
Grund:f|->Partition von N, aber Zuordnung der Blöcke ist entscheidend
r^n=|F(N,R)|=∑ |Sur(N,A)|
A⊆R
(Klassifizierung nach Bild der Funktion),
r
=∑ (∑ Sur(N,A))=∑ ( ∑ k!S_(n,k))
k=0 A⊆R k=0 A⊆R
|A|=k |A|=k
r
=∑ ((r)nCr(k)) k! S_(n,k)
k=0
r r
=∑ (r^k /k! *k! S_n,k=∑ r^k*S_n,k
k=0 k=0
(Zusammenfassung aller Bilder Gleicher Größe)
11.12.2012
Zwölf Arten des Abzählens
n Bälle werden auf r Fächer verteilt
Varianten: Bälle unterscheidbar/nicht unterscheidbar
Fächer unterscheidbar/nicht unterscheidbar
Verteilung: beliebig
injektiv (höchstens 1 Ball pro Fach) n≤r
surjektiv (mind. ein Ball pro Fach) n≥r
bijektiv (genau ein Ball pro Fach) n=r
// (n)nCr(k) = n über k = Binomialkoeffizient
Bälle Fächer |beliebig |injektiv |Surjektiv |bijektiv
beide unterscheidbar |r^n |r^n |r!*S_n,r |n! falls n=r 0 sonst
nur Fächer unterscheidbar |(n+r-1)nCr(r-1) |(r)nCr(n) |(n-1)nCr(r-1)|1 oder 0
nur Bälle unterscheidbar |∑(k=0 bis r) S_(n,k)|1 falls n≤r, 0 sonst|S_(n,r) |1 oder 0
beides nicht unterscheidbar |∑(k=0 bis r) P_(n,r)|1 falls n≤r, 0 sonst|P_(n,r) |1 oder 0
Rekursionen
1) Binominalkoeffizienten
(n)nCr(k)=((n-1)nCr(k-1))+((n-1)nCr(k))
(n)nCr(n)=1
(n)nCr(0)=1
(0)nCr(k)=0 falls k>0
Pascalsches Dreieck
n\k|0|1|2 |3 |4|5
0 |1|0|0 |0 |0|0
1 |1|1|0 |0 |0|0
2 |1|2|1 |0 |0|0
3 |1|3|3 |1 |0|0
4 |1|4|6 |4 |1|0
5 |1|5|10|10|5|1
andere Darstellung:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
n
∑ (m)nCr(k)=(n+1)nCr(k+1) |für alle n,k
m=0
n
∑(m+k)nCr(k)=(n+m+1)nCr(n) |für alle m,n
k=0
Solche Identitäten können auf Polynome übertragen werden
x^k=x*(x-1)*(x-2)*...*(x-k+1)
x^2=x^2-x
x^3=x^3-3x^2+2x
(x)nCr(k)=(x^k)/k! |Polynom vom Grad k
(x)nCr(k)=(x-1)nCr(k-1)+(x-1)nCr(k)
Grad k = Grad k-1 + Grad k
Beispiel für k=2:
(x^2-x)/2!=x-1+((x-1)^2-(x-1))/2!
=(2x-2+x^2-2x+1-x+1)/2
// Polynomidentitäten sind nicht Klausurrelevant
Vandermonde-Identität
(x+y)nCr(n)=∑(k=0 bis n) (x)nCr(k)*(y)nCr(n-k)
Beweis für beliebige x,y€N:
|A|=x |B|=y A⋂B=∅
(x+y)nCr(n)=|(A∪B)nCr(n)|=Anzahl der n-Untermengen von A∪B
n
Summenregel (AuB)nCr(n)=U
{n-Untermengen von AuB und k Elemnten aus A}
k=0 aus A
Anzahl:(|A|)nCr(k)*(|B|)nCr(n-k)
Binomialsatz:
n
(x+y)^n=∑ (n)nCr(k)*(x^k)*y^(n-k)
k=0
Beweis mit vollständiger Induktion
alternative Idee
(x+y)^n=(x+y)*(x+y)*....*(x+y) |n-Mal
=x^n+(n)nCr(1)*(x^(n-1))*y+(n)nCr(2)*(x^(n-2))*(y^2)+...+(n)nCr(1)x*(y^(n-1))+y^n
(x+1)^n=∑(k=0 bis n) (n)nCr(k)*x^k
2^n=(1+1)^n
13.12.2012
Monotone Gitterwege
m|_|_|_|_|_|_|_|_|_|
5|_|_|_|_|_|_|_|_|_|
4|_|_|_|_|_|_|_|_|_|
3|_|_|_|_|_|_|_|_|_|
2|_|_|_|_|_|_|_|_|_|
1|_|_|_|_|_|_|_|_|_|
0|_|_|_|_|_|_|_|_|_|
0 1 2 3 4 5 6 7 k
Betrachte ganzzahliges Gitter
Ein Gitterweg ist monoton, wenn in jedem Schritt entweder die x- oder die y-Koordinate um 1 erhöht wird und die andere Koordinate gleich bleibt.
Anschaulich: Jeder Schritt geht um eine eine Einheit nach rechts oder nach oben.(in k-Richtung oder in m Richtung)
Anzahl der Wege:
Alle Wege haben Länge m+k
Alle Wege machen genau k Schritte von links anch rechts (horizontal)
Weg ist charakterisiert durch eine Auswahl von k horizontalen Schritten aus insgesamt m+k Schritten
=>(m+k)nCr(k)
Bsp:
k=9 m=7
grüner Weg: {2,3,6,7,9,10,11,13,16}
{1,3,4,5,6,7,10,11,15}|->roter Weg
Beobachtungen:
Man kann an Stelle der k horizontalen Kanten auch dei entsprechend m vertikalen Kanten auswählen
=>(m+k)nCr(k)=(m+k)nCr(m) m+k=n m=n-k
=>(n)nCr(k)=(n)nCr(n-k)
Menge der monotonen Gitterwege von (0,0) nach (k,m) kann partitioniert werden danach ob letzter Schritt horizontal ist oder vertikal ist:
(m+k)nCr(k)=(m+(k-1))nCr(k-1)+((m-1)+k)nCr(k)
=>(n)nCr(k)=(n-1)nCr(k-1)+(n-1)nCr(k)
Partitionierung der Wege von (0,0) nach (k,m) nach der Höhe, in der letzter horizontaler Schritt erfolgt
das kann sein 0,1,2,3...,m
(m+k)nCr(k)=(k-1)nCr(k-1)+(k-1+1)nCr(k-1)+(k-1+2)nCr(k-1)+..+(k-1+m)nCr(k-1)
=∑[j=0 bis m] (k-1+j)nCr(k-1)
Rekursion für Stirling-Zahlen zweiter Art
S_(n,k) =Anzahl der k-Partitionen einer n-Menge
S_(n,n)=S_(n,1)=1 für n>0
S_(n,n-1)=(n)nCr(2)
Sei |M|=n und a€M fix
P k-Partitionen von M:
Fall 1: {a} ist in Block von P
Fall 2: a ist in einem Block der Größe ≥2 von P enthalten
Wie viele Partitionen ergeben Fall 1? -> S_(n-1,k-1)
Wie viele Partitionen ergeben Fall 2? -> k*S_(n-1,k)
Rekursion: S_(n,k)=S_(n-1,k-1)+k*S_(n-1,k)
n\k|0|1|2 |3 |4 |5
0 | |
1 | |1
2 | |1|1
3 | |1|3 |1
4 | |1|7 |6 |1
5 | |1|15|25|10|1
Folgerung: S_(n,k)=1/k!* ∑[j=0 bis k] (-1)^(k-j)*(k)nCr(j)*j^n
Auflösung von Rekursionen
Gegeben: Rekursionsgelichung mit Anfangsbedingungen
a_n=f(a_n-1,a_n-2,...,a_n-k) a_0=C0 a_1=C1...a_k-1=Ck-1
Gesucht: Direkte Formel a_n=g(n)
naive Methode:
Anfangsteil ausrechnen, Lösung raten und verifizieren (Induktion)
Beispiel: Türme von Hanoi
t_n=2*t_(n-1)+1 t-1=1 t_2=3 t_3=7 t_4=15
Hypothese: t_n=2^n -1
Induktionsbeweis
IA: t_1=1=2^1 -1
IS: n->n+1
t_n+1=2*t_n+1=2*(2^n -1)= 2^(n+1)-2+1=2^(n+1)-1
Methode 1: Rekursionen der Form a_n=c*a_(n-1)+d a_0=C
c≠1 (für c=1 a_n=C+n*d)
a_n=d+c*a_(n-1)=d+c*(d+c*a_(n-2))=d+c*(d+c*(d+c*(...(d+c*a_0))))
=d+cd+c^2*d+c^3*d+...+c^(n-1)*d+c^n*C
=(d*∑[i=0 bis n-1] c^i)+c^n*C
=d*((1-c^n)\(1-c))+c^n*C
Methode 2:Lineare homogene Rekursionen vom Grad k
a_n=c_1*a_(n-1)+c_2*a_(n-2)+...+c_k*a_(n-k) +d
a_0=C_0 a_1=C_1 ...a_(k-1)=C_(k-1)
Idee:Angenommen es gäbe eine Lösung der Form
a_n=r^n für ein r€|R
=>r^n=c_1*r^(n-1)+c_2*r^(n-2)+...+c_k*r^(n-k) |:r^(n-k)
=>r^k-c1*r^k-1-c_2*r^k-2-...-c_k-1*r-c_k=0
=>r ist Nullstelle des polynoms
p(x)=x^k-c1*x^k-1-c2*x^k-2-...-c_k-1*x-c_k
Man kann zeigen
Wenn p(x) k verschiedene Nullstellen
r1,r2,...,rk
gibt es eine Lösung a_n=
Sonderzeichen: √, ∤, |, ≥, ≤, ∑, ⊕, ≠, , ○, ⚡, Σ, π, ✓, ∞, ρ
≡, ∈, ∉, ∀, ∃, ∅, ⋂, ⋃, ∪, ⊂, ⊃, ⊆, ⊇, ⋀, ⋁, ¬,
⇒, ⇔, ⟼, ↤, ☇, →, ↔, ↓,
Ā, Ē, Ū, Ō, Ω, ɸ, ω, τ, ℕ, ℤ,