Diskrete Mathematik

Voraussetzung: $m_1, \ldots, m_k \geq 2$ paarweise teilerfremd$,$ $M = m_1 \cdots m_k,$ $M_i = \tfrac{M}{m_i},$ $M_i \, y_i \equiv 1 \!\!\pmod{m_i}$

$x$

gesuchte ganze Zahl

$a_i$

vorgegebener Rest modulo m_i

$m_i$

Moduln, paarweise teilerfremd

$M$

Produkt aller Moduln

$M_i$

Produkt aller Moduln außer m_i

$y_i$

Inverses von M_i modulo m_i

Simultane Kongruenzen mit paarweise teilerfremden Moduln haben genau eine Lösung modulo dem Produkt der Moduln.

$A, B$

Aussagen, die wahr oder falsch sind

$\neg$

Negation, „nicht“

$\wedge, \vee$

Konjunktion „und“ sowie Disjunktion „oder“ (nicht ausschließend)

$\Leftrightarrow$

logische Äquivalenz, beide Seiten haben immer denselben Wahrheitswert

Eine verneinte Und-Aussage wird zu einer Oder-Aussage der Verneinungen und umgekehrt.

Voraussetzung: $A, B \subseteq \Omega,$ $\overline{A} = \Omega \setminus A$

$A, B$

Teilmengen einer Grundmenge Ω

$\Omega$

Grundmenge, bezüglich der das Komplement gebildet wird

$\overline{A}$

Komplement von A, alle Elemente von Ω, die nicht in A liegen

$\cup, \cap$

Vereinigung und Schnitt

Das Komplement einer Vereinigung ist der Schnitt der Komplemente, das Komplement eines Schnitts die Vereinigung der Komplemente.

Voraussetzung: $a, b \in \mathbb{Z},$ $(a, b) \neq (0, 0),$ $s, t \in \mathbb{Z}$

$a, b$

ganze Zahlen, nicht beide null

$\operatorname{ggT}(a, b)$

größter gemeinsamer Teiler von a und b

$s, t$

ganzzahlige Bézout-Koeffizienten, die der erweiterte Algorithmus liefert

Der ggT zweier Zahlen lässt sich als ganzzahlige Kombination s·a + t·b schreiben; s und t liefert der erweiterte Algorithmus.

Voraussetzung: $a, b \in \mathbb{N}_0;$ $b \geq 1$ in der ersten, $a \geq 1$ in der zweiten Gleichung

$a, b$

natürliche Zahlen, deren größter gemeinsamer Teiler gesucht ist

$\operatorname{ggT}(a, b)$

größter gemeinsamer Teiler von a und b

$a \bmod b$

Rest bei der Division von a durch b, eine Zahl zwischen 0 und b−1

Der ggT zweier Zahlen ändert sich nicht, wenn man die größere durch ihren Rest bei Division durch die kleinere ersetzt.

Voraussetzung: $n \in \mathbb{N},$ $n \geq 1;$ Produkt über die verschiedenen Primteiler $p$ von $n$

$\varphi(n)$

Anzahl der Zahlen k mit 1 ≤ k ≤ n und ggT(k, n) = 1

$n$

natürliche Zahl ab 1

$p$

die verschiedenen Primzahlen, die n teilen (jede nur einmal)

φ(n) zählt die zu n teilerfremden Zahlen von 1 bis n und ergibt sich aus den verschiedenen Primteilern von n.

Voraussetzung: konvexes Polyeder (allgemein: Polyeder ohne Löcher)

$E$

Anzahl der Ecken

$K$

Anzahl der Kanten

$F$

Anzahl der Flächen

Bei jedem konvexen Polyeder ergibt Ecken minus Kanten plus Flächen immer 2.

Voraussetzung: $n \in \mathbb{N}_0$

$D_n$

Anzahl der Permutationen von n Elementen, bei denen kein Element an seiner Stelle bleibt (Subfakultät !n)

$n$

Anzahl der Elemente

$n!$

Anzahl aller Permutationen von n Elementen

$j$

Summationsindex

Die Anzahl der Permutationen von n Elementen ohne Fixpunkt ist n! mal die alternierende Summe der Kehrwerte von 0! bis n!.

Voraussetzung: $n \in \mathbb{N}_0,$ $F_0 = 0,$ $F_1 = 1,$ $F_{n+1} = F_n + F_{n-1}$

$F_n$

n-te Fibonacci-Zahl

$n$

Index, natürliche Zahl einschließlich 0

$\tfrac{1+\sqrt{5}}{2}$

goldener Schnitt Φ ≈ 1,618

$\tfrac{1-\sqrt{5}}{2}$

zweite Lösung ψ ≈ −0,618 der Gleichung x² = x + 1

Die Formel von Binet berechnet die n-te Fibonacci-Zahl direkt aus Potenzen des goldenen Schnitts.

Voraussetzung: $G = (V, E)$ endlicher ungerichteter Graph; Schleifen zählen beim Grad doppelt

$G = (V, E)$

Graph mit Knotenmenge V und Kantenmenge E

$\deg(v)$

Grad des Knotens v, die Anzahl der Kanten, die an v enden

$|E|$

Anzahl der Kanten

In jedem endlichen ungerichteten Graphen ist die Summe aller Knotengrade doppelt so groß wie die Anzahl der Kanten.

Voraussetzung: $A_1, \ldots, A_n$ endliche Mengen$,$ $n \geq 1$

