Diskrete Strukturen

Ilja Bezrukov

SS2001 16. Mai 2001

2

Kapitel 1

Abzählungen, Rekursionen, erzeugende Funktionen

1.1 Elementare Zählprinzipien

Sei M eine endliche Menge |M|=Anzahl der Elemente von M |A| = n ∈ N = {1, 2, 3, …} ⇔ es gibt eine Bijektion α : A → {1, …, n} |A| = 0 ⇔ A = ∅

1.1.1 \underline{Lemma 1:}

a) |A| = |B| ⇔Es gibt eine Bijektion α : A → B

b) |A ˙∪B| = |A| + |B| A ˙∪B disjunkte Vereinigung, d.h. es gilt A ∩ B = ∅

c) |A × B| = |A| · |B| A × B = {(a, b)|a ∈ A, b ∈ B}

1.1.2 \underline{Folgerung:}

Abb.(A, B) = B^{A} =Menge aller Abbildungen von A nach B |B^{A}| = |B|^{|A|} \underline{Beweis:}|A| = n

|B| = m, A = \{a_{1}, …, a_{n}\}B^{A} → \underbrace{B × B × ⋯ × B}_{n}

f ↦ (f(a_{1}), f(a_{2}), f(a_{n})) ist eine Bijektion.

|B^{A}| = |B × B × ⋯ × B|Lemma 1c^{=}|B|^{n}

4KAPITEL 1. ABZÄHLUNGEN, REKURSIONEN, ERZEUGENDE FUNKTIONEN

1.1.3 \underline{Definition:}

f : A → A heisst Permutation von A, wenn f bijektiv. S_{n} = {σ : {1, …, n} → {1, …, n}|σ bijektiv} Heisst auch Symmetrische Gruppe von Grad n.

1.1.4 \underline{Lemma 2:}

|S_{n}| = n! = 1 · 2 ⋯ n (=Anzahl der Möglichkeiten, eine n-Menge A anzuordnen). Siehe LAI.

1.1.5 \underline{Satz 1:}

Die Anzahl der Teilmengen einer n-Menge A ist 2^{n}. |A| = n ⇒ |P (A)| = 2^{n} dabei ist |P (A) = {B|B ⊆ A}Potenzmenge von A. P (A) = {{1, 2}, {1}, {2}, ∅}. Beispiel: A = {1, 2}. \underline{Beweis:} P (A) → \{0, 1\}^{A}

B → χ_{b} characteristische Funktion von B, definiert durch χ_{B}(x) = \{ \begin{matrix}1 & fürx ∈ B \\ 0 & sonst \end{matrix}

ist Bijektion. B = {x ∈ A|χ_{B}(x) = 1}|P (A)| = ||{0, 1}^{A}| = 2^{|A|}.

1.1.6 Definition:

P_{k}(A) = \binom{A}{k} =Menge aller k-Teilmengen von A. = \{B ⊆ A||B| = k\}

\underline{Bem:} P (A) = ˙ ⋃{n \atop k=0}P_{k}(A) |A| = n Also nach Lemma 1 ist |P (A)| = ∑_{k=0}^{n} |P_{k}(A)|

1.1.7 \underline{Lemma 3}

|P_{k}(A)| = | \binom{A}{k} | = \binom{n}{k} = \frac{n·(n−1)···(n−k+1)}{k!} falls |A| = n. \underline{Beweis:} B = \{b_{1}, …, b_{k}\}, |b| = k, b_{i} ≠ b_{j}füri ≠ j, b_{i} ∈ A |{(b_{1}, …, b_{k})|b_{i} ∈ A, b_{i} ≠ b_{j}füri ≠ j}| = n(n − 1) ⋯ (n − k + 1). Es gibt k! Anordnungen von {b_{1}, …, b_{k}}. \underline{2.Beweis von Satz 1(Binomialsatz):} |A| = n |P (A)| = ∑_{k=0}^{n} \binom{n}{k} = ∑_{k=0}^{n} \binom{n}{k} 1^{k} · 1^{n−k} = (1 + 1)^{n}.

1.1.8 \underline{Satz 2:}

a) Pascaldreieck \binom{n}{k} = \binom{n−1}{k} + \binom{n−1}{k−1} fr k ≥ 1, n ≥ k . \underline{Beweis:} n ≥ 1, |A| = n, \binom{n}{k} =Anzahl der k-Teilmengen von A. b ∈ A

\binom{A}{k} = \{X ⊆ A|b ∉ X\} ∪ \underbrace{\{X ⊆ A||X| = k, b ∈ X\}}_{M}

= {A\\{b\} \atop k} ) ˙∪M.M →( {A\\{b\} \atop k−1} )X → X\\{b\} sind bijektiv.

| \binom{A}{k} | = \binom{n−1}{k} + \binom{n−1}{k−1}

b) Vandermondsche Identität: \binom{n+m}{k} = ∑_{l=0}^{k} \binom{n}{l} · \binom{m}{k−l}. \underline{Beweis:}|A| = m + n, |B| = m, |C| = n, A = B ˙∪C | \binom{A}{k}_{l} = \{X ⊆ A||X| = k, |x ∩ B| = l\} l = 0, 1, …, k | \binom{A}{k} = ˙⋃_{l=0}^{k}| \binom{A}{k}_{l}

