Mengenlehre

• es gilt:
  • \emptyset \subseteq M$\emptyset \subseteq M$
  • wenn M \subseteq \emptyset$M \subseteq \emptyset$, dann M = \emptyset$M = \emptyset$
  • wenn M_1 \subseteq M_2$M_1 \subseteq M_2$, dann M_1 \cap M_2 \neq \emptyset$M_1 \cap M_2 \neq \emptyset$
  • wenn M_1 = M_2$M_1 = M_2$, dann M_1 \subseteq M_2$M_1 \subseteq M_2$ und M_2 \subseteq M_1$M_2 \subseteq M_1$
• Differenz und symmetrische Differenz:
  • M_2 \backslash M_1$M_2 \backslash M_1$: Elemente der Menge M_2$M_2$, ohne Elemente, die auch in M_1$M_1$ sind
  • M_1 \Delta M_2$M_1 \Delta M_2$: Elemente, die nur in eines der beiden, aber nicht in beiden Mengen sind
    • M_1 \Delta M_2 = M_2 \Delta M_1 = (M_1 \backslash M_2) \cup (M_2 \backslash M_1)$M_1 \Delta M_2 = M_2 \Delta M_1 = (M_1 \backslash M_2) \cup (M_2 \backslash M_1)$
• Kardinalität einer Menge |M|$|M|$: bestimmt die Anzahl der (unterschiedlichen) Elemente einer Menge
• Mengenoperationen:
  • Schnitt \cap$\cap$
    • wenn M_1 \cap M_2 = \emptyset$M_1 \cap M_2 = \emptyset$, dann sind die Mengen disjunkt
  • Vereinigung \cup$\cup$
• Universum \Omega$\Omega$, Komplement \overline A = \Omega \backslash A$\overline A = \Omega \backslash A$
• Potenzmenge 2^M$2^M$ / \mathcal{P}(M)$\mathcal{P}(M)$: alle Teilmengen von M$M$
  • Kardinalität der Potenzmenge: 2^{|M|}$2^{|M|}$
• Partition: Menge von disjunkten, nicht leeren Teilmengen von M$M$, deren Vereinigung genau M$M$ ergibt
• Kartesisches Produkt: A \times B = \{ (a,b) \; | \; a \in A, b \in B\}$A \times B = \{ (a,b) \; | \; a \in A, b \in B\}$
  • Menge aller Paare, deren ersten Komponente ein Element aus A und deren zweiten ein Element aus B ist
  • |A \times B| = |A| * |B|$|A \times B| = |A| * |B|$
  • nicht kommutativ
• "k-Tupel": A^k = \{ (a_1, ..., a_k) \; | \; a_1, ..., a_k \in A\}$A^k = \{ (a_1, ..., a_k) \; | \; a_1, ..., a_k \in A\}$

Standardäquivalenzen

• A = A \cup A$A = A \cup A$
• A = A \cap A$A = A \cap A$
• A = A \cup \emptyset$A = A \cup \emptyset$
• \emptyset = A \cap \emptyset$\emptyset = A \cap \emptyset$
• A \cup B = B \cup A$A \cup B = B \cup A$
• A \cap B = B \cap A$A \cap B = B \cap A$
• A \cup (B \cup C) = (A \cup B) \cup C$A \cup (B \cup C) = (A \cup B) \cup C$
• A \cap (B \cap C) = (A \cap B) \cap C$A \cap (B \cap C) = (A \cap B) \cap C$
• A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$
• A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
• A \; \backslash \; (B \cup C) = (A \; \backslash \; B) \cap (A \; \backslash \; C)$A \; \backslash \; (B \cup C) = (A \; \backslash \; B) \cap (A \; \backslash \; C)$
• A \; \backslash \; (B \cap C) = (A \; \backslash \; B) \cup (A \; \backslash \; C)$A \; \backslash \; (B \cap C) = (A \; \backslash \; B) \cup (A \; \backslash \; C)$
• A = A \cup (A \cap B)$A = A \cup (A \cap B)$
• A = A \cap (A \cup B)$A = A \cap (A \cup B)$
• A \; \Delta \; B = (A \; \backslash \; B) \cup (B \; \backslash \; A)$A \; \Delta \; B = (A \; \backslash \; B) \cup (B \; \backslash \; A)$

Standardäquivalenzen mit definiertem Universum

• A \cap \overline A = \emptyset$A \cap \overline A = \emptyset$
• A \cup \overline A = \Omega$A \cup \overline A = \Omega$
• A \; \backslash \; B = A \cap \overline B$A \; \backslash \; B = A \cap \overline B$
• \overline{\overline A} = A$\overline{\overline A} = A$
• \overline{A \cup B} = \overline A \cap \overline B$\overline{A \cup B} = \overline A \cap \overline B$
• \overline{A \cap B} = \overline A \cup \overline B$\overline{A \cap B} = \overline A \cup \overline B$

Wörter und Sprachen

• Alphabet: \Sigma$\Sigma$
• Menge aller endlichen Wörter \Sigma^*$\Sigma^*$: \bigcup_{k \in \N_0}\Sigma^k$\bigcup_{k \in \N_0}\Sigma^k$
  • "Menge aller endlichen Tupel mit Einträgen aus einem Alphabet \Sigma$\Sigma$"
• Wort = Tupel
  • leeres Wort \epsilon$\epsilon$ = leeres Tupel
• Sprache: L \subseteq \Sigma^*$L \subseteq \Sigma^*$

Binäre Relationen

• 2-stellige Relationen R \subseteq A \times B$R \subseteq A \times B$
  • Infix-Notation: a R b$a R b$ für (a,b) \in R$(a,b) \in R$

Relationales Produkt

• R^0 =$R^0 =$ Id_A = \{(a,a) \; | \; a\in R \}$_A = \{(a,a) \; | \; a\in R \}$

• R^1 = R^0R = R$R^1 = R^0R = R$

• R^2 = R^1R = RR$R^2 = R^1R = RR$ ("Pfade mit 2 Schritte")
  

• transitive Hülle: R^+ = \bigcup_{k \in \N}R^k$R^+ = \bigcup_{k \in \N}R^k$ (alle Pfade, die mindestens einen Schritt machen)

• reflexiv-transitive Hülle: R^* = R^0 \cup R^k$R^* = R^0 \cup R^k$ (alle Pfade, die mindestens einen Schritt machen, und auch Pfade der Länge 0 / Selbstschleifen)
  

Eigenschaften von binären Relationen

• eine binäre Relation R \subseteq A \times A$R \subseteq A \times A$ ist...
  • ...reflexiv, falls Id_A \subseteq R$_A \subseteq R$ (jeder Knoten hat eine Schleife)
  • ...symmetrisch, falls für jedes (s,t) \in R$(s,t) \in R$ auch (t,s) \in R$(t,s) \in R$ gilt (zwischen je zwei Knoten gibt es entweder keine oder beide Kanten)
  • ...asymmetrisch, falls für jedes (s,t) \in R$(s,t) \in R$ immer (t,s) \notin R$(t,s) \notin R$ gilt (keine Schleifen + zwischen je zwei verschiedenen Knoten gibt es höchstens eine Kante)
  • ...antisymmetrisch, falls für jedes (s,t) \in R$(s,t) \in R$ und (t,s) \in R$(t,s) \in R$ auch s = t$s = t$ gilt (Schleifen erlaubt + zwischen je zwei verschiedenen Knoten gibt es höchstens eine Kante)
  • ...transitiv, falls für jedes (s,t) \in R$(s,t) \in R$ und (t,u) \in R$(t,u) \in R$ auch (s,u) \in R$(s,u) \in R$ gilt (kommt man mit genau zwei Schritten von s$s$ nach u$u$, dann auch mit genau einem)
• partielle Ordnungen: reflexiv, antisymmetrisch, transitiv (z.B. |_\N$|_\N$)
  • totale Ordnungen: partielle Ordnung + für alle a,b \in R$a,b \in R$ gilt entweder aRb$aRb$ oder bRa$bRa$
  • m \in A$m \in A$ ist ein maximales Element bzgl. R$R$, wenn es keine Kanten zu einem anderen Element gibt
    • analog: minimal
  • Darstellung: Hasse-Diagramme
    
  • m \in A$m \in A$ ist das größte Element bzgl. R$R$, wenn es keine Kanten zu einem anderen Element gibt und von jedem anderen Knoten eine Kante zu m$m$ existiert (z.B. 1 in |^{-1}_\N$|^{-1}_\N$)
    • analog: kleinstes Element (z.B. 1 in |_\N$|_\N$)
  • (!) mit R$R$ ist R^{-1}$R^{-1}$ auch eine Ordnung
• Äquivalenzrelationen: reflexiv, symmetrisch, transitiv (z.B. \leq_\Z$\leq_\Z$)
  • Äquivalenzklasse eines Objekts a$a$ bzgl. R$R$: [a]_R = \{ b \in A \; | \; a R b\}$[a]_R = \{ b \in A \; | \; a R b\}$
    • z.B. [1]_{=\Z} = \{1\}$[1]_{=\Z} = \{1\}$, [-5]_{\equiv_3} = \{3 \Z + 1\}$[-5]_{\equiv_3} = \{3 \Z + 1\}$
    • es gilt:
      • a \in [a]_R$a \in [a]_R$
      • [a]_R = [b]_R$[a]_R = [b]_R$ für aRb$aRb$
      • [a]_R \cap [b]_R = \emptyset$[a]_R \cap [b]_R = \emptyset$ für (a,b) \notin R$(a,b) \notin R$
  • Quotient von A$A$ bzgl. R$R$: Menge aller Äquivalenzklassen A/R = \{ [a]_R \; | \; a \in A\}$A/R = \{ [a]_R \; | \; a \in A\}$
    • z.B. \Z/\equiv_3=\{3\Z, 3\Z + 1, 3\Z + 2\}$\Z/\equiv_3=\{3\Z, 3\Z + 1, 3\Z + 2\}$

Funktionen

• totale Funktion: eine Relation R \subseteq A \times B$R \subseteq A \times B$, wobei es für jedes a \in A$a \in A$ genau ein b \in B$b \in B$ mit (a,b) \in R$(a,b) \in R$ gibt
  • Menge aller Funktionen von A$A$ nach B$B$: B^A = \{ f : A \to B\}$B^A = \{ f : A \to B\}$ mit |B^A| = |B|^{|A|}$|B^A| = |B|^{|A|}$