$A_1, \ldots, A_n$

endliche Mengen

$I$

nichtleere Auswahl von Indizes, über die geschnitten wird

$|I|$

Anzahl der ausgewählten Mengen; sie bestimmt das Vorzeichen

$|M|$

Mächtigkeit, also Anzahl der Elemente einer Menge M

Die Größe einer Vereinigung erhält man, indem man Schnitte ungerader Ordnung addiert und Schnitte gerader Ordnung abzieht.

Voraussetzung: $p$ Primzahl$,$ $a \in \mathbb{Z},$ $p \nmid a$

$p$

Primzahl, die als Modul dient

$a$

ganze Zahl, die nicht durch p teilbar ist

Für jede Primzahl p und jede nicht durch p teilbare Zahl a lässt a hoch p−1 bei Division durch p den Rest 1.

Voraussetzung: $p, q \in \mathbb{R},$ $q \neq 0,$ $\lambda_1 \neq \lambda_2$ Lösungen von $\lambda^2 = p\lambda + q,$ $n \geq 2$ in der Rekursion

$a_n$

n-tes Folgenglied

$p, q$

konstante Koeffizienten der Rekursion

$\lambda_1, \lambda_2$

verschiedene Lösungen der charakteristischen Gleichung λ² = pλ + q, eventuell komplex

$c_1, c_2$

Konstanten, die aus den Startwerten a₀ und a₁ bestimmt werden

Eine lineare Rekursion zweiter Ordnung löst man über die Nullstellen der charakteristischen Gleichung λ² = pλ + q.

Voraussetzung: $M$ endliche Menge

$M$

endliche Menge

$\mathcal{P}(M)$

Potenzmenge von M, die Menge aller Teilmengen von M

$|M|$

Mächtigkeit, also Anzahl der Elemente von M

Eine Menge mit n Elementen hat genau 2ⁿ Teilmengen, die leere Menge und die Menge selbst eingeschlossen.

Voraussetzung: $n, k \in \mathbb{N}_0;$ $\binom{n}{k} = 0$ für $k > n$

$\binom{n}{k}$

Binomialkoeffizient „n über k“, Anzahl der k-elementigen Teilmengen einer n-elementigen Menge

$n$

Größe der Grundmenge

$k$

Größe der ausgewählten Teilmenge

Die Pascalsche Regel und verwandte Identitäten erlauben, Binomialkoeffizienten ohne Fakultäten zu berechnen und Summen zu vereinfachen.

Voraussetzung: $a, a', b, b' \in \mathbb{Z},$ $m \in \mathbb{N},$ $m \geq 2$

$a, b$

ganze Zahlen

$a', b'$

ganze Zahlen mit demselben Rest modulo m wie a bzw. b

$m$

Modul, die natürliche Zahl, durch die geteilt wird

$a \equiv b \pmod m$

a ist kongruent zu b modulo m, das heißt m teilt a − b

Summen, Differenzen, Produkte und Potenzen darf man modulo m mit beliebigen Vertretern gleichen Rests ausrechnen.

Voraussetzung: $m \in \mathbb{N},$ $m \geq 2,$ $a \in \mathbb{Z},$ $\operatorname{ggT}(a, m) = 1$

$a$

ganze Zahl, teilerfremd zu m

$m$

Modul, natürliche Zahl ab 2

$\varphi(m)$

Eulersche φ-Funktion, Anzahl der zu m teilerfremden Zahlen von 1 bis m

Ist a teilerfremd zu m, dann lässt a hoch φ(m) bei Division durch m den Rest 1.

Voraussetzung: $n, k \in \mathbb{N},$ $k \geq 1,$ $n_1, \ldots, n_k \in \mathbb{N}_0$

$n$

Anzahl der verteilten Objekte

$k$

Anzahl der Fächer

$n_j$

Anzahl der Objekte im Fach j

$\left\lceil x \right\rceil$

Aufrundung, die kleinste ganze Zahl größer oder gleich x

Verteilt man n Objekte auf k Fächer, liegen in mindestens einem Fach mindestens n/k aufgerundet Objekte.

Voraussetzung: $n, k \in \mathbb{N},$ $1 \leq n \leq k;$ Kugeln gleich, Urnen unterscheidbar, keine Urne leer

$k$

Anzahl der gleichen (nicht unterscheidbaren) Kugeln

$n$

Anzahl der unterscheidbaren Urnen

$x_j$

Anzahl der Kugeln in Urne j, mindestens 1

$\binom{k-1}{n-1}$

Binomialkoeffizient, Anzahl der Verteilungen

k gleiche Kugeln lassen sich auf (k−1 über n−1) Arten so auf n Urnen verteilen, dass keine Urne leer bleibt.

Voraussetzung: $n, n_0 \in \mathbb{Z},$ $A(n)$ Aussage für jedes ganze $n \geq n_0$

$A(n)$

Aussage, die von der ganzen Zahl n abhängt

$n_0$

Startwert, ab dem die Aussage gelten soll (meist 0 oder 1)

$A(n_0)$

Induktionsanfang, die Aussage für den Startwert

$A(n) \Rightarrow A(n+1)$

Induktionsschritt, aus der Gültigkeit für n folgt die für n+1

Gilt eine Aussage für einen Startwert und folgt sie stets von n auf n+1, dann gilt sie für alle n ab dem Startwert.