| \binom{m+n}{k} = || \binom{A}{k} | = ∑_{l=0}^{k} | \underbrace{| \binom{A}{k}_{l} |}_{\binom{m}{l}\binom{n}{k−l}}

1.1.9 \underline{Lemma 4 :}

a) Doppeltes Abzählen Ist R ⊆ M × N, so ist |R| = ∑ |{b ∈ N|(a, b) ∈ R}|, a ∈ M = ∑_{b∈N} |{a ∈ M|(a, b) ∈ R}|

b) Schubfachprinzip |M| > |N| Ist f : M → N, so ist f nicht injektiv, d.h. ∃b ∈ N|f^{−1}(b) = |{a ∈ M, f(a) = b}| > 1v

c) Inklusion-Exklusionsprinzip A_{1}, … A_{n} ⊆ M | ⋃_{i=1}^{n} A_{i}| = ∑_{i=1}^{n} |A_{i}| − ∑_{i_{1}<i_{2}} |A_{i_{1}} ∩ A_{i_{2}}| + ∑_{···} |A_{i_{1}} ∩ A_{i_{2}} ∩ A_{i_{3}}| = ∑_{j=1}^{n}(−1)^{j−1} ∑_{i_{1}<...<i_{j}≤n} |A_{i_{1}} ∩ … ∩ A_{i_{j}}

(\underline{Beweis:}) / (A ⊆ M)

χ_{A} : m → {0, 1}

x ↦ \{ \begin{matrix}1 & wennx ∈ A \\ 0 & sonst \end{matrix} |A| = ∑_{x∈M} χ_{A}(x)(*)χ_{A_{1}∪···∪a_{n}}(x) = ∑_{j=1}^{n} ∑_{1≤i_{1}<...<i_{j}≤n} χ_{A_{1}∪···∪a_{n}}(x)

Daraus folgt die Beh. durch Summation über M ∑_{x∈M} :

(a) Ist x ∈ A_{1} ∪ … ∪ A_{n} so ist \begin{matrix}L.S(∗) = 0 \\ R.S(∗) = 0 \end{matrix}

(b) x ∈ A_{1} ∪ … ∪ A_{n}so istL.S(∗) = 1 x liege in genau k(≥ 1) Teilmengen A_{1}, …, A_{n}, x ∈ A_{j_{1}} ∩ … ∩ A_{j_{k}}, j_{1} < … < j_{k} dann ist χ_{A_{1}∪···∪a_{n}}(x) = 1 ⇔ {i_{1}, …, ı_{j}} ⊆ {j_{1}, …, j_{k}}

R.S(∗) = ∑_{j=1}^{n}(−1)^{j−1} \binom{k}{j} = 1 − \underbrace{∑_{j=0}^{k}(−1)^{j} \binom{k}{j} = 1}_{(1−1)^{k}} .

1.2 Partitionen

1.2.1 \underline{Definition:}

Eine Partition P von M (Menge) ist eine Zerlegung von M in eine Vereinigung von disjunkten, nichtleeren Teilmengen(Blöcke genannt), genauer P = {A_{1}, …, A_{k}} Partition von M, wenn M = A_{1} ˙∪ … ˙∪A_{k} und A_{i} ≠ ∅ für i = 1, …, k P art_{K}(M) := {P |P ist Partition vom M |P | = k} S_{n,k} = |P art_{K}(M)|falls |M| = n Stirling Zahlen 2.Art n, k ≥ 0 S_{0,0} = 1 \underline{Beispiele:} S_{n,0} = 0, n ≥ 1S_{n,1} = 1, n ≥ 1S_{n,n} = 1S_{n,n−1} = \binom{n}{2}

1.2.2 \underline{Satz 1:}

Es gilt für 1 ≤ k ≤ nS_{n,k} = S_{n−1,k−1} + k · S_{n−1,k}

\underline{Beweis:} a ∈ M, |M| = n ≥ 1 P art_{k}M = X_{1} ⊎ X_{2}, wobei X_{1} = {P ∈ P art_{k}M|{a} ∉P } X_{2} = {P ∈ P art_{k}M|{a} ∈ P } X_{2} = {P = {{a}, B_{1}, …, B_{k−1}}|{B_{1}, … B_{k−1}} ∈ P art_{k−1}M\{a}} |X_{2}| = S_{n−1,k−1} Ist P ∈ X_{1} dann erhält man durch löschen von a eine Partition {B_{1}, …, B_{k}} von M\{a} Umgekehrt erhalten wir zu jedem {B_{1}, … B_{k}} ∈ P art_{k}M\{a} genau k verschiedene Partitionen aus X_{1}, nämlich {{a}∪B_{1}, B_{2}, … B_{k}}, …, {B_{1}, B_{2}, … B_{k}∪ {a}} |X_{1}| = k · S_{n−1,k}.

\underline{Bemerkung:}

1. { Partitionen von M } ↔ { Äquivalenzrelationen auf M }

2. Ist f : M → N eine surjektive Abb f^{−1}(b) = {a ∈ M|f(a) = b} ≠ ∅, b ∈ M M = ⋃_{b∈N} f^{−1}(b) P_{f} = {f^{−1}(b)|b ∈ N} ∈ P art_{|N|}M

1.2.3 \underline{Satz 2:}

Ist |M| = m, |N| = n

1. |Abb(M, N) = |N^{M}| = n^{m} 2. | \underbrace{Inj(M, N)}_{Injektive Abb.} | = n\underline{m} = n(n − 1) ⋯ (n − m + 1) n nach m fallend

3. | \underbrace{Surj(M, N)}_{Surjektive Abb.} | = n!S_{m,n}

\underline{Beweis:}

1. siehe 1

2. M = {a_{1}, …, a_{m}} Jede Abb. f : M → N ist gegeben durch f(a_{1}) = b_{1} ∈ N … f(a_{m}) = b_{m} ∈ N f injektiv ⇔ b_{i} ≠ b_{j} für i ≠ j für b_{1} gibt es n Möglichkeiten b_{1} ∈ N für b_{2} gibt es n-1 Möglichkeiten b_{2} ∈ N\{b_{1}} ⋯ für b_{m} gibt es n-m+1 Möglichkeiten b_{m} ∈ N\{b_{1}, … b_{m−1}}

3. f : M → N surjektiv P_{=}{f^{−1}(b)|b ∈ N} ∈ P art_{n}M = {A_{1}, … A_{n}} P_{f} = P_{g} ⇔ g = σ ∘ f mit σ ∈ Sym N |Surj(M, N)| = S_{m,n} · n!

1.2.4 \underline{Satz 3:}

n^{m} = ∑_{k=0}^{n} n\underline{k}S_{m,k} m, n ∈ N

\underline{Beweis:} Abb(M, N) = ⋃_{A⊆N} Surj(M, A) f kann man auffasen als surj. Abb. f : M → Bild(f) = {f(a) ∈ N|a ∈ M} ⊆ N n^{m} = |Abb(M, N)| = ∑_{A⊆N} |surj(M, A)| = ∑_{k=0}^{n} ∑_{A∈\binom{N}{k}} |Surj(M, A)| = ∑_{k=0}^{n} k! · S_{m,k}

= ∑_{k=0}^{n} \frac{n\underline{k}}{k!} S_{m,k}

1.3 Permutationen

S_{n} = Sym(\underline{n}) = \{σ : \{1, …, n\} → \{1, …, n\}|σ bijektiv\} |S_{n}| = n! jedes σ ∈ S_{n} kann durch eine Wertetabelle angegeben werden:

σ = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 4 & 3 & 7 & 2 & 9 & 1 & 6 & 8 & 5 \end{matrix} )