• partielle Funktion: eine Relation R \subseteq A \times B$R \subseteq A \times B$, wobei es für jedes a \in A$a \in A$ höchstens ein b \in B$b \in B$ mit (a,b) \in R$(a,b) \in R$ gibt
• Komposition (g$g$ nach f$f$): (g \circ f)(x) = g(f(x))$(g \circ f)(x) = g(f(x))$
  • aus f : A \to B$f : A \to B$ und g : B \to C$g : B \to C$ folgt g \circ f : A \to C$g \circ f : A \to C$

Eigenschaften von Funktionen

• eine Funktion f : A \to B$f : A \to B$ ist...
  • ...injektiv, falls aus f(a) = f(a')$f(a) = f(a')$ stets a = a'$a = a'$ folgt (für jedes b \in B$b \in B$ gibt es höchstens ein Urbild)
  • ...surjektiv, falls für jedes b \in B$b \in B$ ein a \in A$a \in A$ mit f(a) = b$f(a) = b$ gibt (für jedes b \in B$b \in B$ gibt es mindestens ein Urbild)
  • ...bijektiv, falls sie sowohl injektiv, als auch surjektiv ist (für jedes b \in B$b \in B$ gibt es genau ein Urbild)

Kardinalität von Mengen

• |A| \leq |B|$|A| \leq |B|$ falls es eine Injektion f: A \to B$f: A \to B$ gibt
• |A| = |B|$|A| = |B|$ falls es eine Bijektion f: A \to B$f: A \to B$ gibt
• |A| < |B|$|A| < |B|$ falls es eine Injektion f: A \to B$f: A \to B$, aber keine Injektion g: B \to A$g: B \to A$ gibt
• Satz von Cantor:
  • sind f: A \to B$f: A \to B$ und g: B \to A$g: B \to A$ injektiv, dann ist h: A \to B$h: A \to B$ bijektiv (|A| = |B|$|A| = |B|$)

Graphen

Gerichtete Graphen (Digraphen)

• G = (V, E)$G = (V, E)$
  • G$G$ - Digraph
  • V$V$ - Knotenmenge, |V|$|V|$ - Anz. Knoten
    • Endliche Graphen: Wenn |V|$|V|$ endlich, ist G$G$ endlich
  • E \subseteq V \times V$E \subseteq V \times V$ - Kantenmenge, |E|$|E|$ - Anz. Kanten
    • jede Kante ist ein Tupel (u, v)$(u, v)$
• Bipartite Graphen: V = A \dot\cup B$V = A \dot\cup B$ (A und B disjunkt)
• Pfad: je zwei aufeinander folgende Knoten sind durch eine gerichtete Kante aus E$E$ verbunden
  • Länge eines Pfades: Anzahl der Kanten
  • einfacher Pfad: kein Knoten taucht mehrmals auf
  • (!) In einem endlichen Digraphen hat ein einfacher Pfad maximal die Länge |V| - 1$|V| - 1$
• Teilgraph G[U]$G[U]$ (von U induzierter Teilgraph, U \subseteq V$U \subseteq V$)
  • Beispiel: U = \{a,2,b\}$U = \{a,2,b\}$
    
  • H = (V_H, E_H)$H = (V_H, E_H)$ ist Teilgraph von G = (V_G, E_G)$G = (V_G, E_G)$, wenn V_H \subseteq V_G \land E_H \subseteq E_G$V_H \subseteq V_G \land E_H \subseteq E_G$
• Zusammenhang und Zusammenhangskomponente
  • G - zusammenhängend, wenn u(E \cup E^{-1})^*v \; \forall u,v \in V$u(E \cup E^{-1})^*v \; \forall u,v \in V$
    • es existiert einen Weg zwischen jedem u$u$ und v$v$, wenn G$G$ ungerichtet wäre
    • U \subseteq V$U \subseteq V$ ist eine Zusammenhangskomponente von G, wenn G[U]$G[U]$ zusammenhängend ist
    • (*) hinreichende Bedingung: wenn die Summe aus minimalem und maximalem Knotengrad größer oder gleich n-1$n-1$ ist, ist der Graph zusammenhängend
      • generell, ohne Beweis: prüfe anhand des maximalen Grades, ob der Knoten mit minimalem Grad irgendwie durch einen Pfad mit dem Knoten mit maximalem Grad verbunden ist
  • G - stark zusammenhängend, wenn uE^*v \; \forall u,v \in V$uE^*v \; \forall u,v \in V$
    • es existiert einen Weg zwischen jedem u$u$ und v$v$ im gerichteten Graph G$G$
    • U \subseteq V$U \subseteq V$ ist eine starke Zusammenhangskomponente von G, wenn G[U]$G[U]$ stark zusammenhängend ist
    • isolierte Knoten sind starke Zusammenhangskomponenten
    • (!) jeder stark zusammenhängende Graph G$G$ mit n$n$ Knoten hat mindestens n$n$ Kanten
• Kreise
  • Pfad mit l \geq 1$l \geq 1$, der in Knoten u$u$ beginnt und in u$u$ endet
  • einfache Kreise: kein Knoten taucht mehrmals auf
    • m.a.W der Kreis enthält keinen kleineren Kreis
  • ein Graph ohne Kreise heist azyklisch (kreisfrei)
• Vorgänger und Nachfolger
  • Nachfolger von u$u$: uE = \left\{v \in V | uEv\right\}$uE = \left\{v \in V | uEv\right\}$
  • Vorgänger von v$v$: Ev = \left\{u \in V | uEv\right\}$Ev = \left\{u \in V | uEv\right\}$
• Isomorphie
  • G \cong H$G \cong H$, wenn man die Knoten von G in H umbenennen kann (V_G \rightarrow V_H$V_G \rightarrow V_H$), so dass die Kanten erhalten bleiben
  • (!) Isomorphie \cong$\cong$ ist eine Äquivalenzrelation
  • isomorphe Graphen haben dieselbe Gradfolge (sortiert), jedoch kann es sein, dass 2 nicht-isomorphe Graphen dieselbe Gradfolge haben

Ungerichtete und einfache Graphen

• G = (V, E)$G = (V, E)$ ungerichtet, wenn E$E$ symmetrisch (wenn es zwischen zwei Knoten entweder gar keine oder beide Kanten existieren)
  • in einem ungerichteten Graph hat ein Kreis mind. Länge 3 (l \geq 3$l \geq 3$)
• einfacher Graph: endlicher, ungerichteter Digraph ohne Schleifen (E$E$ symmetrisch, irreflexiv)
  • Satz: ein einfacher Graph ist genau dann bipartit, wenn er keinen Kreis ungerader Länge enthält
• spezielle einfache Graphen:
  • Vollständiger Graph K_n$K_n$
  • Kreisgraph C_n$C_n$ (n \geq 3$n \geq 3$)
  • Pfadgraph P_n$P_n$
  • Vollständiger Bipartiter Graph K_{m,n}$K_{m,n}$ (m \leq n$m \leq n$)
  • Perfekter Binärbaum B_h$B_h$ (h - Höhe)
    
• (!) Eigenschaften:
  • für jeden einfachen zshgd. Graphen gilt: |E| \geq |V| - 1$|E| \geq |V| - 1$ bzw. |V| \leq |E| + 1$|V| \leq |E| + 1$
    • "jeder zshgd. Graph hat mindestens |V| - 1$|V| - 1$ Kanten"
    • "jeder zshgd. Graph hat höchstens |E| + 1$|E| + 1$ Knoten"
  • jeder einfache Graph mit |E| \geq |V|$|E| \geq |V|$ und |V| \geq 3$|V| \geq 3$ enthält einen Kreis
    • G$G$ kreisfrei, wenn |V| \geq |E| + 1$|V| \geq |E| + 1$
    • wenn G$G$ kreisfrei ist, dann ist G$G$ bipartit, falls |E| \geq 1$|E| \geq 1$
  • Handschlaglemma: 2|E| = \sum_{i \in [n]}deg(v_i)$2|E| = \sum_{i \in [n]}deg(v_i)$ (Anzahl der Kanten eines Graphen ist gleich mit der Hälfte der Summe aller Knotengrade)
    • ein Graph mit |V| > \frac{1}{2}\sum_{i\in[n]}d_i+1$|V| > \frac{1}{2}\sum_{i\in[n]}d_i+1$ kann nicht zusammenhängend sein (da sonst |V| > |E| + 1$|V| > |E| + 1$ gilt und der Graph nicht genug Kanten hat)
      • dies bedeutet jedoch nicht, dass ein Graph mit |V| \leq \frac{1}{2}\sum_{i\in[n]}d_i+1$|V| \leq \frac{1}{2}\sum_{i\in[n]}d_i+1$ zshgd. ist

Bäume

• einfache Graphen, die sowohl zshgd., als auch kreisfrei sind
  • Knoten mit deg(v) = 1$deg(v) = 1$: "Blatt"
  • andere Knoten: "innere Knoten"
• (!) Eigenschaften:
  • |E| = |V| - 1$|E| = |V| - 1$ bzw. |V| = |E| + 1$|V| = |E| + 1$
  • jeder Baum mit |V| \geq 2$|V| \geq 2$ hat mindestens 2 Blätter
  • jeder zshgd. Graph hat mindestens einen Spannbaum

Perfekte Binärbaume

• (!) Eigenschaften:
  • ein Baum der Höhe h$h$ hat 2^h$2^h$ Blätter
  • ein Baum der Höhe h$h$ hat 2^{h+1}-1$2^{h+1}-1$ Knoten

Wurzelbäume

• Bäume mit einer Wurzel (root), von welcher man jeden anderen Knoten erreichen kann
• Höhe = Tiefe = Level = Abstand eines Knoten u$u$ von der Wurzel r$r$ (root)
  • Höhe eines Baumes: max. Abstand zw. Wurzel und einem Blatt
  • Schreibweise:
    • uEv$uEv$ (u Vater von v, v Kind von u)
    • uE^*v$uE^*v$ (u Vorfahrer von v, v Nachfahrer von u)

Gradfolge

• Havel-Hakimi-Algorithmus

Hamiltonkreise und Eulertouren

• Hamiltonkreis: jeder Knoten wird genau einmal besucht
  • (!) Existenz (hinreichend; es gibt auch Hamiltonkreise, wo diese Bedingung verletzt wird): jeder Knoten in einem einfachen Graph mit |V| \geq 3$|V| \geq 3$ hat mindestens Grad \frac{|V|}{2}$\frac{|V|}{2}$
