Spickzettel

Anbei mein handgeschriebener Spickzettel für die Klausur. Leider war der Text sehr klein bzw. an manchen Stellen unleserlich. Nichtsdestotrotz hat er mir sehr geholfen. Vielleicht hilft er Anderen auch weiter.

ILIAS Lösungen

Meine Rechenwege zu den ILIAS-Probeübungen.

Binomischer Lehrsatz

Lemma 1.9 (Binomischer Lehrsatz). Seien \(x\) und \(y\) Unbestimmte oder Zahlen, die kommutieren, d.h. \(xy = yx\). Dann gilt für alle \(n \in \mathbb{N}\): \[(x+y)^n = \sum_{i=0}^{n} \binom{n}{i} x^{n-i}y^i\]

Aufgabe 2 (e)

Bestimmen Sie den Koeffizienten von \(x^5\) in \((2x-3)^8\)

Lösung.

Nach dem Binomischen Lehrsatz ist \[(2x-3)^8 = \sum_{i=0}^{8} \binom{8}{i} (2x)^{8-i} (-3)^i.\] \(5 = 8-i \iff i=3,\) somit erhält man den Koeffizienten für \(x^5\) durch \[\binom{8}{3} \cdot 2^5 \cdot (-3)^3 = 56 \cdot 32 \cdot -27 = -48384.\]

Algebraische Strukturen

Teilbarkeit

Quersummenregel

Der ultimative Life-Hack, wenn man bei der Primfaktorzerlegung stecken ist.

• Eine Zahl ist durch \(3\) teilbar, wenn die Quersumme durch \(3\) teilbar ist.
• Eine Zahl ist durch \(9\) teilbar, wenn die Quersumme durch \(9\) teilbar ist.

Beispiel: auf erstem Blick erscheint \(441\) wie eine Primzahl, da aber \(4+4+1 = 9\) ist die Zahl durch \(9\) teilbar.

Definition 4.12. Sei \(n \in \mathbb{N}\). Die Menge \[\mathbb{Z}^*_n = \{\overline{a} \mid \gcd{(a,n)} = 1\} \subseteq \mathbb{Z}_n\] enthält nach Satz 4.11 die invertierbaren Elemente von \(\mathbb{Z}_n\).

Graphentheorie

Satz 3.5. Sei \(G = (E, K)\) ein (Multi-)Graph. Dann gilt:

1. \(\sum_{v \in E} \deg{v} = 2 |K|\)
2. Die Anzahl der Ecken mit ungeradem Grad ist gerade.

Zusammenhängende Graphen

Definition 3.10. Ein (Multi-)Graph \(G = (E, K)\) heißt zusammenhängend, wenn je zwei Ecken \(u, v \in E\) durch einen Weg verbunden werden können, d.h. es gibt einen Weg \(u_1, \dots, u_s\) in G mit \(u_1 = u\) und \(u_s = v\).

Rekursionsgleichungen

Der Unterschied zwischen homogen und inhomogen ist nur, dass eine inhomogenene Rekursionsgleichung eine Konstante hinzugefügt hat. Beispielsweise ist \(x_n = 2 x_{n-1} + 3\) inhomogen.

Die Ordnung wird durch die anzahl der \(x_{k-\dots}\) bestimmt. Beispielsweise ist \(x_n = 3 x_{n-1} + x_{n-2}\) eine Rekursionsgleichung der 2. Ordnung.

Erste Ordnung lösen

Sei \(x_0 = b_0, x_n = c x_{n-1} +b_1\) für \(n \geq 1\). Dann gilt: \begin{equation} x_n = \begin{cases} c^n b_0 & b_1 = 0\\ b_0 + n b_1 & c=1\\ c^n b_0 + \frac{c^n - 1}{c-1} b_1 & c \neq 1 \end{cases} \end{equation}

Kombinatorik & Zählprobleme

Inklusion und Exklusion

Für zwei Mengen

\begin{equation} |A \cup B| = |A| + |B| - |A \cap B| \end{equation}

Für drei Mengen

\begin{equation} |A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C| \end{equation}

Klausuraufgabe (SoSe 2023)

Wie viele 0-1-Folgen der Länge 7 gibt es, die mit 000 beginnen oder mit 10 enden? (Hinweis: Beides ist auch erlaubt.) Ergebnis bitte in Dezimaldarstellung angeben.

Stirling Zahlen

…der Ersten Art

Definition 1.18

Für \(n \in \mathbb{N}, k \in \mathbb{N}_0\) sei \(s_{n,k}\) die Anzahl der Permutationen in \(S_n\) mit genau \(k\) Zykeln in der Zykelschreibweise. Außerdem setzen wir \(s_{0,0} = 1.\)

Eigenschaften

Proposition 1.19

1. Für \(n < k\) ist \(s_{n,k} = 0.\)
2. \(s_{n,0} = 0\) und \(s_{n,n} = 1\) für alle \(n \in \mathbb{N}.\)
3. Für alle \(n \in \mathbb{N}\) gilt:
   1. \(s_{n,1} = (n − 1)!\)
   2. \(s_{n,n−1} = \binom{n}{2}\)
4. \(\sum_{k=1}^n s_{n,k} = n!\)

Code Beispiel

#!/bin/env python
from math import comb, factorial


def stirling(n: int, k: int) -> int:
    if n < k:
        return 0
    if k == 0:
        return 0
    if n == k:
        return 1
    if k == 1:
        return factorial(n - 1)
    if k == n - 1:
        return comb(n, 2)

    return stirling(n - 1, k - 1) + (n - 1) * stirling(n - 1, k)


if __name__ == "__main__":
    n = int(input())
    k = int(input())
    s = stirling(n, k)
    print(s)

…der Zweiten Art

Gegeben einer Menge \(\{x_1, \dots x_n\}\), zähle die Anzahl von Möglichkeiten diese auf \(k\) Partitionen aufzuteilen.