Final review for CS2304, Mathematical Foundations of Computer Science.

Set and Ordering

I won’t repeat the basics of set theory here.

Symmetric difference: the elements that are in or but not both:

$$A \oplus B = (A - B) \cup (B - A)$$

Relations and Functions

• Ordered pair: $<x,y> = <u,v> \Leftrightarrow x=u \land y=v$
• Cartesian product: $A \times B = \{<x,y> \mid x \in A \land y \in B\}$

Relations

• Binary relation: $R \subseteq A \times B$ (a set of ordered pairs)
• Properties:
  • Reflexivity: $\forall a \in A (aRa)$
  • Symmetry: $\forall a,b \in A (aRb \to bRa)$
  • Transitivity: $\forall a,b,c \in A (aRb \land bRc \to aRc)$

Equivalence Relations and Partitions

• Equivalence relation: a relation that is reflexive, symmetric and transitive at the same time
• Equivalence class: $[x]_R = \{y \mid xRy\}$
• Partition: a family of non-empty, mutually disjoint subsets of A that covers A

Functions

• Definition of a function: a relation F such that
  • $\forall x \in \text{dom } F, \exists! y (xFy)$ , written F(x) = y
• Special functions:
  • Injective: $x_1 \neq x_2 \to F(x_1) \neq F(x_2)$
  • Surjective: $\text{ran } F = B$
  • Bijective: both injective and surjective

Orderings

Partial Order

• Definition: a relation satisfying:
  • Reflexivity:
  • Antisymmetry:
  • Transitivity:
• A linear order (Total Order) is a special case of a partial order that satisfies:
  • Any two elements are comparable: $\forall a,b (a \leq b \lor b \leq a)$
  • Unique maximal and minimal elements
• Hasse Diagram:
  keeps only the immediate successor relation ( means is the immediate successor of )

Special Elements

Properties:

• The largest/smallest element is always maximal/minimal, but the converse does not hold
• A finite partially ordered set always has minimal and maximal elements

Linear Extension Theorem