1.3.1 \underline{Bemerkung:}

(S_{n}, ·) ist eine Gruppe. σ_{1} ∘ σ_{2} : {1, …, n} → {1, …, n}, x ↦ σ_{1}(σ_{2}(x))

1.3.2 \underline{Definition:}

Ein k-Zyklus (i_{1}, …, i_{k}) = σ ∈ S_{n}, {i_{1}, …, i_{k}} ∈ {1, …, n} ist eine Permutation mit σ(i_{1}) = i_{2}σ(i_{2}) = i_{3} ⋯ σ(i_{k−1}) = i_{k}σ(i_{k}) = i_{1} und σ(i) = i für i ∉{i_{1}, …, i_{k}}

1.3.3 \underline{Beispiel:}

σ wie oben σ = (1 4 2 3 7 6) ∘ (5 9) ∘ (8)

1.3.4 \underline{Bemerkung:}

Jedes σ ∈ S_{n} lässt sich als Produkt von Zyklen schreiben. \underline{Beispiel:} S_{3} = \{(1)(2)(3), (1)(2 3), (2), (1 3), (3)(1 2), (1 2 3), (1 3 2)\}

1.3.5 \underline{Definition:}

Die Stirlingzahlen s_{n,k} 1.Art geben die Anzahl der Permutationen von {1, …, n} an, die genau k (disjunkte) Zyklen haben.

1.3.6 \underline{Definition:}

Ein (r) Zyklus ζ = (i_{1}, …, i_{r}) ist eine Permutation ζ ∈ S_{n} mit Ziffernmenge Z(ζ) = {i_{1}, …, i_{r}} mit |Z(ζ) = r P er_{k}(\underline{n}) = \{σ ∈ S_{n}|σ = ζ_{1} ∘ … ∘ ζ_{k} mit Z(ζ_{1}) ⊎ … ⊎ Z(ζ_{k}) = \{1, …, n\} = n\}.

1.3.7 \underline{Bemerkung:}

a) (i_{1} … i_{r}) = (i_{2} … i_{r} i_{1}) = (i_{r} i_{1} … i_{r−1})

b) ζ_{1}, ζ_{2} disjunkt, d.h. Z(ζ_{1}) ∩ Z(ζ_{2}) = ∅ ⇒ ζ_{1} ∘ ζ_{2} = ζ_{2} ∘ ζ_{1}. z.B. (1 2) ∘ (3 4) = (3 4) ∘ (1 2)

\underbrace{(1 2)(2 3)}_{(1 2 3)} ≠ \underbrace{(2 3)(1 2)}_{(1 3 2)}

1.3.8 \underline{Definition:}

s_{n,k} = |P erm_{k}(\underline{n})| n, k ≥ 1 s_{0,0} = 1 s_{0,k} = 0, k > 0 Stirling-Zahlen 1. Art.

1.3.9 \underline{Lemma 1:}

a) s_{n,k} = 0 für k > n

b) s_{n,n} = 1 für n ∈ N_{0}P erm_{n}\underline{n} = \{(1) ∘ (2) ∘ ⋯ ∘ (n) = id\} c) s_{n,1} = (n − 1)!

