Discrete Mathematics: Counting, Combinatorics, Graph Theory, and Relations

Vocabulary flashcards covering key definitions, principles, formulas, and concepts from Sections 3.1 through 3.10 of the discrete mathematics lecture notes.

Binomial Coefficient ($\binom{n}{k}$)

The number of subsets of size $k$ chosen from a set of size $n$, pronounced "$n$ choose $k$".

Pascal’s Identity

The recurrence relation $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ defining entry $k$ of row $n$ in Pascal's Triangle as the sum of the two entries above it.

Binomial Theorem

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

Bit String

A sequence consisting entirely of binary digits ($0$s and $1$s).

Weight of a Bit String

The number of $1$s contained in a given bit string.

Lattice Path

A sequence of steps along a grid (typically moving only right $R$ or up $U$) connecting two points $(x_1, y_1)$ to $(x_2, y_2)$.

Additive Principle (Sum Rule)

If event $A$ can occur in $m$ ways and event $B$ in $n$ ways, and $A$ and $B$ cannot occur together, then choosing $A$ or $B$ can occur in $m + n$ ways.

Multiplicative Principle (Product Rule)

If a task consists of two independent sequential steps where step 1 has $m$ outcomes and step 2 has $n$ outcomes, then there are $m \times n$ total outcomes.

Function ($f: A \rightarrow B$)

A relation mapping every element in set $A$ (domain) to exactly one element in set $B$ (codomain).

Injective (One-to-One) Function

A function where distinct domain elements map to distinct codomain elements; i.e., $f(a) \ne f(b)$ whenever $a \ne b$.

Surjective (Onto) Function

A function where every element in the codomain $B$ has at least one pre-image in the domain $A$.

Bijection

A function that is both injective and surjective (a one-to-one correspondence).

Disjoint Sets

Two or more sets that have no elements in common ($A \cap B = \emptyset$).

Principle of Inclusion-Exclusion (PIE)

A counting technique to find the size of the union of multiple overlapping sets by adding individual set sizes, subtracting pair intersections, adding triple intersections, and alternating signs.

Complementary Counting

A strategy calculating the size of a set $A$ by subtracting its complement $A^c$ from the universal set $U$ ($|A| = |U| - |A^c|$).

Derangement

A permutation of a set of objects in which no object appears in its original position.

Permutation ($P(n, k)$)

An ordered arrangement of $k$ distinct elements selected from a set of $n$ elements without repetition.

Combination ($\binom{n}{k}$)

An unordered selection of $k$ distinct elements chosen from a set of $n$ elements without repetition.

Factorial ($n!$)

The product of all positive integers less than or equal to $n$, defined as $n! = n \times (n-1) \times \dots \times 1$ with $0! = 1$.

Quotient Principle

The rule stating that if a set $A$ of size $N$ can be partitioned into $k$-element disjoint equivalence classes, there are $N/k$ distinct classes.

Multiset

A set-like collection where elements are allowed to appear more than once.

Stars and Bars

A combinatorial method used to count distributions of $n$ identical items into $k$ distinct categories, given by $\binom{n+k-1}{k-1}$.

Non-negative Integer Solution

An assignment of values to variables $x_1, x_2, \dots, x_k \ge 0$ satisfying $x_1 + x_2 + \dots + x_k = n$.

Proper Vertex Coloring

An assignment of colors to the vertices of a graph such that no two adjacent vertices share the same color.

Chromatic Number ($\chi(G)$)

The minimum number of colors required to form a proper vertex coloring of graph $G$.

Bipartite Graph

A graph whose vertices can be partitioned into two disjoint sets $V_1, V_2$ such that every edge connects a vertex in $V_1$ to a vertex in $V_2$ ($\chi(G) \le 2$).

Complete Graph ($K_n$)

A simple graph containing $n$ vertices where every pair of distinct vertices is connected by an edge.

Cycle Graph ($C_n$)

A graph consisting of a single closed loop of $n$ vertices and $n$ edges.

Eulerian Path

A continuous walk in a graph that traverses every edge exactly once.

Eulerian Circuit (Eulerian Cycle)

An Eulerian path that starts and ends on the same vertex.

Degree of a Vertex

The number of edges incident (connected) to a vertex.

Bridge (Cut-Edge)

An edge whose removal increases the number of connected components in a graph (disconnects the graph).

Fleury’s Algorithm

An algorithm for constructing Eulerian paths/circuits that avoids choosing bridge edges unless no other edge is available.

Matching

A set of independent edges in a graph such that no two edges share a vertex.

Perfect Matching

A matching that covers every vertex of the graph.

