Mathematics Discrete Mathematics Flashcards

24 sample cards from the Discrete Mathematics deck

Sampled from the end of the deck, so these are different cards from the ones shown on the syllabus page.

1. State Pascal's identity for binomial coefficients.

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

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

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

3. 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)$.

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

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

5. 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}$.

6. 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$.

7. 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$.

8. 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$.

9. 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$.

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

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

11. 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$.

12. 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.

13. 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|$.

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

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

15. 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.

16. 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).

17. 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).

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

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

19. 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.

20. 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).

21. 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.

22. 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.

23. 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$.

24. 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.

What this deck covers

Discrete Mathematics flashcards FAQ