Linear extensions: for a finite partially ordered set $(S, \preccurlyeq)$, there exists a linearly ordered set $(S, \preccurlyeq')$ such that

$$x \preccurlyeq y \to x \preccurlyeq' y .$$

That is, any partial order can be extended to a linear order while preserving the original order relation. (This is actually topological sorting.)

Antichains and Chains

Dilworth’s Theorem

• Core result: the size of the largest antichain equals the minimum number of antichains in a partition
  
• Corollary:
  where is the size of the largest antichain and is the length of the longest chain

Application: the Erdős–Szekeres Lemma

Any sequence of real numbers contains a monotone subsequence of length .

Cardinality

Equinumerosity

• Definition:
• Important results:
  • (the natural numbers and the rationals are equinumerous)
  • (the reals are uncountable)
  • (Cantor’s theorem)

Continuum Hypothesis

• Question: is there a cardinal with ?
• Conclusion: it can be neither proved nor disproved within the ZFC axiom system (Gödel & Cohen)

Combinatorics

Basic Counting Problem: The Balls-into-Boxes Model

The different cases of putting n balls into m boxes:

where:

• $(m)_n$: the falling factorial
• $\begin{Bmatrix} n \\ k \end{Bmatrix}$: Stirling numbers of the second kind (set partitions)
• $p_k(n)$: the number of ways to partition the integer n into k parts

Basic Counting Principles

Counting Subsets

• Number of subsets of an n-element set: $2^n$
• Number of k-element subsets: $\binom{n}{k} = \frac{n!}{k!(n-k)!}$

Counting Permutations

• Number of permutations of an n-element set: $n!$
• Permutations with constraints (multinomial coefficients): $$\binom{n}{k_1,k_2,\ldots,k_m} = \frac{n!}{k_1!k_2!\cdots k_m!}$$

The Binomial and Multinomial Theorems

Binomial Theorem

$$(1+x)^n = \sum_{k=0}^n \binom{n}{k}x^k$$

Corollaries:

• $$\sum_{k=0}^n \binom{n}{k} = 2^n$$
• $$\sum_{k=0}^n (-1)^k \binom{n}{k} = 0$$

Multinomial Theorem

$$(x_1 + x_2 + \cdots + x_m)^n = \sum_{k_1+\cdots+k_m=n} \binom{n}{k_1,\ldots,k_m} x_1^{k_1}\cdots x_m^{k_m}$$

Generalized Binomial Theorem (Newton)

$$(x+y)^r = \sum_{k=0}^\infty \binom{r}{k} x^{r-k}y^k, \quad |x|>|y|$$

where $\binom{r}{k} = \frac{r(r-1)\cdots(r-k+1)}{k!}$

Special Counting Sequences

Catalan Numbers

Definition:

$$C_n = \frac{1}{n+1}\binom{2n}{n}$$

Recurrence:

$$C_0=1, \quad C_n = \sum_{k=0}^{n-1} C_k C_{n-k-1}$$

Applications:

• Triangulations of a convex (n+2)-gon
• Dyck paths (lattice paths that do not cross the diagonal)
• Number of valid parenthesis sequences

Stirling Numbers

• Stirling numbers of the second kind (set partitions):

  $$\begin{Bmatrix} n \\ k \end{Bmatrix} = k\begin{Bmatrix} n-1 \\ k \end{Bmatrix} + \begin{Bmatrix} n-1 \\ k-1 \end{Bmatrix}$$

• Stirling numbers of the first kind (permutations by cycles):

  $$\begin{bmatrix} n \\ k \end{bmatrix} = (n-1)\begin{bmatrix} n-1 \\ k \end{bmatrix} + \begin{bmatrix} n-1 \\ k-1 \end{bmatrix}$$

Properties:

$$\sum_{k=0}^n \begin{Bmatrix} n \\ k \end{Bmatrix} = B_n \text{(Bell number)}, \quad \sum_{k=0}^n \begin{bmatrix} n \\ k \end{bmatrix} = n!$$

Inclusion–Exclusion Principle

Basic Formula

$$\left| \bigcup_{i=1}^n A_i \right| = \sum_{\emptyset \neq I \subseteq [n]} (-1)^{|I|-1} \left| \bigcap_{i \in I} A_i \right|$$

Applications

Derangements:

$$D(n) = n! \sum_{k=0}^n \frac{(-1)^k}{k!} \sim \frac{n!}{e}$$

Euler’s totient function:

$$\varphi(n) = n \prod_{p|n} \left(1 - \frac{1}{p}\right)$$

Generating Functions

Ordinary Generating Functions (OGF)

Definition:

$$A(x) = \sum_{n=0}^\infty a_n x^n$$

Operations on Generating Functions

Applications

Fibonacci sequence:

$$F(x) = \frac{x}{1-x-x^2}$$

Catalan numbers:

$$C(x) = \frac{1 - \sqrt{1-4x}}{2x}$$

Solving Recurrence Relations

Homogeneous Linear Recurrences

$$h_n = \sum_{i=1}^k a_i h_{n-i}$$

Method:

1. Solve the characteristic equation: $x^k - a_1 x^{k-1} - \cdots - a_k = 0$
2. Build the general solution according to the roots:
   • Simple root $\lambda_i$: $c_i \lambda_i^n$
   • Root of multiplicity $r$: $(c_0 + c_1 n + \cdots + c_{r-1} n^{r-1}) \lambda^n$

Non-homogeneous Recurrences

$$h_n = \sum_{i=1}^k a_i h_{n-i} + b_n$$

General solution = homogeneous solution + particular solution (guess the particular solution from the form of $b_n$)

Asymptotic Analysis

Asymptotic Notation

• f(n) = O(g(n)): $\exists C>0, n_0 \quad \forall n>n_0: |f(n)| \leq C g(n)$
• $f(n) = \Theta(g(n))$: f=O(g) and g=O(f)

Important Asymptotic Estimates

Factorial (Stirling’s formula):

$$n! \sim \sqrt{2\pi n} \left( \frac{n}{e} \right)^n$$

Harmonic series:

$$H_n = \sum_{k=1}^n \frac{1}{k} \sim \ln n$$

Binomial coefficients:

$$\binom{n}{k} \leq \left( \frac{en}{k} \right)^k, \quad \text{for } k=o(\sqrt{n}):\ \binom{n}{k} \sim \frac{n^k}{k!}$$

Graph theory

Already covered in detail in Graph Theory

(Rant: I started learning graph theory in Data Structures in the second semester of freshman year, learned it again in Circuit Theory and Discrete Mathematics in the first semester of sophomore year, and then once more in Algorithms and this math course in the second semester of sophomore year. Saturation-style learning, I guess.)

The probabilistic method

Same as above, I won’t repeat the basic concepts.

Random Variables

Definition and Distribution

• Random variable
• Discrete distribution:

Expectation and Variance

• Expectation:
• Variance:
• Linearity: $$E\left[\sum X_i\right] = \sum E[X_i], \quad E[cX] = cE[X]$$

Common Distributions

Memorylessness of the Geometric Distribution

$$Pr(X=n+k \mid X>k) = Pr(X=n)$$

---

Probability Inequalities

Basic Inequalities

• Markov: for non-negative and : $$Pr(X \geq a) \leq \frac{E[X]}{a}$$
• Chebyshev: $$Pr(|X - E[X]| \geq a) \leq \frac{Var[X]}{a^2}$$

Chernoff Bounds

For independent Bernoulli() variables, , :

• Upper tail:
• Lower tail:

---

The Probabilistic Method

By choosing objects of a specified class at random and showing that the probability of obtaining the target object is greater than zero, we prove that it exists. This is a non-constructive method.

Basic Counting Arguments

• Existence of Boolean functions: there exists an -variable Boolean function that needs symbols to describe $$2^{2^n} > (n+8)^m \implies m < 2^n / \log_2(n+8)$$

Expectation Arguments

• Graph cuts: a graph with vertices and edges has a partition with a cut $$E[\text{number of cut edges}] = m \cdot \frac{n}{2n-1} > \frac{m}{2}$$
• Lower bound on independent sets: $$\alpha(G) \geq \sum_{v} \frac{1}{\deg(v)+1} \geq \frac{n^2}{2|E|+n} \quad (\text{Turán's theorem})$$
• MAXSAT: with clauses (minimum length ), there exists an assignment satisfying clauses $$E[\text{number of satisfied clauses}] = \sum (1-2^{-k_i}) \geq m(1-2^{-k})$$

Lovász Local Lemma

For events whose dependency graph has maximum degree , if and , then:

$$Pr\left(\bigcap \overline{E_i}\right) > 0$$

Applications:

• A -SAT instance is satisfiable when each variable appears times
• Existence of edge-disjoint paths: a solution exists when

Random graph

Random Graphs

---

Translated from the Chinese original.