Blocking Pair (Instability)

A pair $(A, B)$ not matched to each other where $A$ prefers $B$ over their assigned partner, and $B$ prefers $A$ over their assigned partner.

Stable Matching

A matching that contains zero blocking pairs.

Gale-Shapley Algorithm

An iterative propose-and-reject algorithm that guarantees a stable matching between two equal-sized sets of agents.

Proposer-Optimal / Receiver-Pessimistic

A property of the Gale-Shapley algorithm where proposers receive the best possible valid partner they could have in any stable matching, while receivers receive their worst possible valid partner.

Binary Relation

A subset $R$ of the Cartesian product $A \times B$ (or $A \times A$ for a relation on a set $A$), consisting of ordered pairs $(a, b)$ where $a \in A$ and $b \in B$. We write $aRb$ to mean $(a, b) \in R$.

Reflexive Property

A relation $R$ on set $A$ is reflexive if $aRa$ for every element $a \in A$.

Symmetric Property

A relation $R$ on set $A$ is symmetric if whenever $aRb$, then $bRa$ for all $a, b \in A$.

Transitive Property

A relation $R$ on set $A$ is transitive if whenever $aRb$ and $bRc$, then $aRc$ for all $a, b, c \in A$.

Antisymmetric Property

A relation $R$ on set $A$ is antisymmetric if whenever $aRb$ and $bRa$, then $a = b$.

Equivalence Relation

A relation $R$ on set $A$ that satisfies all three properties simultaneously: reflexive, symmetric, and transitive.

Equivalence Class ($[a]$)

The set of all elements in $A$ related to $a$ under an equivalence relation $R$, defined as $[a] = \{x \in A \mid aRx\}$.

Partition of a Set

A collection of non-empty, pairwise disjoint subsets of $A$ whose union is $A$. Every equivalence relation on $A$ uniquely partitions $A$ into its equivalence classes.

Binomial Coefficient ($\binom{n}{k}$)

The number of subsets of size $k$ chosen from a set of size $n$, pronounced "$n$ choose $k$".

Pascal’s Identity

The recurrence relation $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ defining entry $k$ of row $n$ in Pascal's Triangle as the sum of the two entries above it.

Binomial Theorem

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

Bit String

A sequence consisting entirely of binary digits ($0$s and $1$s).

Weight of a Bit String

The number of $1$s contained in a given bit string.

Lattice Path

A sequence of steps along a grid (typically moving only right $R$ or up $U$) connecting two points $(x_1, y_1)$ to $(x_2, y_2)$.

Additive Principle (Sum Rule)

If event $A$ can occur in $m$ ways and event $B$ in $n$ ways, and $A$ and $B$ cannot occur together, then choosing $A$ or $B$ can occur in $m + n$ ways.

Multiplicative Principle (Product Rule)

If a task consists of two independent sequential steps where step 1 has $m$ outcomes and step 2 has $n$ outcomes, then there are $m \times n$ total outcomes.

Function ($f: A \rightarrow B$)

A relation mapping every element in set $A$ (domain) to exactly one element in set $B$ (codomain).

Injective (One-to-One) Function

A function where distinct domain elements map to distinct codomain elements; i.e., $f(a) \ne f(b)$ whenever $a \ne b$.

Surjective (Onto) Function

A function where every element in the codomain $B$ has at least one pre-image in the domain $A$.

Bijection

A function that is both injective and surjective (a one-to-one correspondence).

Disjoint Sets

Two or more sets that have no elements in common ($A \cap B = \emptyset$).

Principle of Inclusion-Exclusion (PIE)

A counting technique to find the size of the union of multiple overlapping sets by adding individual set sizes, subtracting pair intersections, adding triple intersections, and alternating signs.

Complementary Counting

A strategy calculating the size of a set $A$ by subtracting its complement $A^c$ from the universal set $U$ ($|A| = |U| - |A^c|$).

Derangement

A permutation of a set of objects in which no object appears in its original position.

Permutation ($P(n, k)$)

An ordered arrangement of $k$ distinct elements selected from a set of $n$ elements without repetition.

Combination ($\binom{n}{k}$)

An unordered selection of $k$ distinct elements chosen from a set of $n$ elements without repetition.

Factorial ($n!$)

The product of all positive integers less than or equal to $n$, defined as $n! = n \times (n-1) \times \dots \times 1$ with $0! = 1$.

Quotient Principle

The rule stating that if a set $A$ of size $N$ can be partitioned into $k$-element disjoint equivalence classes, there are $N/k$ distinct classes.

Multiset