• Eulertour: jede Kante wird genau einmal besucht
  • (!) Existenz: jeder Knoten in einem einfachen, zshgd. Graph hat geraden Grad

Planarität

• ein einfacher Graph ist planar, wenn man ihn so zeichnen kann, dass sich keine Kanten überschneiden
• (!) Eulerische Polyederformel (EPF) für zshgd., planare Graphen (I): f - |E| + |V| = 2$f - |E| + |V| = 2$ (f$f$: Anzahl der Flächen)
  • (!) die umschließenede Fläche wird mitgezählt!
• (!) Eulerische Polyederformel für planare Graphen mit k maximale Zshgskomponenten (II): f- |E| + |V|= 1 + k$f- |E| + |V|= 1 + k$
• (!) Eigenschaften jedes planaren Graphen:
  • f - |E| + |V| \geq 2$f - |E| + |V| \geq 2$ (laut I und II)
  • |E| \leq 3|V| - 6$|E| \leq 3|V| - 6$ für |V| \geq 3$|V| \geq 3$
  • Satz von Kuratowski: ein Graph ist genau dann planar, wenn er weder K_5$K_5$, noch K_{3,3}$K_{3,3}$ als Minor enthält
    • G$G$ hat mindestens 5 Knoten mit mindestens Grad 4 oder mindestens 6 Knoten mit mindestens Grad 3 \to$\to$ G$G$ ist nicht planar
  • wenn eine Fläche f$f$ durch mindestens n$n$ Kanten definiert ist: |E| \geq \frac{n}{2}f$|E| \geq \frac{n}{2}f$ bzw. f \leq \frac{2}{n}|E|$f \leq \frac{2}{n}|E|$
    • wenn eine Fläche f$f$ durch genau n$n$ Kanten definiert ist: |E| = \frac{n}{2}f$|E| = \frac{n}{2}f$ bzw. f = \frac{2}{n}|E|$f = \frac{2}{n}|E|$

Knotenfärbung

• \chi(G)$\chi(G)$: minimale Anzahl der Farben, für die es eine Knotenfärbung für den Graphen G gibt
• (!) Eigenschaften:
  • für einfache Graphen: \chi(G) \leq |V|$\chi(G) \leq |V|$
  • für bipartite Graphen: \chi(G) \leq 2$\chi(G) \leq 2$
  • wenn E \neq \emptyset$E \neq \emptyset$: \chi(G) > 1$\chi(G) > 1$
  • Vier-Farben-Satz: für jeden planaren Graphen gilt \chi(G) \leq 4$\chi(G) \leq 4$
• überprüfe, ob ein Graph bipartit ist:
  • färbe einen Knoten in einer Farbe
  • färbe Nachbar mit einer anderen Farbe
  • wenn Widerspruch (2 benachbarte Knoten haben selbe Farbe) \to$\to$ G ist nicht bipartit

Heiratssatz, Gale-Shapley-Algorithmus

• Matchings existieren in bipartiten Graphen G = (A \dot \cup B, E)$G = (A \dot \cup B, E)$
  • Definition: ein Matching M \subseteq E$M \subseteq E$ ist eine Teilmenge der Kanten E$E$ eines Graphen G$G$, so dass keine zwei Kanten aus M$M$ einen gemeinsamen Knoten haben (\forall e,e' \in M \; : \; |e \cap e'| \neq 1$\forall e,e' \in M \; : \; |e \cap e'| \neq 1$)
  • perfektes Matching: jeder Knoten wurde gematcht (|M| = |V| / 2$|M| = |V| / 2$)
• Heiratssatz: \exists$\exists$ Matching \leftrightarrow$\leftrightarrow$ |\Gamma(X)| \geq |X|$|\Gamma(X)| \geq |X|$ mit \Gamma(X) = \bigcup_{x\in X}\Gamma(x)$\Gamma(X) = \bigcup_{x\in X}\Gamma(x)$ (X$X$ - beliebige Knotenmenge in A, \Gamma(X)$\Gamma(X)$ - Nachbarn von X in B)
  • jede Knotenteilmenge X$X$ in A hat mind. |X|$|X|$ Nachbarn in B
