Mathematics Discrete Mathematics Syllabus

What three properties define a partial order relation?

It must be reflexive, antisymmetric, and transitive.

Distinguish among injective, surjective, and bijective functions.

Injective (one-to-one): distinct inputs give distinct outputs. Surjective (onto): every element of the codomain is hit. Bijective: both injective and surjective.

State the pigeonhole principle.

If $n$ objects are placed into $k$ boxes and $n > k$, then at least one box contains at least two objects. More generally, some box contains at least $\lceil n/k \rceil$ objects.

State the formula for the number of permutations of $n$ distinct objects taken $r$ at a time.

$P(n,r) = \dfrac{n!}{(n-r)!}$.

State the formula for the number of combinations of $n$ objects taken $r$ at a time.

$C(n,r) = \binom{n}{r} = \dfrac{n!}{r!\,(n-r)!}$.

State the binomial theorem.

$(x+y)^{n} = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^{k}$.

State Pascal's identity for binomial coefficients.

$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$.

How many ways can $r$ objects be chosen from $n$ types with repetition allowed (combinations with repetition)?

$\binom{n+r-1}{r}$.

What are the two steps of a proof by mathematical induction?

Base case: prove $P(n_0)$ holds (often $n_0 = 1$). Inductive step: assume $P(k)$ (the inductive hypothesis) and prove $P(k+1)$.

State the sum of the first $n$ positive integers.

$\sum_{i=1}^{n} i = \dfrac{n(n+1)}{2}$.

State the formula for the sum of a finite geometric series $\sum_{i=0}^{n} ar^{i}$ with $r \neq 1$.

$\sum_{i=0}^{n} ar^{i} = \dfrac{a(r^{n+1}-1)}{r-1}$.

Define what it means for an integer $a$ to divide an integer $b$.

$a \mid b$ means there exists an integer $k$ such that $b = ak$, where $a \neq 0$.

State the division algorithm for integers.

For integers $a$ and $d > 0$, there exist unique integers $q$ (quotient) and $r$ (remainder) with $a = dq + r$ and $0 \leq r < d$.

What does $a \equiv b \pmod{m}$ mean?

$a$ is congruent to $b$ modulo $m$, meaning $m \mid (a - b)$, i.e. $a$ and $b$ have the same remainder when divided by $m$.

State Fermat's little theorem.

If $p$ is prime and $p \nmid a$, then $a^{p-1} \equiv 1 \pmod{p}$. Equivalently, $a^{p} \equiv a \pmod{p}$ for all integers $a$.

What is the relationship between $\gcd(a,b)$ and $\mathrm{lcm}(a,b)$?

$\gcd(a,b) \cdot \mathrm{lcm}(a,b) = |a \cdot b|$.

What does the Euclidean algorithm compute, and on what identity is it based?

It computes $\gcd(a,b)$ using the identity $\gcd(a,b) = \gcd(b,\, a \bmod b)$, repeating until the remainder is $0$.

Define a simple graph and distinguish it from a multigraph.

A simple graph has no loops and no multiple edges between the same pair of vertices. A multigraph allows multiple (parallel) edges between vertices.

State the handshaking lemma (degree-sum formula).

The sum of the degrees of all vertices equals twice the number of edges: $\sum_{v \in V} \deg(v) = 2|E|$.

How many edges does a complete graph $K_n$ have?

$\dbinom{n}{2} = \dfrac{n(n-1)}{2}$ edges.

State the condition for a connected graph to have an Euler circuit.

A connected graph has an Euler circuit if and only if every vertex has even degree.

State the condition for a connected graph to have an Euler path (but not circuit).

A connected graph has an Euler path if and only if it has exactly two vertices of odd degree (the path starts at one and ends at the other).

What is a Hamiltonian cycle in a graph?

A Hamiltonian cycle is a closed cycle that visits every vertex of the graph exactly once (returning to the start).

How many edges does a tree with $n$ vertices have?

A tree with $n$ vertices has exactly $n - 1$ edges.

State Euler's formula relating vertices, edges, and faces of a connected planar graph.

$V - E + F = 2$, where $V$, $E$, and $F$ are the numbers of vertices, edges, and faces.

Define a bipartite graph.

A graph is bipartite if its vertex set can be split into two disjoint sets $V_1$ and $V_2$ such that every edge connects a vertex in $V_1$ to one in $V_2$ (no edge lies within a single set).

What characterizes a graph as bipartite in terms of cycles?

A graph is bipartite if and only if it contains no cycle of odd length.

What is the chromatic number of a graph?

The chromatic number $\chi(G)$ is the minimum number of colors needed to color the vertices so that no two adjacent vertices share the same color.

State the recurrence relation that defines the Fibonacci sequence.

$F_n = F_{n-1} + F_{n-2}$ for $n \geq 2$, with initial conditions $F_0 = 0$ and $F_1 = 1$.

What is the closed-form count of functions from a set of size $m$ to a set of size $n$?

There are $n^{m}$ functions from an $m$-element set to an $n$-element set.