P erm_{1}(\underline{n}) = \{(n i_{2} … i_{n})| |\{i_{2}, …, ı_{n}\}| = n − 1\} | | = (n − 1)!

1.3.10 \underline{Satz 1}

für n, k ∈ N gilt s_{n,k} = s_{n−1,k−1} + (n − 1)s_{n−1,k} \underline{Beweis:} X = P erm_{k}(\underline{n}) = X_{1} ⊎ X_{2} X_{1} = {σ ∈ X|σ(n) = n} = {σ = (n) ∘ ζ_{1} ∘ … ∘ ζ_{k−1}|ζ_{1} ∘ … ∘ ζ_{k−1} ∈ P erm_{k−1}(\underline{n − 1})\} |X_{1}| = s_{n−1,k−1} X_{2} = {σ ∈ X|σ(n) ≠ n} Jedes σ ∈ X_{2} liefert durch Streichen von n eine Permutation

τ : \underbrace{(i_{1} … i_{r})(i_{r_{1}+1} … i_{r_{1}+r_{2}}) ⋯ (ı_{r_{1}+r_{k−1}+1} i_{n−1})}_{k Zyklen der Länge r_{1},r_{2},...,r_{k}∈P erm_{k}(\underline{n−1})}

Umgekehrt liefert jedes solches τ ∈ P erm_{k}(\underline{n − 1}) genau n-1 Elemente aus X_{2} indem wir vor i_{1}, i_{2}, ı_{n−1} n einfügen: (n i_{1} … i_{r})(i_{r_{1}+1} … i_{r_{1}+r_{2}}) ⋯ (ı_{r_{1}+r_{k−1}+1} i_{n−1}) (i_{1} n … i_{r})(i_{r_{1}+1} … i_{r_{1}+r_{2}}) ⋯ (ı_{r_{1}+r_{k−1}+1} i_{n−1}) ⋯ |X_{2}| = (n − 1) |P erm_{k}(\underline{n − 1})| = (n − 1)s_{n−1,k}

1.4 Formale Potenzreihen(erzeugende Funktionen)

Bei der Komplexitätsanalyse von Algorhytmen entstehen oft Rekursionsgleichungen, z.B. a_{n} = a_{n−1} + a_{n−2} Um solche Rekursionen explizit zu lösen, brauchen wir erzeugende Funktionen. (a_{n})_{n∈N_{0}} = (a_{0}, a_{1}, a_{2}, …) ∑_{n=0}^{∞} a_{n}x^{n} formaler Ausdruck, x unbestimmte

1.4.1 \underline{Definition:}

Sei K ein Körper, z.B. K = Q, R, C, F_{2} K[[x]] := {∑_{n=0}^{∞} a_{n}x^{n}|a_{n} ∈ K } und ∑_{k=0}^{∞} a_{n}x^{n} = (a_{n})_{n∈N_{0}}x^{n} := (a_{j})_{j∈N_{0}}