• Matchings mit Präferenzen
  
  • instabiles Matching: f(a) \prec_a f(a') \; \land \; a' \prec_{f(a')} a$f(a) \prec_a f(a') \; \land \; a' \prec_{f(a')} a$ (a bevorzugt den Partner von a' und der Partner von a' bevorzugt a \to$\to$ a und f(a') würden ihren aktuellen Partner verlassen)
    
  • stabiles Matching
    

Matrizen

• M \in D^{m \times n}$M \in D^{m \times n}$: Matrix M$M$ mit m$m$ Zeilen und n$n$ Spalten über eine Menge D$D$
  • D^{1 \times n}$D^{1 \times n}$: Zeilenvektoren
  • D^{n \times 1}$D^{n \times 1}$: Spaltenvektoren
• (!) Summe C zweier Matrizen A, B: C_{i,j} = A_{i,j} + B_{i,j}$C_{i,j} = A_{i,j} + B_{i,j}$ mit C = A + B \in \R^{m \times n}$C = A + B \in \R^{m \times n}$
  • addiere den Eintrag an Position i,j$i,j$ in A mit den Eintrag an derselben Position i,j$i,j$ in B, speichere Ergebnis an Position i,j$i,j$ in neuer Matrix C
• (!) Multiplikation zweier Matrizen:
  • es seien zwei Matrizen A \in \R^{a \times b}$A \in \R^{a \times b}$ und B \in \R^{b \times c}$B \in \R^{b \times c}$
  • das Ergebnis deren Multiplikation ist C = A \cdot B \in \R^{a \times c}$C = A \cdot B \in \R^{a \times c}$
    • Ergebnis der Multiplikation hat Zeilenanzahl von A und Spaltenanzahl von B
    • C_{i,j}$C_{i,j}$ ist das Skalarprodukt des i-ten Zeilenvektors und j-ten Spaltenvektors
• (!) Adjazenzmatrizen
  • (A^k_G)i,j$(A^k_G)i,j$: Anzahl der verschiedenen k$k$-Schritt-Pfade von v_i$v_i$ nach v_j$v_j$ in G$G$
    • A^0_G$A^0_G$: 1 auf Diagonale von oben links nach unten rechts, sonst 0
• Random-Surfer-Modell
  • (P^k_G)$(P^k_G)$: Wahrscheinlichkeit, von v_i$v_i$ zu v_j$v_j$ in genau k$k$ Schritte zu kommen
    • P_{i,j} = \frac{1}{|v_iE|}$P_{i,j} = \frac{1}{|v_iE|}$ (1 / Anzahl der Nachfolger von v_i$v_i$), wenn v_i$v_i$ Nachfolger hat
    • sonst, P_{i,j} = 0$P_{i,j} = 0$
  • Beispiel:
    
    • P_G = \begin{pmatrix} 0 & 1/2 & 0 & 1/2 \\ 0 & 0 & 1/2 & 1/2 \\ 1 & 0 & 0 & 0 \\ 0 & 1/2 & 0 & 1/2 \end{pmatrix}$P_G = \begin{pmatrix} 0 & 1/2 & 0 & 1/2 \\ 0 & 0 & 1/2 & 1/2 \\ 1 & 0 & 0 & 0 \\ 0 & 1/2 & 0 & 1/2 \end{pmatrix}$, P_G^2 = \begin{pmatrix} 0 & 1/4 & 1/4 & 1/2 \\ 1/2 & 1/4 & 0 & 1/4 \\ 0 & 1/2 & 0 & 1/2 \\ 0 & 1/4 & 1/4 & 1/2 \end{pmatrix}$P_G^2 = \begin{pmatrix} 0 & 1/4 & 1/4 & 1/2 \\ 1/2 & 1/4 & 0 & 1/4 \\ 0 & 1/2 & 0 & 1/2 \\ 0 & 1/4 & 1/4 & 1/2 \end{pmatrix}$, ...

Aussagelogik

• Logik: untersucht, welche Inferenzen korrekt sind
• Inferenz: Aussage der Form "Wenn A wahr ist, dann ist B auch wahr"
  • A: Annahme
  • B: Konklusion
• Vokabular besteht aus:
  • true und false
  • Unendliche Menge von Aussagevariablen V$V$: p$p$, q$q$, r$r$ etc.
  • Operatoren: \land, \lor, \to, \neg$\land, \lor, \to, \neg$ etc.
  • Hilfssymbole: ($($, )$)$
• Logische Operatoren - Schreibweise:

Operator	DS	ERA
Konjunktion	\land$\land$	*
Disjunktion	\lor$\lor$	+
Negation	\neg$\neg$	\overline{a}$\overline{a}$

• (!) Regeln:

  1. true und false sind Formeln
  2. Variablen sind Formeln
  3. Ist F$F$ eine Formel, so ist \neg F$\neg F$ auch eine Formel
  4. Sind F$F$ und G$G$ Formeln, so sind (F \land G), (F \lor G), (F \to G)$(F \land G), (F \lor G), (F \to G)$ auch Formeln

• Terminalsymbole: Symbole, die man nicht ersetzen kann (z.B. p$p$, q$q$)

• V_F$V_F$: Menge aller in F$F$ vorkommenden Variablen

• G$G$ ist Teilformel von F$F$, wenn G$G$ vollständig und zshgd. in F$F$ vorkommt

  • Beispiel: Teilformeln zu F = ((p \lor \neg q) \land \neg(q \lor \neg\neg r))$F = ((p \lor \neg q) \land \neg(q \lor \neg\neg r))$
    • p,q,\neg q, (p \lor \neg q), r, \neg r, \neg \neg r, (q \lor \neg \neg r), \neg(q \lor \neg \neg r), ((p \lor \neg q) \land \neg(q \lor \neg\neg r))$p,q,\neg q, (p \lor \neg q), r, \neg r, \neg \neg r, (q \lor \neg \neg r), \neg(q \lor \neg \neg r), ((p \lor \neg q) \land \neg(q \lor \neg\neg r))$

• Bindungsregeln (Reihenfolge stark \to$\to$ schwach): \neg, \land, \lor, \to$\neg, \land, \lor, \to$

  • \neg p \land q \equiv (\neg p \land q)$\neg p \land q \equiv (\neg p \land q)$
  • p \land q \to r \equiv ((p \land q) \to r)$p \land q \to r \equiv ((p \land q) \to r)$
  • p \land q \lor r \land s \equiv ((p \land q) \lor (r \land s))$p \land q \lor r \land s \equiv ((p \land q) \lor (r \land s))$

• Belegung \beta: V' \to \{0, 1\}$\beta: V' \to \{0, 1\}$ mit V' \subseteq V$V' \subseteq V$

  • Abbildung, die jeder Aussagenvariablen V'$V'$ einen Wahrheitswert 0 bzw. 1 zuordnet
  • minimal, wenn V' = V_F$V' = V_F$

• Bedeutung / Wahrheitswert von F: [F](\beta)$[F](\beta)$ oder [F]$[F]$:

  • [F](\beta) = \begin{dcases}1 & \text{falls } F = true \\ 0 & \text{falls } F = false \\ \beta(p) & \text{falls }F = p \text{ für } p \in V \\ 1 - [G](\beta) & \text{falls } F = \neg G \\ \max\{[G](\beta), [H](\beta)\} & \text{falls } F = G \lor H \\ \min\{[G](\beta), [H](\beta)\} & \text{falls } F = G \land H \\ \max\{1 - [G](\beta), [H](\beta)\} & \text{falls } F = G \to H\end{dcases}$[F](\beta) = \begin{dcases}1 & \text{falls } F = true \\ 0 & \text{falls } F = false \\ \beta(p) & \text{falls }F = p \text{ für } p \in V \\ 1 - [G](\beta) & \text{falls } F = \neg G \\ \max\{[G](\beta), [H](\beta)\} & \text{falls } F = G \lor H \\ \min\{[G](\beta), [H](\beta)\} & \text{falls } F = G \land H \\ \max\{1 - [G](\beta), [H](\beta)\} & \text{falls } F = G \to H\end{dcases}$

• Erf_G$_G$: Menge aller minimalen Belegungen \beta$\beta$, die G erfüllen

• Eine Formel ist...

  • ...eine Tautologie / (allgemein)gültig, wenn sie in allen Welten wahr ist (für jede Belegung \beta$\beta$ gilt [F](\beta) = 1$[F](\beta) = 1$) (Test: prüfe in Wahrheitstabelle, ob Spalte für F$F$ nur 1 enthält)
    • z.B. p \lor \neg p$p \lor \neg p$
  • ...ein Widerspruch / unerfüllbar, wenn sie in allen Welten falsch ist (für jede Belegung \beta$\beta$ gilt [F](\beta) = 0$[F](\beta) = 0$) (Test: prüfe in Wahrheitstabelle, ob Spalte für F$F$ nur 0 enthält)
    • z.B. p \land \neg p$p \land \neg p$
  • ...erfüllbar, wenn es mindestens eine Belegung \beta$\beta$ mit [F](\beta) = 1$[F](\beta) = 1$ gibt (Test: prüfe in Wahrheitstabelle, ob Spalte für F$F$ mindestens ein 1 enthält)
    • z.B. p \to q$p \to q$

• F$F$ gültig \leftrightarrow$\leftrightarrow$ \neg F$\neg F$ unerfüllbar

  • F$F$ unerfüllbar \leftrightarrow$\leftrightarrow$ \neg F$\neg F$ gültig

• F$F$ nicht gültig \leftrightarrow$\leftrightarrow$ \neg F$\neg F$ erfüllbar

  • F$F$ erfüllbar \leftrightarrow$\leftrightarrow$ \neg F$\neg F$ nicht gültig

• F$F$ nicht gültig, aber erfüllbar \leftrightarrow$\leftrightarrow$ \neg F$\neg F$ nicht gültig, aber erfüllbar

Wahrheitstabellen

Logische Äquivalenzen

• F \equiv G$F \equiv G$ genau dann, wenn für jede mögliche Belegung \beta$\beta$ für F$F$ und G$G$ die Gleichung [F](\beta) = [G](\beta)$[F](\beta) = [G](\beta)$ gilt
  • wenn F und G äquivalent sind, heißt das, dass F und G zwei unterschiedliche Schreibweise für die selben Formeln sind / F und G sind semantisch gleich
    • Test: prüfe in Wahrheitstabelle, ob für F \leftrightarrow G$F \leftrightarrow G$ die Spalte für \leftrightarrow$\leftrightarrow$ nur 1 enthält

Logische Inferenzen

• Formel der Gestalt F \to G$F \to G$ ("F impliziert G") (korrekt, wenn sie gültig ist)
• F \models G$F \models G$ ("G folgt aus F") bezeichnet, dass F \to G$F \to G$ gültig ist

Beziehungen

• F \equiv G$F \equiv G$, wenn Erf_F$_F$ = Erf_G$_G$ (Belegungen, die F erfüllen, gleich mit Belegungen, die G erfüllen)
• F \models G$F \models G$, wenn Erf_F$_F$ \subseteq$\subseteq$ Erf_G$_G$ (Belegungen, die F erfüllen, unter den Belegungen, die G erfüllen)
• F ist gültig, wenn...
  • ...\neg F$\neg F$ ein Widerspruch ist
  • ...F \equiv true$F \equiv true$
  • ...true \models F$true \models F$ (anders \models F$\models F$) (1 \to a$1 \to a$ nur dann gültig, wenn a = 1)
• F ist widersprüchlich, wenn...
  • ...\neg F$\neg F$ eine Tautologie ist
  • ...F \equiv false$F \equiv false$
  • ...F \models false$F \models false$ (a \to 0$a \to 0$ nur dann gültig, wenn a = 0)

Äquivalenzumformungen

• Idempotenz
  • F \land F \equiv F$F \land F \equiv F$
  • F \lor F \equiv F$F \lor F \equiv F$
• Kommutativität
  • F \land G \equiv G \land F$F \land G \equiv G \land F$
  • F \lor G \equiv G \lor F$F \lor G \equiv G \lor F$
• Assoziativität
  • (F \land G) \land H \equiv F \land (G \land H)$(F \land G) \land H \equiv F \land (G \land H)$
  • (F \lor G) \lor H \equiv F \lor (G \lor H)$(F \lor G) \lor H \equiv F \lor (G \lor H)$
• Absorption
  • F \land (F \lor G) \equiv F$F \land (F \lor G) \equiv F$
  • F \lor (F \land G) \equiv F$F \lor (F \land G) \equiv F$
• Distributivität
  • F \land (G \lor H) \equiv (F \land G) \lor (F \land H)$F \land (G \lor H) \equiv (F \land G) \lor (F \land H)$
  • F \lor (G \land H) \equiv (F \lor G) \land (F \lor H)$F \lor (G \land H) \equiv (F \lor G) \land (F \lor H)$
• Doppelnegation
  • \neg \neg F \equiv F$\neg \neg F \equiv F$
• De Morgan
  • \neg(F \land G) \equiv \neg F \lor \neg G$\neg(F \land G) \equiv \neg F \lor \neg G$
  • \neg(F \lor G) \equiv \neg F \land \neg G$\neg(F \lor G) \equiv \neg F \land \neg G$
• Triviale Kontradiktion / Tautologie
  • F \land \neg F \equiv false$F \land \neg F \equiv false$
  • F \lor \neg F \equiv true$F \lor \neg F \equiv true$
• Dominanz
  • F \land false \equiv false$F \land false \equiv false$
  • F \lor true \equiv true$F \lor true \equiv true$
• Identität
  • F \land true \equiv F$F \land true \equiv F$
  • F \lor false \equiv F$F \lor false \equiv F$
• Implikation
  • F \to G \equiv \neg F \lor G$F \to G \equiv \neg F \lor G$
• Bikonditional (gdw, iff)
  • F \leftrightarrow G \equiv (F \to G) \land (G \to F) \equiv \neg(F \oplus G)$F \leftrightarrow G \equiv (F \to G) \land (G \to F) \equiv \neg(F \oplus G)$
• XOR
  • F \oplus G \equiv (F \lor G) \land (\neg F \lor \neg G) \equiv (F \land \neg G) \lor (\neg F \land G)$F \oplus G \equiv (F \lor G) \land (\neg F \lor \neg G) \equiv (F \land \neg G) \lor (\neg F \land G)$

KNF und DNF

• Literale L$L$: {p, \neg p$p, \neg p$} (einzelne Variablen und deren Negationen)
• KNF: (L \lor ... \lor L) \land ... \land (L \lor ... \lor L)$(L \lor ... \lor L) \land ... \land (L \lor ... \lor L)$
  • erfüllbar, wenn alle Konjunkte erfüllbar sind
  • jede Formel ist in KNF übertragbar
    1. Entferne \to$\to$, \leftrightarrow$\leftrightarrow$ und \oplus$\oplus$ mit Umformung
    2. Wende deMorgan an
    3. Wende Distributivität an
• DNF: (L \land ... \land L) \lor ... \lor (L \land ... \land L)$(L \land ... \land L) \lor ... \lor (L \land ... \land L)$
  • erfüllbar, wenn mindestens ein Disjunkt erfüllbar ist
  • jede Formel ist in DNF übertragbar
    1. Entferne \to$\to$, \leftrightarrow$\leftrightarrow$ und \oplus$\oplus$ mit Umformung
    2. Wende deMorgan an
    3. Wende Distributivität an

Kanonische DNF und Kanonische KNF

• K. DNF (1-Werte)
  

• K. KNF (0-Werte) (wenn KV-Diagramm, wähle 0-Werte und negiere sie)
  

Aufstellen einer KNF-Formel erfüllbarkeitsäquivalent zu F

• stelle Syntaxbaum von F$F$ auf, notiere Wurzel als T$T$
• für jede Teilformel (nichtterminale Knoten), notiere sie als T_i$T_i$ mit T_i \leftrightarrow T_{i_1} \cdot T_{i_2}$T_i \leftrightarrow T_{i_1} \cdot T_{i_2}$ (wobei i_1$i_1$ und i_2$i_2$ die Kinder von T_i$T_i$ sind) bzw. T_i \leftrightarrow \neg T_{i_1}$T_i \leftrightarrow \neg T_{i_1}$ (wenn nur Negation)
• die finale Klausel hat die Form T \land (T \leftrightarrow T_{i} \cdot T_{j}) \land ...$T \land (T \leftrightarrow T_{i} \cdot T_{j}) \land ...$
• wende Umformungsregeln an, um KNF zu erreichen

Weitere Operatoren

Name	Operator und Syntax	Äquivalent zu...
NAND	F \overline\land G$F \overline\land G$	\neg(F \land G)$\neg(F \land G)$
NOR	F \overline\lor G$F \overline\lor G$	\neg(F \lor G)$\neg(F \lor G)$

DPLL: Davis-Putnam-Logemann-Loveland für Formeln in KNF

• auf Erfüllbarkeit ausgerichtet
• berechnet eine erfüllende Belegung, die weiterhin als Zertifikat der Erfüllbarkeit verwendet werden kann

• Optimierungen (Priorität hoch \to$\to$ niedrig):
  • OLR (one-literal rule): Wenn \exists$\exists$ eine Klausel, die nur L$L$ enthält, setze L$L$ auf true
  • PLR (pure-literal rule): Wenn nur L$L$ und nie \overline L$\overline L$ in jedwelcher Formel auftritt, setze L$L$ auf true$true$
  • Caching / Memoization: bereits behandelte Klauselmengen können ignoriert werden

Resolution

• auf Unerfüllbarkeit ausgerichtet
• berechnet Zertifikat der Unerfüllbarkeit

1. Suche zwei Mengen K_1$K_1$ und K_2$K_2$, wo L \in K_1$L \in K_1$ und \overline L \in K_2$\overline L \in K_2$ (genau ein Literal!)
2. Füge die Vereinigung dieser Mengen ohne L$L$ bzw. \overline L$\overline L$ zur neuen Klauselmenge hinzu
3. Wiederhole, bis die leere Klauselmenge \square$\square$ bzw. {{}} resolviert wird

• Anzahl der möglichen Formeln für n$n$ Literale: 4^n = 2^{2n}$4^n = 2^{2n}$

Kombinatorik

Kombinatorische Grundprinzipien

• Summenregel:
  • wenn A \cap B = \emptyset$A \cap B = \emptyset$, dann |A \cup B| = |A| + |B|$|A \cup B| = |A| + |B|$
  • wenn A \cap B \neq \emptyset$A \cap B \neq \emptyset$, dann |A \cup B| = |A| + |B| - |A \cap B|$|A \cup B| = |A| + |B| - |A \cap B|$
• Produktregel:
  • |A \times B|$|A \times B|$ = |A| * |B|$|A| * |B|$ (kann mit beliebig vielen Mengen erweitert werden)
  • analog |\{a, b\}^n| = 2^n$|\{a, b\}^n| = 2^n$
• (+) Regeln können zusammen angewendet werden: |A \times (B \cup C)| = |A| * (|B| + |C|)$|A \times (B \cup C)| = |A| * (|B| + |C|)$ für (B \cap C) = \emptyset$(B \cap C) = \emptyset$
• generelle Mengenregeln:
  • für f: A \to B$f: A \to B$, wo jedes Element aus B$B$ genau m$m$ Urbilder in A$A$ hat, gilt |A| = m|B|$|A| = m|B|$
  • wenn f$f$ bijektiv, gilt |A| = |B|$|A| = |B|$
• Schubfachprinzip / pigeon-hole principle:
  • falls man n$n$ Objekte auf m$m$ Mengen verteilt (n, m > 0$n, m > 0$) und n$n$ größer als m$m$ ist, dann gibt es mindestens eine Menge, in der mehr als ein Objekt landet
  • falls man n$n$ Objekte auf m$m$ Mengen verteilt (n, m > 0$n, m > 0$) und n$n$ kleiner als m$m$ ist, dann gibt es mindestens eine Menge, in der kein Objekt landet
  • Verschärfung: verteilt man n$n$ Elemente auf k$k$ Mengen, gibt es mindestens eine Menge, in der sich zumindest \lceil \frac{n}{k} \rceil$\lceil \frac{n}{k} \rceil$ Objekte befinden
  • Beispiele:
    • in einer Gruppe von 3 Personen haben mindestens 2 das gleiche Geschlecht: 2 = \lceil 3 / 2 \rceil$2 = \lceil 3 / 2 \rceil$
    • in einer Gruppe von 13 Personen haben mindestens 2 Personen im selben Monat Geburtstag: 2 = \lceil 13 / 12 \rceil$2 = \lceil 13 / 12 \rceil$
    • es gibt in Deutschland mindestens 415 Menschen, die exakt die gleiche Anzahl von Haaren auf dem Kopf haben: 415 = \lceil 83.000.000 / 200.000 \rceil$415 = \lceil 83.000.000 / 200.000 \rceil$, wobei die Einwohnerzahl Deutschlands 83 Mio. beträgt und die durschnittliche Anzahl der Haare auf dem Kopf 200.000 ist
• Beweistechnik - Doppeltes Abzählen:
  • Inzidenzmatrix: die Summe der Spalten (\sum_{v \in V}deg(v)$\sum_{v \in V}deg(v)$) ist gleich mit der Summe der Zeilen (2|E|$2|E|$) \to$\to$ Beweis des Handschlaglemmas (2|E| = \sum_{v \in V}deg(v)$2|E| = \sum_{v \in V}deg(v)$)
    
• Inklusion und Exklusion
  • z.B. n = 3$n = 3$: |A_1 \cup A_2 \cup A_3| = |A_1| + |A_2| + |A_3| - |A_1 \cap A_2| - |A_1 \cap A_3| - |A_2 \cap A_3| + |A_1 \cap A_2 \cap A_3|$|A_1 \cup A_2 \cup A_3| = |A_1| + |A_2| + |A_3| - |A_1 \cap A_2| - |A_1 \cap A_3| - |A_2 \cap A_3| + |A_1 \cap A_2 \cap A_3|$

Ziehen aus einer Urne: Formeln

• k$k$ Elemente aus einer n$n$-elementigen Menge

	mit Zurücklegen	ohne Zurücklegen
geordnet (mit Reihenfolge)	n^k$n^k$	\frac{n!}{(n-k)!}$\frac{n!}{(n-k)!}$
ungeordnet (ohne Reihenfolge)	{k+n-1}\choose k${k+n-1}\choose k$	n \choose k$n \choose k$

• Urne mit n$n$ Kugeln, ziehe k$k$ Kugeln...
• Ohne Zurücklegen, Mit Reihenfolge: A_{n,k} := \{(s_1, ..., s_k) \in [n]^k | |\{s_1, ..., s_k\}| = k \}$A_{n,k} := \{(s_1, ..., s_k) \in [n]^k | |\{s_1, ..., s_k\}| = k \}$
  • |A_{n,k}| = \frac{n!}{(n-k)!}$|A_{n,k}| = \frac{n!}{(n-k)!}$
  • "k$k$-Tupel mit k$k$ verschiedenen Einträgen aus [n]$[n]$"
  • Tupel ohne Duplikate
• Ohne Zurücklegen, Ohne Reihenfolge: B_{n,k} := \{(s_1, ..., s_k) \in [n]^k : s_1 < s_2 < ... < s_k \}$B_{n,k} := \{(s_1, ..., s_k) \in [n]^k : s_1 < s_2 < ... < s_k \}$
  • |B_{n,k}| = {n \choose k} = \frac{n!}{k!(n-k)!}$|B_{n,k}| = {n \choose k} = \frac{n!}{k!(n-k)!}$
  • "Aufsteigend sortierte k$k$-Tupel mit k$k$ verschiedenen Einträgen aus [n]$[n]$"
  • eindeutige Menge
• Mit Zurücklegen, Ohne Reihenfolge: C_{n,k} := \{(s_1, ..., s_k) \in [n]^k : s_1 \leq s_2 \leq ... \leq s_k \}$C_{n,k} := \{(s_1, ..., s_k) \in [n]^k : s_1 \leq s_2 \leq ... \leq s_k \}$
  • |C_{n,k}| = {n + k - 1 \choose k}$|C_{n,k}| = {n + k - 1 \choose k}$
  • (!) |C_{n,k}| = |D_{k,n}|$|C_{n,k}| = |D_{k,n}|$
  • "Aufsteigend sortierte k$k$-Tupel über [n]$[n]$ mit Wiederholungen"
  • Multimenge
• Mit Zurücklegen, Mit Reihenfolge: \{(s_1, ..., s_k) \in [n]^k \}$\{(s_1, ..., s_k) \in [n]^k \}$
  • Anz. Möglichkeiten = n^k$n^k$
  • Tupel mit Duplikate

Beispielsaufgaben: Ziehen aus einer Urne

• Wie viele mögliche Lottoziehungen gibt es (n$n$ Bälle, k$k$ Ziehungen)? \to |B_{n,k}|$\to |B_{n,k}|$ (ohne Zurücklegen, ohne Reihenfolge)
• Ein Wettbewerb vergibt einen ersten, einen zweiten, ... und einen k$k$-ten Preis. Wie viele Möglichkeiten gibt es, die Preise unter den n$n$ Wettbewerbsteilnehmer zu verteilen? \to |A_{n,k}|$\to |A_{n,k}|$ (ohne Zurücklegen, mit Reihenfolge)
• Wie viele Möglichkeiten gibt es, k$k$ Fußballspiele auf n$n$ Austragungsorte zu verteilen? \to n^k$\to n^k$ (mit Zurücklegen, mit Reihenfolge)
• Wie viele Möglichkeiten gibt es, k$k$ Euro unter n$n$ Personen zu verteilen? \to |C_{n,k}|$\to |C_{n,k}|$ (mit Zurücklegen, ohne Reihenfolge)

Beispielsaufgaben: Möglichkeiten, Buchstaben umzuordnen

• Möglichkeiten, die Buchstaben in ABCDEFGH umzuordnen, so, dass ABC erhalten bleibt
  • gesamte Anzahl an Buchstaben: 8$8$ \to$\to$ Anz. Möglichkeiten, alle Buchstaben umzuordnen, ohne zu beachten, dass ABC erhalten bleibt = 8!$8!$
  • betrachte ABC als 1 Einheit \to$\to$ 5 einzelne Buchstaben, 1 Paar ABC \to$\to$ Anz. Möglichkeiten, alle Buchstaben umzuordnen, ohne dass das Paar ABC verloren geht = 6! = 720$6! = 720$
• Anz. der erhaltenen Wörter aus Permutation von "hallo"
  • wenn man l_1$l_1$ und l_2$l_2$ als unterschiedliche Buchstaben betrachten würde: 5! = 120$5! = 120$ (Wortlänge)
  • jedes Wort würde 2!$2!$ mal auftreten \to$\to$ gesuchter Wert = 5! / 2! = 60$5! / 2! = 60$
• Anz. der erhaltenen Wörter aus Permutation von "bewundernswert"
  • selbes Prinzip \to$\to$ 14! / (3! * 2! * 2! * 2!) = 14! / 48 = 1.816.214.400$14! / (3! * 2! * 2! * 2!) = 14! / 48 = 1.816.214.400$

Stirling-Zahlen 2. Art

• Definition: Anzahl Partitionen von n$n$ Elementen ([n]$[n]$) in k$k$ nicht leere Klassen
  • m.a.W. Anzahl der Äquivalenzrelationen über [n]$[n]$ mit genau k$k$ Klassen
• Notation: S_{n,k} = \left\{ n \atop k \right\}$S_{n,k} = \left\{ n \atop k \right\}$
• Formeln:
  • rekursiv: S_{n,k} = S_{n-1,k-1} + k * S_{n-1,k}$S_{n,k} = S_{n-1,k-1} + k * S_{n-1,k}$
    • Base Cases: S_{n,0} = 0$S_{n,0} = 0$, S_{0,0} = 1$S_{0,0} = 1$ und S_{n,n} = 1$S_{n,n} = 1$
  • geschlossen: S_{n,k} = \frac{1}{k!}\sum_{j=0}^k(-1)^{k-j}{k \choose j}j^n$S_{n,k} = \frac{1}{k!}\sum_{j=0}^k(-1)^{k-j}{k \choose j}j^n$

Anzahl Partitionen bei vorgegebener Klassengröße

• es gilt \sum_{i = 1}^n i * \lambda_i= n$\sum_{i = 1}^n i * \lambda_i= n$
  • z.B. 1 * 3= 1 * 1 + 2 * 1 = 3 * 1$1 * 3= 1 * 1 + 2 * 1 = 3 * 1$
• Anzahl der Partitionen von [n]$[n]$ mit \lambda_i$\lambda_i$ vielen i$i$-elementigen Klassen = \frac{n!}{(1!)^{\lambda_1} * ... * (n!)^{\lambda_n} * \lambda_1! * ... * \lambda_n!}$\frac{n!}{(1!)^{\lambda_1} * ... * (n!)^{\lambda_n} * \lambda_1! * ... * \lambda_n!}$

Stirling-Zahlen 1. Art

• Zykelschreibweise: die einzelnen Tupel beschreiben die Kreise im Graph
  
• Definition: Anzahl Permutationen von n$n$ Elementen ([n]$[n]$) mit genau k$k$ Zyklen
• Notation: s_{n,k} = \left[ n \atop k \right]$s_{n,k} = \left[ n \atop k \right]$
• Formel: s_{n,k} = s_{n-1,k - 1} + (n-1) * s_{n-1,k}$s_{n,k} = s_{n-1,k - 1} + (n-1) * s_{n-1,k}$
  • Base Cases: s_{n,0} = 0$s_{n,0} = 0$, s_{0,0} = 1$s_{0,0} = 1$ und s_{n,n} = 1$s_{n,n} = 1$

Zählvektoren

• |D_{n,k}| = |C_{k,n}| := |\{(s_1, ..., s_k) \in \N_0^k | s_1 + ... + s_k = n \}| = {n + k - 1 \choose n} = {n + k - 1 \choose k - 1}$|D_{n,k}| = |C_{k,n}| := |\{(s_1, ..., s_k) \in \N_0^k | s_1 + ... + s_k = n \}| = {n + k - 1 \choose n} = {n + k - 1 \choose k - 1}$
  • "Zählvektoren mit k$k$ Einträgen und Summe genau n$n$"
  • Eselsbrücke: entspricht der Menge der Wörter, die "n$n$ Strichen und k-1$k-1$ Kommata haben"
• |E_{n,k}| = |D_{n,k+1}| := := |\{(s_1, ..., s_k) \in \N_0^k | s_1 + ... + s_k \leq n \}| = {n + k \choose n}$|E_{n,k}| = |D_{n,k+1}| := := |\{(s_1, ..., s_k) \in \N_0^k | s_1 + ... + s_k \leq n \}| = {n + k \choose n}$
  • "Zählvektoren mit k$k$ Einträgen und Summe höchstens n$n$"
• |F_{n,k}| := |\{(s_1, ..., s_k) \in [n]^k | |\{s_1, ..., s_k\}| = n\}|$|F_{n,k}| := |\{(s_1, ..., s_k) \in [n]^k | |\{s_1, ..., s_k\}| = n\}|$ (n$n$ - Anzahl der Klassen, k$k$ - Anzahl der Objekte)
  • rekursiv: |F_{n,k}| = n! * S_{k,n}$|F_{n,k}| = n! * S_{k,n}$
  • geschlossen: |F_{n,k}| = \sum_{i=0}^n(-1)^{n-i}{n \choose i}i^k$|F_{n,k}| = \sum_{i=0}^n(-1)^{n-i}{n \choose i}i^k$
• |G_{n,k}| := |\{(s_1, ..., s_k) \in \N^k | s_1 + ... + s_k = n \}| = {n - 1 \choose k - 1}$|G_{n,k}| := |\{(s_1, ..., s_k) \in \N^k | s_1 + ... + s_k = n \}| = {n - 1 \choose k - 1}$
  • "sortierte Zählvektoren mit k$k$ Komponenten und Summe genau n$n$"
  • Eselsbrücke: entspricht der Anzahl der Möglichkeiten, k-1$k-1$ Pluszeichen aus insgesamt n-1$n-1$ Pluszeichen zu wählen
  • geordnete Zahlpartition
• |P_{n,k}| := |\{(s_1, ..., s_k) \in \N^k | s_1 + ... + s_k = n, s_1 \leq ... \leq s_k \}|$|P_{n,k}| := |\{(s_1, ..., s_k) \in \N^k | s_1 + ... + s_k = n, s_1 \leq ... \leq s_k \}|$ (Partitionen von n$n$)
  • |P_{n,k}| = |P_{n-1,k-1}| + |P_{n-k,k}|$|P_{n,k}| = |P_{n-1,k-1}| + |P_{n-k,k}|$ für k > 0$k > 0$
  • |P_{n,0}| = 0$|P_{n,0}| = 0$ für n > 0$n > 0$
  • |P_{n,k}| = 0$|P_{n,k}| = 0$ für k > n$k > n$
  • |P_{0,0}| = 1$|P_{0,0}| = 1$
  • |P_{n,n}| = 1$|P_{n,n}| = 1$
• |H_{n,k}| := |\{(s_1, ..., s_k) \in \N_0^k | s_1 + ... + s_k = n, s_1 \leq ... \leq s_k \}| = |P_{n+k,k}|$|H_{n,k}| := |\{(s_1, ..., s_k) \in \N_0^k | s_1 + ... + s_k = n, s_1 \leq ... \leq s_k \}| = |P_{n+k,k}|$
  • Anzahl der Zahlpartitionen von n$n$ in k$k$ positive Summanden
  • ungeordnete Zahlpartition

Beispielsaufgaben: Verteilungsprobleme

• Wie viele Möglichkeiten gibt es, k$k$ Weihnachtsgeschenke unter n$n$ Kindern zu verteilen, so dass jedes Kind mindestens ein Geschenk erhält?
  • Sowohl die Kinder als auch die Geschenke sind unterscheidbar! \to |F_{n,k}|$\to |F_{n,k}|$ (geordnete Partition von [n]$[n]$ in k$k$ Klassen)
• Wie viele Möglichkeiten gibt es, k$k$ Weihnachtsgeschenke in n$n$ Päckchen aufzuteilen, so dass jedes Päckchen mindestens ein Geschenk enthält?
  • Die Päckchen sind nicht unterscheidbar, die Geschenke sind unterscheidbar \to S_{n,k}$\to S_{n,k}$ (ungeordnete Partition von [n]$[n]$ in k$k$ Klassen)
• Wie viele Möglichkeiten gibt es, n$n$ Euromünzen unter k$k$ Kindern zu verteilen, so dass jedes Kind mindestens eine Münze erhält?
  • Die Münzen sich nicht unterscheidbar, die Kinder sind unterscheidbar \to |G_{n,k}|$\to |G_{n,k}|$
• Wie viele Möglichkeiten gibt es, n$n$ Euromünzen in k$k$ Päckchen aufzuteilen, so dass jedes Päckchen mindestens eine Münze enthält?
  • Sowohl die Münzen, als auch die Päckchen sind nicht unterscheidbar! \to |P_{n,k}|$\to |P_{n,k}|$
• Wie viele Möglichkeiten gibt es, n Euro in k Päckchen aufzuteilen, wenn Päckchen auch 0 Euro enthalten dürfen? \to |H_{n,k}| = |P_{n+k,k}|$\to |H_{n,k}| = |P_{n+k,k}|$

Binomialkoeffizient, Binomialformel und Vandermondesche Identität

• Binomialkoeffizient: {n \choose k} = \frac{n!}{k!(n-k)!}${n \choose k} = \frac{n!}{k!(n-k)!}$: Anzahl der k$k$-Elementigen Teilmengen einer n$n$-Elementigen Menge
• Binomialformel: (x+y)^n = \sum_{k=0}^n{n \choose k}x^ky^{n-k}$(x+y)^n = \sum_{k=0}^n{n \choose k}x^ky^{n-k}$
• Vandermondische Identität: {m + n \choose k} = \sum_{i = 0}^k{m \choose i}{n \choose k - i}${m + n \choose k} = \sum_{i = 0}^k{m \choose i}{n \choose k - i}$

Rechenregel für Binomialkoeffizienten

• Pascalsche Identität: {n \choose k} = {{n - 1} \choose {k - 1}} + {{n - 1} \choose {k}}${n \choose k} = {{n - 1} \choose {k - 1}} + {{n - 1} \choose {k}}$
• Symmetrie: {n \choose k} = {{n} \choose {n-k}}${n \choose k} = {{n} \choose {n-k}}$
• Zeilensumme: \sum_{i=0}^n{n \choose i} = 2^n$\sum_{i=0}^n{n \choose i} = 2^n$
• Spaltensumme:\sum_{i=k}^n{i \choose k} = {{n + 1} \choose {k + 1}}$\sum_{i=k}^n{i \choose k} = {{n + 1} \choose {k + 1}}$
• Diagonalsumme: \sum_{i=0}^n{n + i \choose i} = {{n + k + 1} \choose {k}}$\sum_{i=0}^n{n + i \choose i} = {{n + k + 1} \choose {k}}$

Algebra und Gruppentheorie

Teilbarkeit und Primfaktorzerlegung

• Teilbarkeitsrelation (a ist Teiler von b)
  • a | b \leftrightarrow \frac{b}{a} \in \Z$a | b \leftrightarrow \frac{b}{a} \in \Z$ (a teilt b ohne Rest)
• Primzahlen (alle Zahlen, deren Teiler nur 1 und sich selbst sind)
  • \mathbb{P} = \{p \in \N | p > 1 \land \forall n \in \N: n | p \to (n = 1 \lor n = p)\}$\mathbb{P} = \{p \in \N | p > 1 \land \forall n \in \N: n | p \to (n = 1 \lor n = p)\}$
  • jedes p größer als 1 und wenn n Teiler von p ist, dann, dann ist n entweder 1 oder p

GGT und KGV

• ggT(a, b):
  • \prod_{p\in\mathbb{P}} p^{min\{ v_p(a), v_p(b)\}}$\prod_{p\in\mathbb{P}} p^{min\{ v_p(a), v_p(b)\}}$
  • Produkt jedes Primfaktors der beiden Zahlen mit dem jeweiligen minimalen Exponenten (impl. 0 wenn nicht vorhanden in einem der beiden Zerlegungen)
• kgV(a, b):
  • \prod_{p\in\mathbb{P}} p^{max\{ v_p(a), v_p(b)\}}$\prod_{p\in\mathbb{P}} p^{max\{ v_p(a), v_p(b)\}}$
  • Produkt jedes Primfaktors der beiden Zahlen mit dem jeweiligenmaximalen Exponenten
• a * b = ggT(a,b) * kgV(a,b)$a * b = ggT(a,b) * kgV(a,b)$

Modulorechnung

• a \mod N = a - \lfloor \frac{a}{N} \rfloor * N \in \Z_N$a \mod N = a - \lfloor \frac{a}{N} \rfloor * N \in \Z_N$, mit \Z_N := \{0, ..., N-1\}$\Z_N := \{0, ..., N-1\}$
• Wichtige Gruppen (allgemein):
  • \Z_N := \{0, ..., N-1\}$\Z_N := \{0, ..., N-1\}$ (alle möglichen Ergebnisse modulo N)
  • \Z^*_N := \{1..., N-1\}$\Z^*_N := \{1..., N-1\}$ (teilerfremde Ergebnisse modulo N)
  • [N] := \{1, ..., N\}$[N] := \{1, ..., N\}$ (Menge aller natürlichen Zahlen von 1 bis N inkl.)

Restklassen und Kongruenzen

• Restklasse [a]_m$[a]_m$ von a \mod m$a \mod m$: Menge (Äquivalenzklasse) aller Zahlen, die bei Division durch m$m$ (m \in \Z \land m \neq 0$m \in \Z \land m \neq 0$) denselben Rest lassen wie a$a$
  • [a]_m = a + m\Z$[a]_m = a + m\Z$
  • (a \mod m) = (k \mod m)$(a \mod m) = (k \mod m)$ für ein beliebiges k \in Z$k \in Z$
• Kongruenz modulo m \equiv_m$\equiv_m$: Zwei Zahlen a$a$ und b$b$ sind kongruent modulo m$m$, wenn sie bei der Division durch m$m$ beide denselben Rest haben
  • beide Zahlen unterscheiden sich um ein ganzzahliges Vielfaches von m$m$
  • alt. Schreibweise: a \equiv b \mod m$a \equiv b \mod m$

Erweiterter Euklidischer Algorithmus (EEA)

• Verfahren:
  • von oben nach unten: bestimme \lfloor b / a \rfloor$\lfloor b / a \rfloor$, trage Wert von a$a$ in unteren Zeile für b$b$ und den Rest b \mod a$b \mod a$ für a$a$ ein
    • wiederhole so lange, bis b \mod a = 0$b \mod a = 0$
  • von unten nach oben: setze \alpha = 1$\alpha = 1$ und b = 0$b = 0$, dann trage Wert von \alpha_{alt}$\alpha_{alt}$ in der oberen Zeile für \beta$\beta$ und \beta_{alt} - \lfloor b/a \rfloor_{current} * \alpha_{alt}$\beta_{alt} - \lfloor b/a \rfloor_{current} * \alpha_{alt}$ für \alpha$\alpha$ ein
    • wiederhole bis zur obersten Zeile
• multiplikatives Inverse von a in \left< Z^*_n, \cdot_n, 1\right>$\left< Z^*_n, \cdot_n, 1\right>$: \alpha \mod n$\alpha \mod n$
• Test auf ggT: ggT(a,b) = a * \alpha + b * \beta$ggT(a,b) = a * \alpha + b * \beta$
  • Beispiel: a = 5, b = 911$a = 5, b = 911$
    

Teilerfremde Reste modulo N$N$ und Primzahltest

• Teilerfremde Reste modulo N$N$: \Z^*_N := \{ k \in \Z_N | ggT(k, N) = 1 \}$\Z^*_N := \{ k \in \Z_N | ggT(k, N) = 1 \}$
  • Menge aller Zahlen aus \Z_N$\Z_N$, deren größten gemeinsamen Teiler mit N 1 ist / teilerfremd zu N sind
  • Beispiel: Z^*_{15} = \{ 1, 2, 4, 7, 8, 11, 13, 14\}$Z^*_{15} = \{ 1, 2, 4, 7, 8, 11, 13, 14\}$
• Eulerische Phi-Funktion: \varphi(N) := |\Z^*_N| = N * \prod_{p \in \mathbb{P} : p | N} (1-p^{-1})$\varphi(N) := |\Z^*_N| = N * \prod_{p \in \mathbb{P} : p | N} (1-p^{-1})$
  • Kardinalität der Menge der teilerfremden Reste einer Zahl modulo N$N$
    • berechnet, indem man N mit 1 - 1/p$1 - 1/p$ für jeden einzelnen Primfaktor multipliziert
  • (!) \varphi(p) := p - 1$\varphi(p) := p - 1$ für p \in \mathbb{P}$p \in \mathbb{P}$ (alle Zahlen von 1 bis p - 1$p - 1$)
  • (!) \varphi(m * n) = \varphi(m) * \varphi(n)$\varphi(m * n) = \varphi(m) * \varphi(n)$ für ggT(m,n) = 1$ggT(m,n) = 1$
    • gilt auch für mehr als zwei Faktoren, dann ggT(a,b,c,...) = 1$ggT(a,b,c,...) = 1$
  • Beispiel: \varphi(15) = 15 * (1 - \frac{1}{5}) * (1 - \frac{1}{3}) = (5-1)(3-1) = 8$\varphi(15) = 15 * (1 - \frac{1}{5}) * (1 - \frac{1}{3}) = (5-1)(3-1) = 8$
• Primzahltest: a^{p-1} \equiv 1 \mod p$a^{p-1} \equiv 1 \mod p$
  • für N > 2$N > 2$, wähle 1 \leq a < N$1 \leq a < N$ und prüfe:
    • wenn a^{N-1} \equiv 1 \mod N$a^{N-1} \equiv 1 \mod N$, kann N eine Primzahl sein (oder auch nicht, siehe Carmichael-Zahlen)
    • wenn nicht a^{N-1} \equiv 1 \mod N$a^{N-1} \equiv 1 \mod N$, ist N definitiv keine Primzahl

Modulorechnung

• Rechenregeln:
  • (a + b) \mod n = ((a \mod n) + (b \mod n)) \mod n$(a + b) \mod n = ((a \mod n) + (b \mod n)) \mod n$
  • (a \cdot b) \mod n = ((a \mod n) \cdot (b \mod n)) \mod n$(a \cdot b) \mod n = ((a \mod n) \cdot (b \mod n)) \mod n$
  • (a \mod n) \mod n = a \mod n$(a \mod n) \mod n = a \mod n$

Gruppen

Allgemeine Definition

• eine Menge G$G$ mit innerer Verknüpfung G \times G \to G$G \times G \to G$ heißt Gruppe, falls folgendes gilt:

  1. Abgeschlossenheit: G \times G \to G$G \times G \to G$
  2. Assoziativität: \forall \; a,b,c \in G: a \circ (b \circ c) = (a \circ b) \circ c$\forall \; a,b,c \in G: a \circ (b \circ c) = (a \circ b) \circ c$
  3. neutrales Element: \exists \; e \in G: e \circ a = a = a \circ e$\exists \; e \in G: e \circ a = a = a \circ e$ (eindeutig!)
  4. Inverses: \forall \; a \in G \; \exists \; b \in G: a \circ b = e = b \circ a$\forall \; a \in G \; \exists \; b \in G: a \circ b = e = b \circ a$ mit b = a^{-1}$b = a^{-1}$ (eindeutig!)

• eine Gruppe heißt abelsch, wenn diese kommutativ ist (\forall a,b \in G: a + b = b + a$\forall a,b \in G: a + b = b + a$)

• (!) Eigenschaften einer Gruppe \mathbb{G} = \left< \mathbb{G}, \cdot, 1\right>$\mathbb{G} = \left< \mathbb{G}, \cdot, 1\right>$:

  • das Neutrale ist eindeutig
  • das Inverse ist eindeutig
  • (a^{-1})^{-1} = a$(a^{-1})^{-1} = a$ und (ab)^{-1} = b^{-1}a^{-1}$(ab)^{-1} = b^{-1}a^{-1}$
  • Kürzungsregel: Falls ab = ac$ab = ac$ oder ba = ca$ba = ca$, dann b = c$b = c$
  • b = c$b = c$ gdw. ab = ac$ab = ac$ für ein beliebiges a \in \mathbb{G}$a \in \mathbb{G}$
  • b \neq c$b \neq c$ gdw. ab \neq ac$ab \neq ac$ für ein beliebiges a \in \mathbb{G}$a \in \mathbb{G}$

Ordnung eines Elements

• es gilt hier \mathbb{G} = \left< \mathbb{G}, \cdot, 1\right>$\mathbb{G} = \left< \mathbb{G}, \cdot, 1\right>$
• Ordnung eines Elements: kleinste Zahl k \in \N$k \in \N$, so dass a^k$a^k$ das neutrale Element als Ergebnis hat (a \in \mathbb{G}$a \in \mathbb{G}$)
  • ord(a) := min\{ k \in \N | a^k = 1 \}$ord(a) := min\{ k \in \N | a^k = 1 \}$
    • min \emptyset := \infty$min \emptyset := \infty$
    • (*) für additive Gruppen: ord(a) := min\{ k \in \N \;|\; ka = 0 \}$ord(a) := min\{ k \in \N \;|\; ka = 0 \}$
  • (!) ord(a) = ord(a^{-1})$ord(a) = ord(a^{-1})$
  • (!) ord(a)$ord(a)$ muss Teiler von |\mathbb{G}|$|\mathbb{G}|$ sein
• Erzeugnis von a$a$: \left< a \right> := \{ a^k | k \in \Z \} = \{ ... (a^{-1})^2, (a^{-1})^1, 1, a^1, a^2, ...\}$\left< a \right> := \{ a^k | k \in \Z \} = \{ ... (a^{-1})^2, (a^{-1})^1, 1, a^1, a^2, ...\}$
  • (*) für additive Gruppen: \left< a \right> := \{ ka \;|\; k \in \Z \}$\left< a \right> := \{ ka \;|\; k \in \Z \}$
  • (!) \left< a \right> = \left< a^{-1} \right>$\left< a \right> = \left< a^{-1} \right>$
  • (!) ord(a) = |\left< a \right>|$ord(a) = |\left< a \right>|$
• Erzeuger von \mathbb{G}$\mathbb{G}$: a$a$ ist ein Erzeuger von \mathbb{G}$\mathbb{G}$, wenn \left< a\right> = \mathbb{G}$\left< a\right> = \mathbb{G}$
  • (!) um ein Element mit Ordnung d$d$ zu finden: wenn g$g$ ein Erzeuger von \mathbb{G}$\mathbb{G}$ ist (daraus ord(g) = |\mathbb{G}|$ord(g) = |\mathbb{G}|$), dann gilt für jeden Teiler d \; | \; ord(g)$d \; | \; ord(g)$, dass g^{ord(g) / d}$g^{ord(g) / d}$ Ordnung d$d$ hat
• Gruppenexponent von \mathbb{G}$\mathbb{G}$: \lambda_\mathbb{G} = kgV(\{ord(a) \; | \; a \in \mathbb{G}\})$\lambda_\mathbb{G} = kgV(\{ord(a) \; | \; a \in \mathbb{G}\})$
  • \lambda_\mathbb{G}$\lambda_\mathbb{G}$ teilt \mathbb{G}$\mathbb{G}$ ohne Rest
• (!) Eigenschaften:
  • a^{ord(a)} = 1$a^{ord(a)} = 1$
  • a^{-1} = a^{ord(a)-1}$a^{-1} = a^{ord(a)-1}$
  • a^{k} = a^{k\mod ord(a)}$a^{k} = a^{k\mod ord(a)}$ für jedes k \in \Z$k \in \Z$
  • a^{k} = a^{k\mod |\mathbb{G}|}$a^{k} = a^{k\mod |\mathbb{G}|}$ für jedes k \in \Z$k \in \Z$
  • a^{k} = a^{k\mod \lambda_\mathbb{G}}$a^{k} = a^{k\mod \lambda_\mathbb{G}}$ für jedes k \in \Z$k \in \Z$
  • \left< a \right> = \{ 1, a, a^2, ... , a^{ord(a)-1}\}$\left< a \right> = \{ 1, a, a^2, ... , a^{ord(a)-1}\}$
  • |\left< a \right>| = ord(a)$|\left< a \right>| = ord(a)$
  • a^k = a^{k\mod ord(a)}= 1$a^k = a^{k\mod ord(a)}= 1$ gdw. k \mod ord(a) = 0$k \mod ord(a) = 0$ gdw. ord(a) \; | \; k$ord(a) \; | \; k$
  • a^{|\mathbb{G}|} = 1$a^{|\mathbb{G}|} = 1$ für alle a \in \mathbb{G}$a \in \mathbb{G}$, also |\mathbb{G}|\mod ord(a) = 0$|\mathbb{G}|\mod ord(a) = 0$
  • a^{\lambda_\mathbb{G}} = 1$a^{\lambda_\mathbb{G}} = 1$ für alle a \in \mathbb{G}$a \in \mathbb{G}$
• (!) Satz von Euler:
  • Sei \left< \mathbb{\Z^*_n}, \cdot_n, 1\right>$\left< \mathbb{\Z^*_n}, \cdot_n, 1\right>$, dann gilt 1 = a^{|\Z^*_n|} = a^{\varphi(n)}$1 = a^{|\Z^*_n|} = a^{\varphi(n)}$
  • alternativ: a^{\varphi(n)} \equiv_n 1$a^{\varphi(n)} \equiv_n 1$, falls ggT(a,n) = 1$ggT(a,n) = 1$
• (!) Kleiner Fermatscher Satz:
  • Sei \left< \mathbb{\Z^*_p}, \cdot_p, 1\right>$\left< \mathbb{\Z^*_p}, \cdot_p, 1\right>$ für p \in \mathbb{P}$p \in \mathbb{P}$, dann gilt 1 = a^{|\Z^*_p|} = a^{\varphi(p)} = a^{p-1}$1 = a^{|\Z^*_p|} = a^{\varphi(p)} = a^{p-1}$
  • alternativ: a^{p-1} \equiv_p 1$a^{p-1} \equiv_p 1$, falls ggT(a,p) = 1$ggT(a,p) = 1$

Veranschaulichung der Ordnung

• G_{r_a} = (\mathbb{G}, \{ (x,xa) | x \in \mathbb{G} \})$G_{r_a} = (\mathbb{G}, \{ (x,xa) | x \in \mathbb{G} \})$
• x\left<a\right>$x\left<a\right>$: Kreis in G_{r_a}$G_{r_a}$, der x$x$ enthält
• (!) Eigenschaften:
  • Länge des Kreises: ord(a)$ord(a)$
    • jeder Kreis hat die gleiche Länge
  • Anzahl der Kreisen: |\mathbb{G}| \;/ \; ord(a)$|\mathbb{G}| \;/ \; ord(a)$
• (?) Allgemeine Regel: für alle k \geq 3$k \geq 3$ gilt...
  • ...\Z^*_{2^k}$\Z^*_{2^k}$ (teilerfremde Gruppe einer Zweierpotenz) ist nie zyklisch, wird aber stets durch 2 Elemente erzeugt, wobei eines die Ordnung 2^{k-2}$2^{k-2}$, das andere die Ordnung 2 hat
  • ...der Gruppenexponent \lambda$\lambda$ von \Z^*_{2^k}$\Z^*_{2^k}$ ist stets 2^{k-2}$2^{k-2}$
    • z.B: für \Z^*_{16}$\Z^*_{16}$ sind die Erzeuger beispielsweise 3 und 7 (ord(3) = 4$ord(3) = 4$, ord(7) = 2$ord(7) = 2$) und der Gruppenexponent ist 4
  • \Z^*_{2}$\Z^*_{2}$ und \Z^*_{4}$\Z^*_{4}$ sind zyklisch

Untergruppen

• Untergruppe H$H$: nicht leere Teilmenge von \mathbb{G}$\mathbb{G}$, die bezüglich der Operation \cdot$\cdot$ selbst eine Gruppe definiert
• Bezeichnung: H \leq \mathbb{G}$H \leq \mathbb{G}$
• (!) Eigenschaften:
  • H$H$ erbt das Neutrale und die Inversen von \mathbb{G}$\mathbb{G}$
  • H \leq \mathbb{G}$H \leq \mathbb{G}$ gdw. \forall a,b \in H : ab^{-1} \in H$\forall a,b \in H : ab^{-1} \in H$
• (!) Satz von Lagrange: |H|$|H|$ ist stets ein Teiler von |\mathbb{G}|$|\mathbb{G}|$ für H \leq \mathbb{G}$H \leq \mathbb{G}$

Symmetrische Gruppen

• jedes Tupel beschreibt einen Kreis in G_f = ([n], f)$G_f = ([n], f)$
  • Zykel können beliebig angeordnet werden, Fixpunkte (Kreise bzw. Tupel der Länge 1) müssen nicht angegeben werden: (2)(1,3,5)(4) = (3,5,1)(4)(2) = (5,1,3)$(2)(1,3,5)(4) = (3,5,1)(4)(2) = (5,1,3)$
  • Beispiel: Für \pi = [5] \to [5]$\pi = [5] \to [5]$ in \left< S_5, \circ, Id_{[5]} \right>$\left< S_5, \circ, Id_{[5]} \right>$ mit \pi(1) = 2, \pi(2) = 4, \pi(3) = 5, \pi(4) = 1, \pi(5) = 3$\pi(1) = 2, \pi(2) = 4, \pi(3) = 5, \pi(4) = 1, \pi(5) = 3$ folgt \pi = (1,2,4)(3,5)$\pi = (1,2,4)(3,5)$
• l_a(x) = ax$l_a(x) = ax$ und r_a(x) = xa$r_a(x) = xa$ sind Permutationen auf x$x$
• (!) Eigenschaften:
  • |S_n| = n!$|S_n| = n!$
  • ord(\pi)$ord(\pi)$ = kgV der Zykellängen
    • Beispiel (oberes): ord(\pi) = kgV(\{3,2\}) = 6$ord(\pi) = kgV(\{3,2\}) = 6$
  • \lambda_S$\lambda_S$ = kgV aller möglichen Zykellängen
    • Beispiel für S^*_5$S^*_5$: \lambda = kgV(\{1,2,3,4,5\}) = 60$\lambda = kgV(\{1,2,3,4,5\}) = 60$
  • Inverse eines Zyklus: Zyklus umdrehen ((1,2,3)^{-1} = (3,2,1)$(1,2,3)^{-1} = (3,2,1)$)

Zyklische Gruppen

• Zyklische Gruppen: Gruppen, die von einem einzigen Element a$a$ erzeugt werden
  • \left < a\right> = \mathbb{G}$\left < a\right> = \mathbb{G}$
  • a$a$: Generator von \mathbb{G}$\mathbb{G}$
  • jede zyklische Gruppe ist kommutativ (a^k \cdot a^l = a^{k+l} = a^l \cdot a^k$a^k \cdot a^l = a^{k+l} = a^l \cdot a^k$)
• (!) Eigenschaften:
  • a$a$ ist ein Erzeuger von \mathbb{G}$\mathbb{G}$ gdw. a^{|\mathbb{G}| / p} \neq 1$a^{|\mathbb{G}| / p} \neq 1$ für jeden Primfaktor p$p$ von |\mathbb{G}|$|\mathbb{G}|$
  • jede Gruppe mit |\mathbb{G}| \in \mathbb{P}$|\mathbb{G}| \in \mathbb{P}$ ist zyklisch
  • jede Untergruppe H \leq \mathbb{G}$H \leq \mathbb{G}$ einer zyklischen Gruppe ist zyklisch
  • \lambda = |\mathbb{G}|$\lambda = |\mathbb{G}|$