A set-like collection where elements are allowed to appear more than once.

Stars and Bars

A combinatorial method used to count distributions of $n$ identical items into $k$ distinct categories, given by $\binom{n+k-1}{k-1}$.

Non-negative Integer Solution

An assignment of values to variables $x_1, x_2, \dots, x_k \ge 0$ satisfying $x_1 + x_2 + \dots + x_k = n$.

Proper Vertex Coloring

An assignment of colors to the vertices of a graph such that no two adjacent vertices share the same color.

Chromatic Number ($\chi(G)$)

The minimum number of colors required to form a proper vertex coloring of graph $G$.

Bipartite Graph

A graph whose vertices can be partitioned into two disjoint sets $V_1, V_2$ such that every edge connects a vertex in $V_1$ to a vertex in $V_2$ ($\chi(G) \le 2$).

Complete Graph ($K_n$)

A simple graph containing $n$ vertices where every pair of distinct vertices is connected by an edge.

Cycle Graph ($C_n$)

A graph consisting of a single closed loop of $n$ vertices and $n$ edges.

Eulerian Path

A continuous walk in a graph that traverses every edge exactly once.

Eulerian Circuit (Eulerian Cycle)

An Eulerian path that starts and ends on the same vertex.

Degree of a Vertex

The number of edges incident (connected) to a vertex.

Bridge (Cut-Edge)

An edge whose removal increases the number of connected components in a graph (disconnects the graph).

Fleury’s Algorithm

An algorithm for constructing Eulerian paths/circuits that avoids choosing bridge edges unless no other edge is available.

Matching

A set of independent edges in a graph such that no two edges share a vertex.

Perfect Matching

A matching that covers every vertex of the graph.

Blocking Pair (Instability)

A pair $(A, B)$ not matched to each other where $A$ prefers $B$ over their assigned partner, and $B$ prefers $A$ over their assigned partner.

Stable Matching

A matching that contains zero blocking pairs.

Gale-Shapley Algorithm

An iterative propose-and-reject algorithm that guarantees a stable matching between two equal-sized sets of agents.

Proposer-Optimal / Receiver-Pessimistic

A property of the Gale-Shapley algorithm where proposers receive the best possible valid partner they could have in any stable matching, while receivers receive their worst possible valid partner.

Binary Relation

A subset $R$ of the Cartesian product $A \times B$ (or $A \times A$ for a relation on a set $A$), consisting of ordered pairs $(a, b)$ where $a \in A$ and $b \in B$. We write $aRb$ to mean $(a, b) \in R$.

Reflexive Property

A relation $R$ on set $A$ is reflexive if $aRa$ for every element $a \in A$.

Symmetric Property

A relation $R$ on set $A$ is symmetric if whenever $aRb$, then $bRa$ for all $a, b \in A$.

Transitive Property

A relation $R$ on set $A$ is transitive if whenever $aRb$ and $bRc$, then $aRc$ for all $a, b, c \in A$.

Antisymmetric Property

A relation $R$ on set $A$ is antisymmetric if whenever $aRb$ and $bRa$, then $a = b$.

Equivalence Relation

A relation $R$ on set $A$ that satisfies all three properties simultaneously: reflexive, symmetric, and transitive.

Equivalence Class ($[a]$)

The set of all elements in $A$ related to $a$ under an equivalence relation $R$, defined as $[a] = \{x \in A \mid aRx\}$.

Partition of a Set

A collection of non-empty, pairwise disjoint subsets of $A$ whose union is $A$. Every equivalence relation on $A$ uniquely partitions $A$ into its equivalence classes.

Hamiltonian Path

A continuous sequence of adjacent edges in a graph that visits every vertex exactly once.

Hamiltonian Cycle (Circuit)

A closed loop in a graph that visits every vertex exactly once and returns to the starting vertex.

Eulerian vs. Hamiltonian Distinction

An Eulerian path or circuit visits every edge in a graph exactly once, whereas a Hamiltonian path or cycle visits every vertex exactly once.

Bipartite Graph Characterization (Odd Cycle Condition)

A graph is bipartite if and only if it contains no odd-length cycles and has chromatic number $\chi(G) \le 2$.

Balanced Bipartite Graph

A bipartite graph $G = (V_1 \cup V_2, E)$ where the two vertex partition sets have equal cardinality ($|V_1| = |V_2|$).

Hamiltonian Cycle Condition in Bipartite Graphs

A Hamiltonian cycle can only exist in a bipartite graph if the graph is balanced ($|V_1| = |V_2|$), because any cycle must alternate back and forth between vertices in $V_1$ and $V_2$.