mit a_{j} = \{ \begin{matrix}1 & fürj = n \\ 0 & sonst \end{matrix}

∑_{n=m}^{∞} a_{n}x^{n} = (b_{j})_{j∈N_{0}} mit b_{j} = \{ \begin{matrix}a_{j} & fürj ≥ n \\ 0 & sonst \end{matrix}

∑_{n=0}^{∞} a_{k}x^{kn} = (b_{j})_{j∈N_{0}} mit b_{j} = \{ \begin{matrix}0 & wenn j ≠ kn \\ a_{n} & wenn j = kn \end{matrix}

1.4.2 \underline{Satz 1:}

Definiert man

1. ∑_{n=0}^{∞} a_{n}x^{n} + ∑_{n=0}^{∞} b_{n}x^{n} := ∑_{n=0}^{∞}(a_{n}) + b_{n})x^{n}

2. für a ∈ K a · ∑_{n=0}^{∞} a_{n}x^{n} := ∑_{n=0}^{∞}(a · a_{n})x^{n}

So wird K[[x]] ein K-Vektorraum. \underline{Beweis:} Siehe LAI :-).

1.4.3 \underline{Satz 2:}

Definert man, (zusätzlich zu +, siehe Satz 1) (∑_{i=0}^{∞} a_{i}x^{i})·(∑_{j=0}^{∞} a_{j}x^{j}) := ∑_{k=0}^{∞} (∑_{i+j=k} a_{i}b_{j}) x^{k} = ∑_{k=0}^{∞} (∑_{i=0}^{k} a_{i}b_{k−i}) x^{k} so ist (K[[x]], +, ·) ein kommutatiover Ring mit Eins, d.h.

(A1) (A + B) + C = A + (B + C)∗
(A2) A + B = B + A∗
(A3) Es gibt 0 = (0 · x^{0}) mit 0 + A = A∀A ∈ K[[x]]
(A4) zu A ∈ K[[x]]∃ − A ∈ K[[x]] mit A + −A = 0
(M) (A · B) · C = A · (B · C)∗
(Komm) A · B = B · A∗
(Eins) Es gilt 1 ∈ K[[x]] mit 1 · A = A ∀A ∈ K[[x]]
(D) Es gilt A · (B + C) = A · B + A · C∗

∗ : ∀A, B, C ∈ K[[x]] Einselement ist 1 · x^{0} = 1

1.4.4 \underline{Lemma 1:}

x^{m} · ∑_{n=0}^{∞} a_{n}x^{n} = ∑_{n=m}^{∞} a_{n−m}x^{n} In der Folgesprache bedeutet dies x^{m} · (a_{0}, a_{1}, …) = (0, 0, 0, …, 0, a_{1}, a_{2}, …) Multiplikation mit x^{m} bewirkt Verschieben der Folge (a_{n})_{n∈_{0}} um m Stellen nach rechts.

1.4.5 \underline{Folgerung:}

x^{m} · x^{n} = x^{m+n}

1.4.6 \underline{Beispiel:}

(1 − cx) · ∑_{i=0}^{∞} c^{i}x^{i} für c ∈ K = ∑_{i=0}^{∞} c^{i}x^{i} − cx · ∑_{i=0}^{∞} c^{i}x^{i} = ∑_{i=0}^{∞} c^{i}x^{i} − c · ∑_{i=1}^{∞} c^{i−1}x^{i} = ∑_{i=0}^{∞} c^{i}x^{i} − ∑_{i=1}^{∞} c^{i}x^{i} = c^{0}x^{0} + ∑_{i=1}^{∞} c^{i}x^{i} − ∑_{i=1}^{∞} c^{i}x^{i} = 1

1.4.7 Bem. und Definition:

Ist in einem komm Ring mit eins A·B = 1 so ist B durch A eindeutig bestimmt und wird mit B = A^{−1} = \frac{1}{A} bezeichnet. [also A = B^{−}1 = \frac{1}{B} ]und A (und auch B) heisst invertierbar. \underline{Beweis:} Ist A · B = 1 und A · C = 1, so folgt C = C · 1 = C(A · B) =

(\underbrace{A · C}_{=1}) · B = B

\underline{Beispiele:} In Z sind nur 1 und -1 invertierbar.

1.4.8 \underline{Folgerung:}

In K[[x]] ist ∑_{i=0}^{∞} c^{i}x^{i} für c ∈ K invertierbar und

∑_{i=0}^{∞} c^{i}x^{i} = \frac{1}{1−cx}

[Ist \frac{1}{1−cx} eine Formale Potenzreihe? Gegenfrage: ist \frac{1}{0,5} ∈ Z? ]

1.4.9 \underline{Beispiel:}

Code mit variabler Wortlänge (Komprimieren von Daten) Bu = {a, b, c} Zi = {0, 1} W_{k} = {Folgen aus 0 < i < k Buchstaben gefolgt von k − i Ziffern }Co_{n} = ⋃_{k=2}^{n} W_{k} z.B.aa1|bc0001|ac1|

w_{k} = |W_{k}| = ∑_{i=1}^{k−1} 3^{i}2^{k−i} = \underbrace{∑_{i=o}^{k−1} 3^{i}2^{k−i}}_{c_{k}} −2^{k} − 3^{k}

\underline{Beh:} c_{k} = 3^{k+1} − 2^{k+1} c · ∑_{k=0}^{∞} c_{k}x^{k} = (∑_{i=0}^{∞} 3^{i}x^{i})(∑_{j=0}^{∞} 2^{j}x^{j})

Folg.1^{=} \frac{1}{1−3x} · \frac{1}{1−2x} = \frac{1}{(1−3x)(1−2x)}

\underline{Ansatz:} = \frac{α}{1−3x)} + \frac{β}{(1−2x)} = \frac{α(1−2x)+β(1−3x)}{(1−3x)(1−2x)} α(1 − 2x) + β(1 − 3x) = 1 β = −2, α = 3 c = ∑_{k=0}^{∞} c_{k}x^{k} = \frac{3}{(1−3x)} − \frac{2}{(1−2x)} c = ∑_{k=0}^{∞} c_{k}x^{k} = 3 · ∑_{i=0}^{∞} 3^{i}x^{i} − 2 · ∑_{i=0}^{∞} 2^{i}x^{i}

= ∑_{i=0}^{∞}(\underbrace{3^{i+1} − 2^{i+1}}_{c_{i}})x^{i}

1.4.10 \underline{Satz 3:}

Genau dann ist A = ∑_{n=0}^{infty} a_{n}x^{n} ∈ K[[x]] invertierbar, wenn a_{0} ≠ 0 ist. \underline{Beweis:} A ist invertierbar⇔ ∃ B = ∑_{i=0}^{∞} b_{i}x^{i} mit A · B = 1

∑_{k=0}^{∞} (∑_{i=0}^{k} a_{i}b_{k−i}) x^{k} = 1 ⇔ ∑_{i=0}^{k} a_{i}b_{k−i} = \{ \begin{matrix}1 & fürk = 0 \\ 0 & sonst \end{matrix}

\begin{matrix}⇔ a_{0}b_{0} = 1 & k = 0 \\ a_{1}b_{0} + a_{0}b_{1} = 0 & k = 1 \\ a_{2}b_{0} + a_{1}b_{1} + a_{0}b_{2} = 0 & k = 2 \\ ⋮ & ⋮ \end{matrix}

Ist B invertierbar, so muss a_{0} ≠ 0 sein sonst ist die Gleichung für k = 0 nicht erfüllbar. Umgekehrt ist a_{0} ≠ 0, so definiere b_{0} = a_{0}^{−1} ∈ K und b_{n} = \frac{1}{a_{0}} · (−a_{1}b_{n−1} − ⋯ − a_{n}b_{0}) rekursiv.

K[[x]] = {∑_{n=0}^{∞} a_{n}x^{n}|a_{n} ∈ K} Formale Potenzreihen K[x] = {∑_{n=0}^{∞} a_{n}x^{n}|a_{n} ∈ K und a_{n} ≠ 0 nur für endl.viele n } = {∑_{n=0}^{r} a_{n}x^{n}|a_{n} ∈ K, r ∈ N_{0}} Polynomring

• zu K[x] gibt es einen Einsetzungshomomorphismus, ist A ∈ K[[x]], so kann man in A im Allgemeinen nichts einsetzen.

• In K[x] sind nur die Polynome vom Grad=0 invertierbar.

1.4.11 \underline{Satz 3:}

A = ∑_{n=0}^{∞} a_{n}x^{n} ∈ K[[x]] ist invertierbar genau dann, wenn a_{0} ≠ 0 ist.

(∑_{n=0}^{∞} a_{n}x^{n}) · (∑_{n=0}^{∞} b − nx^{n}) = ∑_{n=0}^{∞} \underbrace{(∑_{i=0}^{n} a_{i}b_{n−i})}_{=1=1x^{0}⇔δ_{n,0}x^{n}}

Dann ist (b_{0}, b_{1}, b_{2}, …) Lösung des folgendes Gleichungssystems:

a_{0}x_{0} = 1
a_{1}x_{0} + a_{0}x_{1} = 0
a_{2}x_{0} + a_{1}x_{1} + a_{0}x_{2} = 0

Lösbar ⇔ a_{0} ≠ 0

1.4.12 \underline{Beispiel:}

a_{0} = 1 a_{1} = −c ∈ K a_{2} = a_{3} = … = 0

A = 1 − cx
x_{0} = 1
−cx_{0} + x_{1} = 1
−cx_{1} + x_{2} = 0
x_{1} = c
x_{2} = cx_{1} = c^{2}
x_{n} = c^{n}

\frac{1}{1−cx} = ∑_{n=0}^{∞} c^{n}x^{n} geometrische Reihe (∑_{n=0}^{∞} c^{n}x^{n})^{−1} = (1 − cx)

1.4.13 \underline{Beispiel:}

(∑_{n=0}^{∞} c^{n}x^{n})^{2} = ∑_{n=0}^{∞} (∑_{i=0}^{n} c^{i} · c^{n−i}) x^{n}

= ∑_{n=0}^{∞}(n + 1)c^{n} · x^{n}

(\frac{1}{(1 − cx)})^{2} = \frac{1}{(1 − cx)^{2}}

1.4.14 \underline{Folgerung:}

\frac{1}{(1 − cx)^{2}} = ∑_{n=0}^{∞}(n + 1)c^{n}x^{n}

allgemeiner \frac{1}{(1 − cx)^{m}} = ∑_{n=0}^{∞} \binom{n + m − 1}{m − 1} c^{n}x^{n}

1.4.15 \underline{Definition:}

Die Abbildung

D : K[[x]] → K[[x]]
∑_{n=0}^{∞} a_{n}x^{n} ↦ ∑_{n=0}^{∞}(n + 1)a_{n+1}x^{n}

heisst formale Ableitung

1.4.16 \underline{Lemma 1:}

D : K[[x]] → K[[x]] ist k-linear und es gilt:

a) D(x^{n}) = nx^{n−1}

b) D(A) = A · D(B) + B · D(A)

1.4.17 \underline{Folgerung:}

Ist A ∈ K[[x]] invertierbar, so ist D(A^{−1}) = −\frac{D(A)}{A^{2}} \underline{Beweis:}

A · A^{−1} = 1  D(1) = 0
0 = D(A · A^{−1} = A · D(A^{−1}) + D(A) · A^{−1} nach Lemma 1.b
−D(A) · A^{−1} = D(A^{−1}) · A
1.4.18 \underline{Beispiel:}

A = 1 − cx ∈ K[[x]]
A^{−1} = ∑_{n=0}^{∞} c^{n}x^{n}

D(A^{−1}) = ∑_{n=0}^{∞}(n + 1)c^{n+1}x^{n}  D(A) = −c
Folg.^{=} −\frac{D(A)}{A^{2}} = \frac{c}{(1 − cx)^{2}}  c ≠ 0 O.b.d.A.
\frac{1}{(1 − cx)^{2}} = ∑_{n=0}^{∞}(n + 1)c^{n}x^{n}

neuer Beweis der Folgerung

1.5 Lösen von Rekursionsgleichungen

1.5.1 \underline{Beispiel:}

Die Fibonacci-Zahlen F_{n} sind (für n ∈_{0}) so definert:

F_{0} = 0 F_{1} = 1
(*)  F_{n} = F_{n−1} + F_{n−2}  ∀n ≥ 2

z.B F_{2} = 1 F_{3} = 2 F_{4} = 3 F_{5} = 5 Sei

F = F (x) = ∑_{n=0}^{∞} F_{n}x^{n}

= F_{0}x^{0} + F_{1}x + ∑_{n=2}^{∞} F_{n}x^{n}  benutze (*)

= F_{0}x^{0} + F_{1}x + ∑_{n=2}^{∞}(F_{n−1} + F_{n−2}x^{n}

1.5. LÖSEN VON REKURSIONSGLEICHUNGEN 15

= F_{0}x^{0} + f_{1}x + ∑_{n=2}^{∞} F_{n−1}x^{n} + ∑_{n=2}^{∞} F_{n−2}x^{n}
= F_{0}x^{0} + F_{1}x + x · ∑_{n=1}^{∞} F_{n}x^{n} + x^{2} · \underbrace{∑_{n=0}^{∞} F_{n}x^{n}}_{F}
= F_{0}x^{0} + F_{1}x + xF + x^{2}F − xF_{0}x^{0}
F = x + xF + x^{2}F
F (1 − x − x^{2}) = x
F = \frac{x}{1 − x − x^{2}}

suche α, β ∈ K und a, b ∈ K so dass \frac{x}{1−x−x^{2}} = \frac{a}{1−αx} + \frac{b}{1−βx}

1.5.2 \underline{Satz 1:} Partialbruchzerlegung

K seie ein Körper

g = (1 − α_{1}x)^{m_{1}} · · · · · (1 − α_{r}x)^{m_{r}}  ∈ K[x] α_{i} ≠ 0∀i
f ∈ K[x]Grad f < Grad g
Dann gibt es f_{i} ∈ K[x] Grad f_{i} < m_{i}
mit \frac{f}{g} = \frac{f_{i}}{(1 − α_{1}x)}m_{1} + ⋯ + \frac{f_{r}}{(1 − α_{r}x)}m_{r}
\frac{f_{i}}{(1 − α_{i}x)^{m_{i}}} = \frac{a_{i_{1}}}{1 − α_{i}x)} + \frac{a_{i_{2}}}{(1 − α_{i}x)^{2}} + ⋯ + \frac{a_{m_{i}}}{(1 − α_{i}x)^{m_{i}}}
1.5.3 \underline{Bemerkung:}

Ist g wie in Satz 1, so sind die α_{i}^{−1} Nullstellen von g.

1.5.4 \underline{Definition:}

Ist g = ∑_{i=0}^{n} a_{i}x^{i}mit a_{n} ≠ 0,so sei g^{R} = ∑_{i=0}^{n} a_{n−i}x^{i}

das reflektierte Polynom

\underline{Beispiel:} 1 + 2x + 3x^{2} g^{R} = x^{2} + 2x + 3

1.5.5 \underline{Lemma 1:}

es gilt g(α) = 0 mit α ≠ 0 ⇔ g^{R}(α^{−1}) = 0 \underline{Beweis:} Sei α ≠ 0 in K

0 = g(α) = ∑_{i=0}^{n} a_{i} · α^{i} ⇒ 0 = α^{−n}g(α)

= ∑_{i=0}^{n} a_{i} · α^{i−n}

⇔ 0 = ∑_{j=0}^{n} a_{n−j}α^{−j}  j = n − i, i = n − j
⇔  g^{R}(α^{−1}) = 0
1.5.6 \underline{Bemerkung:}
g^{R}(x) = x^{n}g(x^{−1})

1.5.7 \underline{Satz 2:} Fundamentalsatz der Algebra

Ist g = ∑_{i=0}^{n} a_{i}x^{i} ∈ C[x] a_{n} ≠ 0

so gibt es α_{1}, … α_{n} ∈ C mit

g = a_{n}(x − α_{1}) ⋯ (x − α_{n})
1.5.8 \underline{Folgerung:}

Ist f = ∑_{i=0}^{n} a_{i}x^{i} ∈ C und a_{n} ≠ 0, a_{0} ≠ 0

so gibt es α_{1}, …, α_{n} mit

f = a_{0}(1 − α_{1}x) ⋯ (1 − α_{n}x)

denn nach Satz 2 gilt

f^{R} = a_{0}(x − α_{1}) ⋯ (x − α_{n})
f = (f^{R})^{R} = x^{n}(1/x − α_{1}) ⋯ (1/x − α_{n})
= (1 − α_{1}x) ⋯ (1 − α_{n}x)

Fortsetzung des Fibonacci-Beispiels

F = \frac{1}{1 − x − x^{2}} = \frac{f}{g}
g^{R} = x^{2} − x − 1 = (x − α_{1})(x − α_{2})
α_{1} = \frac{1 + \sqrt{5}}{2}  α_{2} = \frac{1 − \sqrt{5}}{2}
g = (1 − α_{1}x)(1 − α_{2}x)
\frac{f}{g} = \frac{x}{1 − x − x^{2}} =

1.5.9 Verfahren zum Lösen von linearen Rekursionen

(mit konstanten Koeffizienten)

Gegeben: a_{n} = c_{1}a_{n−1} + ⋯ + c_{k}a_{n−k} n ≥ k

mit gegebenen c_{i} ∈ C

und Anfangsbed. a_{i} = b_{i} für i = 0, 1, …, k − 1 b_{i} ∈ C gegeben.

A := ∑_{n=0}^{∞} a_{n}x^{n}
= ∑_{i=0}^{k−1} a_{i}x^{i} + ∑_{n=k}^{∞}(c_{1}a_{n−1} + ⋯ + c_{k}a_{n−k})x^{k}
= ∑_{i=0}^{k−1} b_{i}x^{i} + c_{1}x (A − ∑_{i=0}^{k−1} b_{i}x^{i}) + c_{2}x^{2} (A − ∑_{i=0}^{k−2} b_{i}x^{i})
+ ⋯ + c_{k}x^{k}A

Auflösen nach A

A = \frac{f}{c_{1}x + ⋯ + c_{k}x^{k} − 1}

mit

f=b_{0} + (b_{1} − c_{1}b_{0})x + ⋯ + (b_{k−1} − c_{1}b_{k−1} − c_{k−1}b_{k})x^{k} Es wird jetzt eine Partialbruchzerlegung durchgeführt:

A = ∑ i = 1^{r} \frac{f_{i}}{(1 − α_{i}x)}m_{i} f_{i} = ∑_{j=0}^{m_{i}−1} f_{ij}x^{i}

=∑_{i} = 1^{r} ∑_{j=0}^{m_{i}−1} f_{ij} ∑_{n=j}^{∞} \binom{n+m−1}{n} α_{i}^{n−j}x^{n}

Die α_{i} im Verfahren erhält man als Nullstellen des reflektierten Polynoms

g^{R} = −x^{k} + c_{1}x^{k−1} + ⋯ + c_{k−1}x + c_{k}

Die f_{ij} kann man durch die Anfangsbedingungen bestimmen.

1.5.10 \underline{Beispiel:}Catalanzahlen

C_{n} ={zulässige Klammerungen mit 2n Klammern }

C_{n} = |C_{n}|

C_{0} = 1
C_{1} = 1  ()
C_{2} = 2  ()(), (())
C_{3} = 5
C_{n} = n-te Catalanzahl

C_{n}^{(k)} =Zeichenketten (aus C_{n}),bei denen die 1.Klammer an der Position 2k geschlossen wird.

C_{n} = ⨄_{k=1}^{n} C_{n}^{(k)}

|C_{n}| = C_{n} = ∑_{k=1}^{n} C_{k−1}C_{n−k}  n ≥ 1

C = ∑_{n=0}^{∞} C_{n}x^{n}

= C_{0} + ∑_{n=1}^{∞} C_{n}x^{n}

= 1 + ∑_{n=1}^{∞} (∑_{k=1}^{n} C_{k−1}C_{n−k}) x^{n}
= 1 + (x · C) · C
C = 1 + x · c^{2}  · x
x^{2}C^{2} − xC + x = 0
x^{2}C^{2} − xC + 1/4 = −x + 1/4
((Cx − 1/2)^{2} = −x + 1/4
xC − 1/2 = ±\sqrt{−x + 1/4}
xC = 1/2 · (1 ± \sqrt{1 − 4x})

1.5.11 \underline{Satz 3:}

0 ≠ A = ∑_{n=0}^{∞} a_{n}x^{n} ∈ K[[x]]ein B = ∑_{n=0}^{∞} b_{n}x^{n} ∈ K[[x]] mit B^{2} = A

genau dann, wenn es ein b ≠ 0gibt mit B^{2} = a_{0} (≠ 0)

1.6 Die Polynommethode

1.6.1 \underline{Satz 1}

Ist K ein Körper und 0 ≠ f ∈ K[x]

f = ∑_{i=0}^{n} a_{i}x^{i} a_{n} ≠ 0

so hat f höchstens n Nullstellen.

1.6.2 \underline{Folgerung:}

Ist f = ∑_{i=0}^{n} a_{i}x^{i} g = ∑_{i=0}^{n} b_{i}x^{i} ∈ K[x]

und ist f(α_{i}) = g(α_{i}) für alle α_{i} ∈ M ⊆ K mit |M| ≥ n + 1 so gilt f = g, d.h. a_{i} = b_{i}∀i = 0, …, n. \underline{Beweis:} folgt aus Satz1; betrachte f − g Grad(f − g) ≤ n also f − g = 0.

Im folgenden sei K ein Körper mit Q ⊆ K

1.6.3 \underline{Definition:}

x\underline{n} = x(x − 1) ⋯ (x − n + 1) ∈ K[x] \binom{x}{n} = \frac{1}{n!}x\underline{n} ∈ K[x]x\underline{0} = 1 \binom{x}{0} = 1

\underline{Beispiel:} In 1.2.4 Satz 3:

m^{n} = ∑_{k=0}^{m} S_{n,k}m\underline{k}

= ∑_{k=0}^{n} S_{n,k}m\underline{k}  (1.1)

für n ≥ k > m gilt m\underline{k} = m(m − 1) ⋯ 0(…) = 0 für n < k ≤ m gilt S_{n,k} = 0

Setze f = x^{n}
g = ∑_{k=0}^{n} S_{n,k}x\underline{k}
f(m) = g(m) ∀m ∈ N wegen (1.1)

20KAPITEL 1. ABZÄHLUNGEN, REKURSIONEN, ERZEUGENDE FUNKTIONEN

1.6.4 \underline{Satz 2:}

Ist Q ⊆ K Körper, so gilt

1.

x^{n} = ∑_{k=0}^{n} S_{n,k}x\underline{k}

2.

x^{\underline{n}=∑_{k=0}^{n}(−1)^{n−k}s_{n,k}x^{k}}
1.6.5 \underline{Bemerkung:}

(x^{n})_{n∈N_{0}} und (x^{\underline{n})_{n∈N_{0}}} sind K-Basen des K-Vektorraums K[x] und

[S_{n,k}]_{n,k∈N_{0}}
[(−1)^{n−k}s_{n,k}]_{n,k∈N_{0}}

sind Basiswechselmatrizen, also invers zu einander.