# 1. Basic Enumeration

## Preface

Combinatorial problems:

• Enumeration (counting)：有多少个符合条件的解？
• Existence：是否存在解？
• Extremal（极问题）：满足特定约束的解最大/最小是多少？
• Ramsey：当解很大的时候会出现什么结构？
• Optimization：找到最优解
• Construction (design)：构造一个解

## Enumeration

How many ways are there:

• to rank $$n$$ people: $$n!$$
• to assign $$m$$ zodiac signs to $$n$$ people: $$m^n$$
• to choose $$m$$ people out of $$n$$ people: $$\binom{n}{m}$$
• to partition $$n$$ people into $$m$$ groups: $${n \brace m} = \binom{n+m-1}{m-1}$$ (stirling numbers of the second kind)
• to distribute $$m$$ yuan to $$n$$ people: $$n^m$$
• to partition $$m$$ yuan to $$n$$ parts: $$p_n(m)$$ (partition number)
• $$\dots$$

The Twelvefold Way

Knuth's version: $$n$$ balls are put into $$m$$ bins

balls per binany$$\leqslant 1$$$$\geqslant 1$$
$$n$$ distinct balls, $$m$$ distinct bins$$m^n$$$$(m)_n$$$$m!{n \brace m}$$
$$n$$ identical balls, $$m$$ distinct bins$$\left({m \choose n}\right)$$$${m \choose n}$$$${n-1 \choose m-1}$$
$$n$$ distinct balls, $$m$$ identical bins$$\sum\limits_{k=1}^{m} {n \brace k}$$$$\begin{cases}1 \text{ if } n \leqslant m \\ 0 \text{ if } n > m\end{cases}$$$${n \brace m}$$
$$n$$ identical balls, $$m$$ identical bins$$\sum\limits_{k=1}^m p_k(n)$$$$\begin{cases}1 \text{ if } n \leqslant m \\ 0 \text{ if } n > m\end{cases}$$$$p_m(n)$$

## Tuples

• $$[m] = \lbrace 1, 2, \dots, m \rbrace$$
• $$[m]^n = [m] \times \dots \times [m]$$
• $$\vert [m]^n \vert = m^n$$

Product rule: $$\vert S \times T \vert = \vert S \vert \cdot \vert T \vert$$.

## Functions

Bijection rule: 若存在$$S$$到$$T$$的双射，则$$\vert S \vert = \vert T \vert$$.

Therefore, the number of functions:

• $$f: [n] \rightarrow [m]$$
• $$f \Leftrightarrow (f(1), \dots, f(n)) \in [m]^n$$
• $$\vert [n] \rightarrow [m] \vert = \vert [m]^n \vert = m^n$$.

The number of 1-1 functions (injections):

• $$\pi = (f(1), \dots, f(n))$$
• $$n$$-permutation: $$\pi \in [m]^n$$ of distinct elements
• $$\vert \pi \vert = \dfrac{m!}{(m-n)!} = (m)_n$$ ($$m$$ lower factorial $$n$$)

## Subsets

• $$[n] = \lbrace 1, 2, \dots, n \rbrace$$
• Power set: $$2^{[n]} = \lbrace S | S \subseteq [n] \rbrace$$
• $$\vert 2^{[n]} \vert = 2^n$$

Sum rule: finite disjoint sets $$S$$ and $$T$$, $$\vert S \cup T \vert = \vert S \vert + \vert T \vert$$.

$$\Rightarrow \vert 2^{[n]} \vert = 2\vert 2^{[n-1]} \vert, \vert 2^{\emptyset} \vert = 1$$.

Subsets of fixed size:

• $$k$$-uniform: $${S \choose k} = \lbrace T \subseteq S | \vert T \vert = k \rbrace$$
• $${n \choose k} = \vert {[n] \choose k} \vert = \dfrac{n!}{k!(n-k)!}$$

## Binomial coefficients

Binomial coefficient: $${n \choose k} = \dfrac{n!}{k!(n-k)!}$$

Properties:

• $${n \choose k} = {n \choose n-k}$$
• $$\sum\limits_{k=0}^{n} {n \choose k} = 2^n$$
• # of odd subsets = # of even subsets

Binomial theorem: $$(1+x)^n = \sum\limits_{k=0}^{n} {n \choose k} x^k$$.

## Compositions of an integer

$$n$$块钱分给$$k$$个不同的人，每个人至少一块钱：

$$k$$-composition of $$n$$: a $$k$$-tuple $$(x_1, x_2, \dots, x_k)$$, satisfying

$x_1 + x_2 + \dots + x_k = n, \ x_i \in \mathbb{Z}^+$

# of $$k$$-composition of $$n$$: $${n-1 \choose k-1}$$ (can be proven in the following ways)

• 高中的插板法
• Define $$\phi((x_1, \dots, x_k)) = \lbrace x_1, x_1 + x_2, \dots, x_1 + x_2 + \dots + x_{k-1} \rbrace$$, then $$\phi$$ is a 1-1 correspondence between $$k$$-compositions of $$n$$ and $${[n-1] \choose k-1}$$.

Weak $$k$$-composition of $$n$$: $$x_i \in \mathbb{N}$$ $(x_1 + 1) + (x_2 + 1) + \dots + (x_k + 1) = n + k$

# of weak $$k$$-composition of $$n$$: $${n+k-1 \choose k-1}$$

## Multisets

$$k$$-subset of $$S$$: "$$k$$-combination of set $$S$$ without repetition".

# of $$k$$-subset is denoted as $$\left( {n \choose k} \right) = {n+k-1 \choose n-1} = {n+k-1 \choose k}$$.

$$k$$-subset of $$S$$ is a weak $$n$$-composition of $$k$$.

## Multinomial coefficients

Permutations of a multiset of size $$n$$ with multiplicities $$m_1, m_2, \dots, m_k$$

= Assign $$n$$ distinct balls to $$k$$ distinct bins with the $$i$$-th bin receiving $$m_i$$ balls

E.g. # of reordering of "multinomial" $$\Leftrightarrow$$ permutations of {a, i, i, l, l, m, m, n, o, t, u}

Multinomial coefficient is denoted as $${n \choose m_1, \dots, m_k} = \dfrac{n!}{m_1! m_2! \dots m_k!}$$.

Multinomial theorem: $$(x_1 + \dots + x_k)^n = \sum\limits_{m_1+\dots+m_k = n} {n \choose m_1, \dots, m_k} x_1^{m_1} \cdots x_k^{m_k}$$

## Partitions of a set

Divide a set of $$n$$ into $$k$$ partitions

$$P = \lbrace A_1, \dots, A_k \rbrace$$ is a partition of $$S$$ if:

• $$A_i \neq \emptyset$$,
• $$A_i \cap A_j = \emptyset$$,
• and $$\bigcup A_i = S$$.

# of $$k$$-partitions of an $$n$$ set (Stirling number of the second kind) is denoted as $${n \brace k}$$.

# of all partitions of an $$n$$ set (Bell number) is $$B_n = \sum\limits_{k=1}^{n} {n \brace k}$$.

Satisfies: $${n \brace k} = k {n-1 \brace k} + {n-1 \brace k-1}$$ (as the following two cases)

• case 1: $$\lbrace n \rbrace$$ is not a partition block
• case 2: $$\lbrace n \rbrace$$ is a partition block

## Surjections

$$\forall i \in [m]$$, $$f^{-1}(i) \neq \emptyset$$, then

$$f \Leftrightarrow (f^{-1}(1), \dots, f^{-1}(m))$$.

Surjections is equal to an ordered $$m$$-partition of $$[n]$$

Therefore # of surjections is $$m! {n \brace m}$$.

## Partitions of a number

$$p_k(n)$$: # of partitions of $$n$$ into $$k$$ parts

Equal to # of integral solutions to

$\begin{cases}x_1 + \dots + x_k = n, \ x_1 \geqslant \dots \geqslant x_k \geqslant 1\end{cases}$

Depending on $$x_k = 1$$ or not, we have

$p_k(n) = p_{k-1}(n-1) + p_k(n-k)$

Difference of partition and composition:

• partition: $$x_1 \geqslant \dots \geqslant x_k \geqslant 1$$
• composition: $$x_i \geqslant 1$$

Every partition is a composition (onto).

If we have a partition of $$n$$ into $$k$$ parts $$x_1 \dots x_k$$, then by defining $$y_i = x_i + k - i$$, we have a $$k$$ composition of $$n + \dfrac{k(k-1)}{2}$$ (1-1).

Therefore, we have

$\dfrac{{n-1 \choose k-1}}{k!} \leqslant p_k(n) \leqslant \dfrac{n + \frac{k(k-1)}{2} -1 \choose k-1}{k!}$

Results of Young Graph:

• # of partitions of $$n$$ into $$k$$ parts = # of compositions of $$n$$ with largest part being $$k$$
• # of partitions of $$n$$ into $$k$$ parts = # of partitions of $$n-k$$ into at most $$k$$ parts

# 2. Generating Functions

What is # of compositions of $$n$$ with summands from $$\lbrace 1, 2 \rbrace$$?

• Case 1: $$x_k = 1$$, then $$x_1 + \dots + x_{k-1} = n-1$$,
• Case 2: $$x_k = 2$$, then $$x_1 + \dots + x_{k-1} = n-2$$.

Thus $$a_n = a_{n-1} + a_{n-2}$$.

## Catalan Number

$$C_n$$: # of full binary trees with $$n+1$$ leaves

Using recursion: $$C_0 = 1$$, for all $$n \geqslant 1$$,

$C_n = \sum\limits_{k=0}^{n-1}C_k C_{n-1-k}$

## Double Decks

How to choose $$m$$ cards from $$2$$ decks of $$n$$ cards?

Each card can be chosen for no times, once and twice:

$(x_1^0 + x_1^1 + x_1^2) (x_2^0 + x_2^1 + x_2^2) \cdots (x_n^0 + x_n^1 + x_n^2)$

$\Rightarrow (1+x+x^2)^n = \sum_k \sum_{l \leqslant k} {n \choose k}{k \choose l} x^{k+l} = \sum_m \left( \sum_l {n \choose m-l} {m-l \choose l} \right) x^m$

## Multisets

Multisets on $$S = \lbrace x_1, \dots, x_n \rbrace$$.

Each element can be chosen for no time, once, twice, ...

$(1 + x_1^1 + x_1^2 + \dots) (1 + x_2^1 + x_2^2 + \dots) \cdots (1 + x_n^1 + x_n^2 + \dots)$

$(1 + x^1 + x^2 + \dots)^n = \sum_{m \in \mathbb{N}^n} x^{m_1 + \dots + m_n} = \sum_{k \geqslant 0} \left( {n \choose k} \right) x^k$

By some magic:

$(1 + x^1 + x^2 + \dots)^n = (1-x)^{-n} = \sum_{k \geqslant 0} {n+k-1 \choose k} x^k$

Therefore $$\left( {n \choose k} \right) = {n+k-1 \choose k}$$.

## Ordinary Generating Function

$$G(x) = \sum\limits_{n=0}^{\infty} a_n x^n = a_0 + a_1 x + a_2 x^2 + \dots$$

Define $$[x^n]G(x) = a_n$$.

## Fibonacci Number

Solution of $$F_n$$: $$\phi = \dfrac{1 + \sqrt{5}}{2}, \hat{\phi} = \dfrac{1 - \sqrt{5}}{2}$$

$F_n = \dfrac{1}{\sqrt{5}} \left( \phi^n - \hat{\phi}^n \right).$

By recursion:

$$G(x) = F_0 + F_1 x + \sum\limits_{n \geqslant 2} F_n x^n = x + \sum\limits_{n \geqslant 2} F_{n-1} x^n + \sum\limits_{n \geqslant 2} F_{n-2} x^n$$

Identity: $$G(x) = x + (x + x^2) G(x)$$.

Solution: $$G(x) = \dfrac{x}{1-x-x^2}$$.

## Formal Power Series

$$G(x) = \sum\limits_{n=0}^{\infty} a_n x^n$$

$$\mathbb{C}[x]$$: ring of formal power series with complex coefficient

Inverse: $$F(x)G(x) = 1 \Longrightarrow F(x) = G^{-1}(x) = \dfrac{1}{G(x)}$$

## Generatingfunctionology

1. Recurrence: $$a_n = a_{n-1} + a_{n-2}$$
2. Manipulation: $$G(x) = x + (x + x^2) G(x)$$
3. Solving: $$G(x) = \dfrac{x}{1-x-x^2} = \dots$$

## Generating Function Manipulations

$$G(x) = \sum\limits_{n \geqslant 0} g_n x^n, F(x) = \sum\limits_{n \geqslant 0} f_n x^n$$

• shift: $$x^kG(x) = \sum\limits_{n \geqslant k} g_{n-k} x^n$$
• addition: $$F(x)+G(x) = \sum\limits_{n \geqslant 0} (f_n + g_n) x^n$$
• convolution: $$F(x)G(x) = \sum\limits_{n \geqslant 0} \sum\limits_{k=0}^n f_k g_{n-k} x^n$$
• differentiation: $$G'(x) = \sum\limits_{n \geqslant 0} (n+1) g_{n+1} x^n$$

## Expanding Generating Functions

• Taylor's expansion: $G(x) = \sum_{n \geqslant 0} \dfrac{G^{(n)}(0)}{n!} x^n$
• Geometric sequence: $\dfrac{a}{1-bx} = a \sum_{n \geqslant 0} (bx)^n$
• Binomial theorem (Newton's formula): $(1+x)^\alpha = \sum_{n \geqslant 0} {\alpha \choose n} x^n$

Generalized binomial coefficient: ${\alpha \choose n} = \dfrac{\alpha (\alpha-1) \cdots (\alpha - n + 1)}{n!}$

## Catalan Number (cont'd)

$$C_0 = 1$$, for all $$n \geqslant 1$$,

$C_n = \sum\limits_{k=0}^{n-1}C_k C_{n-1-k}$

Manipulation:

$$G(x) = \sum_{n \geqslant 0} C_nx^n = C_0 + \sum_{n \geqslant 1} \sum_{k=0}^{n-1} C_{k} C_{n-1-k} x^n$$

$$\Longrightarrow G(x) = 1 + xG^2(x)$$

Solving:

$$\Longrightarrow G(x) = \dfrac{1 \pm (1-4x)^{1 / 2}}{2x}$$

Since $$\lim\limits_{x \rightarrow 0} G(x) = C_0 = 1$$, we have

$G(x) = \dfrac{1 - (1-4x)^{1 / 2}}{2x}$

Expanding (by Newton's formula):

\begin{align} (1-4x)^{1 / 2} &= \sum\limits_{n \geqslant 0} {1 / 2 \choose n} (-4x)^n \\ &= 1 + \sum\limits_{n \geqslant 1} {1 / 2 \choose n} (-4x)^n \\ &= 1 + \sum\limits_{n \geqslant 0} {1 / 2 \choose n + 1} (-4x)^{n+1} \\ &= 1 - 4x \sum\limits_{n \geqslant 0} {1 / 2 \choose n} (-4x)^n \end{align}

Therefore, $$G(x) = \dfrac{1 - (1-4x)^{1 / 2}}{2x} = 2 \sum\limits_{n \geqslant 0} {1 / 2 \choose n + 1} (-4x)^n = \sum\limits_{n \geqslant 0} 2 {1 / 2 \choose n + 1} (-4)^n x^n$$

We get $$C_n = 2 {1 / 2 \choose n + 1} (-4)^n$$.

Further more, $$C_n = \dfrac{1}{n+1} {2n \choose n}$$.

## Quicksort

Complexity:

• worst case: $$\Theta(n^2)$$
• average case: ?

Let $$T_n$$ be the average # of comparisons used by quick sort.

Suppose $$\pi$$ is a uniform random permutation of $$S_n$$, then we run quick sort on $$\pi$$.

Suppost the pivot is the $$k$$-th smallest number in $$\pi$$, then we have the # of elements in both sections:

• $$\vert L \vert = k - 1$$
• $$\vert R \vert = n - k$$

Since $$\pi$$ is uniformly random, the probability of pivot being the $$k$$-th smallest element for any $$k$$ is $$\dfrac{1}{n}$$.

By recursion, we have $T_n = \dfrac{1}{n} \sum\limits_{k=1}^n (n-1 + T_{k-1} + T_{n-k})$

-> $$T_n = \Theta(n \lg n)$$ (see the slides).

# 3. Sieve Methods

## Principle of Inclusion-Exclusion

$$\left\vert \bigcup\limits_{i=1}^n A_i \right\vert = \sum\limits_{I \subseteq {1, \dots, n}, I \neq \emptyset} (-1)^{\vert I \vert - 1} \left\vert \bigcap\limits_{i \in I} A_i \right\vert$$.

Suppose $$A_1, \dots, A_n \subseteq U$$, then $\left\vert \overline{A_1} \cap \dots \cap \overline{A_n} \right\vert = \left\vert U - \bigcup\limits_{i=1}^n A_i \right\vert.$

Denote $$A_I = \bigcap\limits_{i \in I} A_i$$, $$A_{\emptyset} = U$$.

## Surjections

What is # of onto functions from $$[n]$$ to $$[m]$$?

Let $$U$$ be the domain of functions $$[n] \rightarrow [m]$$. $$A_i = [n] \rightarrow ([m] \setminus {i}).$$

Then we have $\left\vert \bigcap_{i \in [m]} \overline{A_i} \right\vert = \sum\limits_{I \subseteq [m]} (-1)^{\vert I \vert} \vert A_I \vert = \sum\limits_{I \subseteq [m]} (-1)^{\vert I \vert} (m - \vert I \vert)^n = \sum\limits_{k=0}^{m} (-1)^{m-k} {m \choose k} k^n.$

Therefore, the sterlin number of the second kind is ${n \brace m} = \dfrac{1}{m!} \sum\limits_{k=0}^{m} (-1)^{m-k} {m \choose k} k^n.$

## Derangement

# of permutation $$\pi$$ of $$[n]$$, $$\forall i$$, $$\pi(i) \neq i$$. (permutations with no fixed point, denoted as $$!n$$).

$$U$$: all permutations of $$[n]$$ (a symetric group), $$A_i$$: permutations with $$\pi(i) = i$$.

Size of $$A_I$$ is $$(n - \vert I \vert)!$$.

$\left\vert \bigcap_{i \in [n]} \overline{A_i} \right\vert = \sum\limits_{I \subseteq [n]} (-1)^{\vert I \vert} \vert A_I \vert = \dots = n! \sum_{k=0}^n \dfrac{(-1)^k}{k!} = \dfrac{n!}{e}.$

## Permutations with restricted positions

• Derangement: $$\forall i, \pi(i) \neq i$$
• Generally: $$\pi(i_1) \neq j_1, \pi(i_2) \neq j_2, \dots$$
• Forbidden patterns: $$B \subseteq [n] \times [n], \forall i, (i, \pi(i)) \notin B$$

A chess board: a grid of $$[n] \times [n]$$. To put $$n$$ chess pieces on the board and with no two pieces on same row/column. (A placement of non-attacking rooks).

Forbidden positions $$B \subseteq [n] \times [n]$$

Derangement: $$\forall i, (i, i) \notin B$$ (not on the diagonal).

$$r_k$$: # of ways of placing $$k$$ non-attacking rooks in $$B$$.

$r_k = {n \choose k}.$

$$N_0$$: # of placements of $$n$$ non-attacking rooks.

$N_0 = \sum\limits_{k=0}^{n} (-1)^k r_k (n-k)! = \sum\limits_{k=0}^{n} (-1)^k {n \choose k} (n-k)! \rightarrow \dfrac{n!}{e}.$

## Ménage Problem

# of ways that $$n$$ couples sit around a table, satisfying

• male-female alternative
• no one sit next to its spouse

Ladies first choose where to sit: $$2 \cdot n!$$ ways (all odd or all even).

Then gentlemen sit, each way has a corresponding permutation $$\pi$$ of $$[n]$$.

• $$i$$: husband of the lady at the $$i$$-th position.
• $$\pi(i)$$: his position

Requires

• $$\pi(i) \neq i$$
• $$\pi(i) \neq i+1 \mod n$$

$$\Rightarrow$$ Chess game again: $$B = {(i, i), (i, i+1 \mod n)}$$.

• $$r_k$$: # of ways of placing $$k$$ non-attacking rooks in $$B$$.
• $$r_k$$: # of ways of choosing $$k$$ non-consecutive points from a circle of $$2n$$ points

$$\Rightarrow$$ $$L(m, k)$$: # of ways to choose $$k$$ non-consecutive objects from a line of $$m$$ objects.

• select $$k$$ slots from $$n-k+1$$ slots after removing $$k$$ objects.

$L(m, k) = {n-k+1 \choose k}.$

$$C(m, k)$$: # of ways to choose $$k$$ non-consecutive objects from a circle of $$m$$ objects.

• choose $$k$$ non-consecutive objects from a circle and mark one of the remaining objects: $$(m-k) \cdot C(m, k)$$.
• mark one object and disconnect the circle by removing the object, then choose $$k$$ non-consecutive objects from the $$m-1$$ objects: $$m \cdot L(m-1, k)$$.

$C(m, k) = \dfrac{m}{m-k} L(m-1, k) = \dfrac{m}{m-k} {m-k \choose k}.$

$$\Leftarrow$$ $$r_k = \dfrac{2n}{2n-k}{2n-k \choose k}$$. Therefore,

$N_0 = \sum\limits_{k=0}^{n} (-1)^k r_k (n-k)! = \sum\limits_{k=0}^{n} (-1)^k \dfrac{2n}{2n-k} {2n-k \choose k} (n-k)!$

## Inversion

$$V$$: $$2^n$$-dimensional vector space of all mappings

$f: 2^{[n]} \rightarrow \mathbb{N}.$

linear transformation $$\phi: V \rightarrow V$$.

$\forall S \subseteq [n], \ \ \phi(f(S)) \overset{\Delta}{=} \sum_{T \supseteq S, T \subseteq [n]} f(T).$

then its inverse:

$\forall S \subseteq [n], \ \ \phi^{-1} (f(S)) = \sum_{T \supseteq S, T \subseteq [n]} (-1)^{[T \setminus S]} f(T).$

$$f_{=}(I) = \left\vert \left\{ x \in U | \forall i \in I, x \in A_i, \forall j \notin I, x \notin A_j \right\} \right\vert = \left\vert \left(\bigcap\limits_{i \in I} A_i\right) \setminus \left(\bigcap\limits_{j \notin I} A_j\right) \right\vert.$$

$$f_{\geqslant} (I) = \sum\limits_{J \supseteq I, J \subseteq [n]} f_{=}(J) = \left\vert \bigcap\limits_{i \in I} A_i \right\vert = \vert A_I \vert.$$

PIE:

• $$\sum\limits_{I \subseteq S} (-1)^{\vert S \vert - \vert I \vert} = \begin{cases}1, & S = \emptyset, \\ 0, & \text{otherwise}.\end{cases}$$
• for all $$T \subseteq S$$, $\sum\limits_{T \subseteq I \subseteq S} (-1)^{\vert S \vert - \vert I \vert} = \begin{cases}1, & S = T, \\ 0, & \text{otherwise}.\end{cases}$

## Bipartite perfect matching

Given a bipartite graph $$G([n], [n], E)$$, # of permutations $$\pi$$ of $$[n]$$ satisfying that $$(i, \pi(i)) \in E$$.

$$n \times n$$ matrix $$A$$: $$A_{ij} = \begin{cases}1, & (i, j) \in E, \\ 0, & (i, j) \notin E. \end{cases}$$

# of perfect matching in $$G = \sum\limits_{\pi \in S_n} \prod\limits_{i \in [n]} A_{i, \pi(i)}$$.

• permanent: $$\text{perm}(A) = \sum\limits_{\pi \in S_n} \prod\limits_{i \in [n]} A_{i, \pi(i)}$$.
• determinant: $$\det(A) = \sum\limits_{\pi \in S_n} (-1)^{r(\pi)} \prod\limits_{i \in [n]} A_{i, \pi(i)}.$$

Ryser's formula $$O(n!) \rightarrow O(n 2^n)$$:

$\sum\limits_{\pi \in S_n} \prod\limits_{i \in [n]} A_{i, \pi(i)} = \sum\limits_{I \subseteq [n]} (-1)^{n - \vert I \vert} \prod_{i \in [n]} \sum_{j \in I} A_{ij}.$

## Sieve of Eratosthenes

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

## Euler Totient Function

$$\phi(n) = \left\vert \left\{ 1 \leqslant a \leqslant n | \gcd(a,n) = 1 \right\} \right\vert$$.

prime decomposition: $$n = p_1^{k_1} p_2^{k_2} \cdots p_{r}^{k_r}$$.

$$U = [n], A_i = \left\{ 1 \leqslant a \leqslant n \ {\large|} \ p_i \vert a \right\}$$.

$$\vert A_i \vert = \dfrac{n}{p_i}, \vert A_I \vert = \dfrac{n}{\prod p_i}.$$

Therefore, $$\phi(n) = \sum_{I \subseteq [r]} (-1)^{\vert I \vert} \vert A_I \vert = n \prod\limits_{i=1}^{r} \left( 1 - \dfrac{1}{p_i} \right).$$

# 4. Symmetry

## Permutation Groups

Group $$(G, \cdot)$$ with binary operator $$\cdot: G \times G \rightarrow G$$

• closure: $$\pi, \sigma \in G \Rightarrow \pi \cdot \sigma \in G$$
• associativity: $$\pi \cdot (\sigma \cdot \tau) = (\pi \cdot \sigma) \cdot \tau$$
• identity: $$\exists e, e \cdot \pi = \pi$$
• inverse: $$\pi \cdot \sigma = e, \pi = \sigma^{-1}$$

Commutative (abelian) group: $$\pi \cdot \sigma = \sigma \cdot \pi$$

• Symmetric group $$S_n$$: all permutations $\pi: [n] \underset{onto}{\overset{1-1}{\longrightarrow}} [n]$
• Cyclic group $$C_n$$: rotations $\pi = (012\cdots n-1), C_n = \langle \pi \rangle$
• Dihedral group $$D_n$$: rotations & reflections: generated by $$(012\cdots n-1)$$ and $$\rho$$ (reflection)

## Group Action

Configuration $$x: [n] \rightarrow [m]$$, $$X = [m]^{[n]}$$

Permutation: $$\pi: [n] \underset{onto}{\overset{1-1}{\longrightarrow}} [n]$$

Group action: $$\circ: G \times X \rightarrow X$$

• associativity: $$(\pi \cdot \sigma) \circ x = \pi \circ (\sigma \circ x)$$
• identity: $$e \circ x = x$$

## Graph Isomorphism (GI)

• Input: two undirected graphs $$G$$ and $$H$$
• Output: $$G \cong H ?$$
• GI is in NP (Babai's algorithm).

## String Isomorphism (SI)

• Input: two strings $$x, y: [n] \rightarrow [m]$$, and a permutation group $$G \subseteq S_n$$
• Output: $$x \cong_G y ?$$ (i.e., $$\exists \sigma \in G, \sigma \circ x = y$$)

Johnson group: $$\mathbb{S}_V^{(2)} \subset S_{{V \choose 2}}$$ on vertex pairs

Two graphs $$X \cong Y$$ iff their string versions $$x \cong_{\mathbb{S}_V^{(2)}} y$$

## Orbits

Group action $$\circ$$

Define orbit of $$x$$: $$Gx = \left\lbrace \pi \circ x | \pi \in G \right\rbrace$$, an equivalent class of configuration $$x$$

$$X/G = \left\lbrace Gx | x \in X \right \rbrace$$

Our goal: count $$\vert X/G \vert$$

Example: $$X = [2]^{[6]}$$: $$\vert X/G \vert$$ is the number of ways to put 2 colors onto a ring of 6 elements.

Let $$\vec v = (n_1, n_2, \dots, n_m), \sum n_i = n$$, then $$a_{\vec v}$$ is # of configurations (up to symmetry) with number of color $$i$$ being $$n_i$$.

Pattern inventory: (multi-variate) generating function:

$F_G(y_1, y_2, \dots, y_m) = \sum_{\vec v} a_{vec v} y_1^{\vec v_{n_1}} y_2^{\vec v_{n_2}} \cdots y_m^{\vec v_{n_m}}$

Example: $$n=2, m=6, F_{D_6}(y_1, y_2) = y_1^6 + y_1^5 y_2 + 3y_1^4 y_2^2 + 3y_1^3 y_2^3 + 3y_1^2 y_2^4 + 3y_1 y_2^5 + y_2^6$$

## Burnside's Lemma

Define invariant set of $$\pi$$: $$X_\pi = \left\lbrace x \in X | \pi \circ x = x \right\rbrace$$.

Burnside's Lemma:

$\vert X/G \vert = \dfrac{1}{\vert G \vert} \sum\limits_{x \in G} \vert X_\pi \vert.$

Define stabilizer of $$x$$: $$G_x = \left\lbrace \pi \in G | \pi \circ x = x \right\rbrace$$.

Lemma: $$\forall x \in X, \vert G_x \vert \vert Gx \vert = \vert G \vert.$$

$A(\pi, x) = \begin{cases}1, & \pi \circ x = x \\ 0, & \text{o.w.} \end{cases}$

• $$\vert X_\pi \vert = \sum\limits_{x \in X} A(\pi, x)$$
• $$\vert G_x \vert = \sum\limits_{\pi \in G} A(\pi, x)$$

Double counting: $\sum_{\pi \in G} \vert X_\pi \vert = \sum_{\pi \in G}\sum_{x \in X} A(\pi, x) = \sum_{x \in X} \vert G_x \vert = \vert G \vert \sum_{x \in X} \dfrac{1}{\vert G_x \vert} = \overset{??}{\cdots} = \vert G \vert \vert X/G \vert$

## Cycle Decomposition

E.g. $$\dbinom{0\ 1\ 2\ 3\ 4}{2\ 4\ 0\ 1\ 3} = (02)(143)$$, decompose a permutation into 2 cycles.

Invarian $$\pi \circ x = x$$, forall $$i$$, $$x(\pi(i)) = x(i)$$, iff every cycle of $$\pi$$ has the same color.

If $$X = [m]^{[n]}$$ ($$m$$ colors, $$n$$ elements on a ring), $$\pi$$ has $$k$$ cycles, then $$\vert X_\pi \vert = m^k$$

Burnside's Lemma (cont'd): $\vert X/G \vert = \dfrac{1}{\vert G \vert} \sum\limits_{x \in G} \vert X_\pi \vert = \dfrac{1}{\vert G \vert} \sum\limits_{x \in G} m^{\text{\# of cycle in } \pi}.$

## Cycle Index

Suppose permutation $$\pi$$ has $$k$$ cycles of length $$l_1, l_2, \dots, l_k$$,

Define monomial: $$M_n(x_1, x_2, \dots, x_n) = \prod\limits_{i=1}^k x_{l_i}$$

Cycle index: $$P_G(x_1, x_2, \dots, x_m) = \dfrac{1}{\vert G \vert} \sum\limits_{\pi \in G} M_{\pi}(x_1, x_2, \dots, x_n)$$

Burnside's Lemma: $\vert X/G \vert = P_G(m, m, \dots, m) = \dfrac{1}{\vert G \vert} \sum\limits_{\pi \in G} M_{\pi}(m, m, \dots, m)$

Polya's Enumeration Formula: $F_G(y_1, y_2, \dots, y_m) = P_G \left( \sum_{i=1}^m y_i, \sum_{i=1}^m y_i^2, \dots, \sum_{i=1}^m y_i^n \right)$

# 5. Cayley's Formula

## Counting Trees

How many different trees can be formed from $$n$$ distinct trees?

Cayley's Formula: there are $$n^{n-2}$$ trees on $$n$$ distinct vertices.

### Prufer Code

By removing a leaf from a tree $$T$$, $$T'$$ is still a tree.

Repeatedly remove $$u_i$$ from tree $$T_i$$ to get $$T_{i+1}$$, where $$u_i$$ is the smallest leaf in $$T_i$$. $$u_i$$ has only one edge $$(u_i, v_i)$$, we get Prufer code for $$T$$ with all $$v_i$$s.

2       5
|      /
4--3--1
|   \
6    7

u: 2,4,5,6,3,1
v: 4,3,1,3,1,7


E.g. the tree above has prufer code $$(4,3,1,3,1,7)$$.

For each vertex $$v$$ in $$T$$:

• # of occurrences in $$u_1, \dots, u_{n-1}$$ and $$v_{n-1}$$ is $$1$$,
• # of occurrences in edges $$(u_i, v_i)$$ id $$\deg v$$,
• # of occurrences in $$v_1, \dots, v_{n-2}$$ is $$\deg v - 1$$.

For each $$i$$, the edge $$(u_i, v_i)$$ can be determined because $$u_i$$ is the smallest number not in $$\lbrace u_1, \dots, u_{i-1} \rbrace \cup \lbrace v_i, \dots, v_{n-1} \rbrace$$.

Since the last digit of Prufer code must be $$n$$, there are $$n^{n-2}$$ Prufer code of $$n$$ elements.

Each Prufer code is decodable to a tree, thus there are $$n^{n-2}$$ trees on $$n$$ distinct vertices.

### Double Counting

What is the # of sequences of adding directed edges to an empty graph to form a rooted tree?

From a tree:

• pick a root ($$n$$ vertices)
• pick an order of edges ($$n-1$$ edges in total)

# of sequences are $$T_n \times n \times (n-1)! = n!T_n$$

From an empty graph (all nodes are isolated):

• add edges one by one, each edge eliminates a tree
• after adding $$k$$ edges, there are $$n-k$$ isolated trees remaining
• when adding the next edge, choose any vertex and the root of another tree: $$n \times (n-k-1)$$ methods

Therefore, we have

$n!T_n = \prod_{k=0}^{n-2} n(n-k-1) = n^{n-2}n!$

Thus we reach $$T_n = n^{n-2}$$ again.

## Graph Laplacian

Define adjacency matrix $$A$$, where

$A(i,j) = \begin{cases} 1, & (i,j) \in E, \\ 0, & (i, j) \notin E. \end{cases}$

and diagonal matrix $$D$$, where

$D(i,j) = \begin{cases} \deg i, & i = j, \\ 0, & i \neq j. \end{cases}$

then we define graph Laplacian $$L$$ as $$L = D - A$$.

$$L$$ can be also defined as

$L(i,j) = \begin{cases} \deg i, & i = j, \\ -1, & i \neq j \wedge (i, j) \in E, \\ 0, & \text{otherwise}. \end{cases}$

### Krichhoff's Matrix-Tree Theorem

Define $$L_{i,i}$$ as the submatrix of $$L$$ obtained by removing the $$i$$-th row and $$i$$-th column.

Denote $$t(G)$$ as the number of spanning trees in $$G$$.

Krichhoff's Matrix-Tree Theorem: $\forall i, t(G) = \det(L_{i,i})$

Cauchy-Binet Theorem: $\det(AB) = \sum_{S \in {[m] \choose n}} \det(A_{[n],S}) \det(B_{S,[n]})$

For all $$n$$-vertex trees: they are spanning trees of $$K_n$$, thus

$$L_{i,i} = \begin{bmatrix} n-1 & -1 & \dots & -1 \\ -1 & n-1 & \dots -1 \\ \vdots & \vdots & \ddots & \vdots \\ -1 & -1 & \dots & n-1 \end{bmatrix}$$

thus we obtain Cayley Formula: $T_n = t(K_n) = \det(L_{i,i}) = n^{n-2}.$

# 6. Existence Problems

$$\def\blue{\color{blue}}$$ $$\def\red{\color{red}}$$ $$\def\green{\color{green}}$$

## Circuit Complexity

Gates: $$\wedge$$, $$\vee$$ and $$\neg$$.

The complexity is defined by # of gates.

Theorem (Shannon 1949): There is a boolean function $$f: \lbrace 0, 1 \rbrace^n \rightarrow \lbrace 0, 1 \rbrace$$ which cannot be computed by any circuit with $$\dfrac{2^n}{3n}$$ gates.

## Double Counting

• A party of $$n$$ guests, the # of guests who shake hands an odd number of times is even.
• The sum of degrees in a graph is twice the # of edges.
• Corollary: # of odd-degree vertices is even.

## Sperner's Lemma

Divide a line $${\blue a}{\red b}$$ into small segments, color each end point red or blue.

If $$a$$ and $$b$$ have different color, then there exists a small segment with different colors on two ends.

Divide a triangle $${\blue a}{\red b}{\green c}$$ into small triangles (triangulation) and color each node red, blue or green (each triangle is 3-colored, each line is 2-colored).

Sperner's Lemma (1928): For all properly colored triangulation of a triangle, there exists a tricolored small triangle.

Consider a dual graph, where

• each triangle is a vertex, as well as the outer-space
• add an edge if two triangles share a blue-red edge

Degree of triangle nodes:

• $${\red R}{\green G}{\blue B}$$: $$1$$
• $${\red R}{\blue B}{\blue B}$$ and $${\red R}{\blue B}{\blue B}$$: $$2$$
• other cases: 0

The degree of the outer-space node is odd (because $${\blue a}{\red b}$$ has different colors, there are odd number of segments with different colors).

According to handshaking lemma, the # of odd-degree vertices is even, therefore # of $${\red R}{\green G}{\blue B}$$ triangles must be even.

## Pigeonhole Principle

If $$> mn$$ objects are partitioned into $$n$$ classes, then some class receives $$> m$$ objects.

## Dirichlet's Approximation

Theorem (Dirichlet 1879): Let $$x$$ be a irrational number. For any natural number $$n$$, there is a rational number $$\frac{p}{q}$$ such that $$1 \leqslant q \leqslant n$$ and $\left\vert x - \dfrac{p}{q} \right\vert < \dfrac{1}{nq}$

• fractional part: $$\lbrace x \rbrace = x - \lfloor x \rfloor$$
• $$(n+1)$$ pigeons: $$\lbrace kx \rbrace$$ for $$k = 1, \dots, n+1$$
• $$n$$ holes: $$\left(0, \dfrac{1}{n}\right), \left(\dfrac{1}{n}, \dfrac{2}{n}\right), \dots, \left(\dfrac{n-1}{n}, 1\right)$$

There exists $$\lbrace ax \rbrace$$ and $$\lbrace bx \rbrace$$ in the same hole, therefore

$\vert (a-b) x - (\lfloor ax \rfloor - \lfloor bx \rfloor) \vert = \vert \lbrace ax \rbrace - \lbrace bx \rbrace \vert < \dfrac{1}{n}$

Let $$q = a-b$$, $$p = \lfloor ax \rfloor - \lfloor bx \rfloor$$, we have

$|qx-p| < \dfrac{1}{n} \Leftrightarrow \left\vert x - \dfrac{p}{q} \right\vert < \dfrac{1}{nq}$

## Other Existence Problems

• forall $$S \subseteq [2n]$$ that $$|S| > n$$, there exists $$a, b \in S$$ such that $$a \vert b$$
• consider sets of $$2^km$$ for different $$k$$
• a sequence of $$> mn$$ different numbers must contain either an increasing subsequence of length $$m+1$$, or a decreasing subsequence of length $$n+1$$ (Erdos-Szekeres 1935)
• define $$x_i$$ and $$y_i$$ as the length of longest increasing/decreasing subsequence ending/starting at $$a_i$$
• $$(x_i, y_i) \neq (x_j, y_j)$$ if $$i \neq j$$ (why?)
• $$>mn$$ pigeons, no way to put them into $$mn$$ holes

# 7. The Probabilistic Method

## Tournament

$$T(V,E)$$: $$n$$ players, each pair has a match, $$u$$ points to $$v$$ if and only if $$u$$ beats $$v$$.

$$k$$-paradoxical: For every $$k$$-subset $$S$$ of $$V$$, there is a player in $$V \setminus S$$ who beats all players in $$S$$.

Theorem (Erdős 1963): If $${n \choose k} \left( 1 - 2^{-k} \right)^{n-k} < 1$$ then there is a $$k$$-paradoxical tournament of $$n$$ players.

Proof: Pick a random tournament $$T$$ on $$n$$ players $$[n]$$. (Random $$\rightarrow$$ each player beat the other by probability $$1 / 2$$). For any $$S \in {[n] \choose k}$$, define event $$A_S$$ as no player in $$V \setminus S$$ beat all players in $$S$$.

$Pr[u \in S, \text{ beaten}] = 1 - (1 / 2)^k$

$Pr[A_S] = \left( 1 - 2^{-k} \right)^{n-k}$

Pr[\text{No $$k$$-paradoxical}] \leqslant \sum_{S \in {[n] \choose k}} Pr[A_S] < 1.

## The Probabilistic Method

• Pick random bal from a box, $$Pr[\text{is blue}] > 0 \Rightarrow$$ there is a blue ball.
• Define a probability space $$\Omega$$, and a property $$P$$: $\underset{x}{Pr}[P(x)] > 0$ $$\Rightarrow \exists x \in \Omega$$ with the property $$P$$.

## Averaging Principle

• Average height of the students in class is $$l$$. $$\Rightarrow$$ there is a student of height $$\geqslant l (\leqslant l)$$.
• For a random variable $$X$$,
• $$\exists x \leqslant E[X]$$, such that $$X = x$$ is possible,
• $$\exists x \geqslant E[X]$$, such that $$X = x$$ is possible.

## Hamiltonian Path in Tournament

Hamiltonian path: a path visiting every vertex exactly once.

Theorem (Szele 1943): There is a tournament on $$n$$ players with at least $$n! 2^{-(n-1)}$$ Hamiltonian paths.

Proof Pick a random tournament $$T$$ on $$n$$ players $$[n]$$. For every permutation $$\pi$$ of $$[n]$$, define $X_\pi = \begin{cases} 1, & \pi \text{ is a Hamiltonian path}, \\ 0, & \text{otherwise}.\end{cases}$

$E[X_\pi] = Pr[X_\pi = 1] = (1 / 2)^{n-1}$

$E[X] = \sum_\pi E[X_\pi] = n! 2^{-(n-1)}$

## Large Independent Set

An independent set $$S$$: no adjacent vertices in $$S$$.

Max independent set is NP-hard.

A uniform $$S$$ is very unlikely to be an independent set!

Theorem Graph $$G$$ has $$n$$ vertices and $$m$$ edges, then there exists an independent set $$S$$ of size $$\dfrac{n^2}{4m}$$.

Proof

1. Sample a random $$S$$: each vertex is chosen independently with probability $$p$$
2. modify $$S$$ to $$S^*$$ (an independent set): $$\forall uv \in E$$, if $$u, v \in S$$, then delete one of $$u$$, $$v$$ from $$S$$.

Define $$Y$$: # of edges in $$S$$, we have

$Y = \sum_{uv \in E} Y_{uv}, \ \ \ Y_{uv} = \begin{cases}1, & u, v \in S, \\ 0, &\text{otherwise}.\end{cases}$

$E[\vert S \vert] = np, \ \ \ E[Y] = \sum_{uv \in E} E[Y_{uv}] = mp^2$

$E[\vert S^* \vert] \geqslant E[\vert S \vert] - E[Y] = np - mp^2$

Let $$p = \dfrac{n}{2m}$$, we have $$E[\vert S^* \vert] \geqslant \dfrac{n^2}{4m}$$.

$$\dfrac{n^2}{4m} = \dfrac{n}{2d}$$, where $$d = \dfrac{2m}{n}$$ is the average degree.

## Markov's Inequality

For non-negative $$X$$, for any $$t > 0$$, $Pr[X \geqslant t] \leqslant \dfrac{E[X]}{t}.$

Proof Define $$Y$$ as

$Y = \begin{cases}1, & X \geqslant t, \\ 0, & \text{otherwise}. \end{cases}$

$Y \leqslant \lfloor \dfrac{X}{t} \rfloor \leqslant \dfrac{X}{t},$

$Pr[X \geqslant t] = E[Y] \leqslant E\left[ \dfrac{X}{t} \right] = \dfrac{E[X]}{t}.$

## Chromatic Number

Graph $$G(V,E)$$, define

• girth $$g(G)$$: length of the shortest circle,
• chromatic number $$\chi(G)$$: mnimum number of color to properly color the vertices of $$G$$.

Intuition: large cycles are easy to color.

Theorem (Erdős 1959) For all $$k$$, $$l$$, there exists a finite graph $$G$$ with $$\chi(G) \geqslant k$$ and $$g(G) \geqslant l$$.

Define independence number $$\alpha(G)$$: size of the largest independent set in $$G$$.

$\text{if } \alpha(G) \leqslant \dfrac{n}{k},$

$\text{then } \chi(G) \geqslant \dfrac{n}{\alpha(G)} \geqslant k.$

Theorem' For all $$k$$, $$l$$, there exists a finite graph $$G$$ with $$\alpha(G) \leqslant k$$ and $$g(G) \geqslant l$$.

Define a random graph of $$\vert V \vert = n$$ vertices $$G(n, p)$$: forall $$u, v \in V$$, $$Pr[{u, v} \in E] = p$$ (independently).

A uniform random graph: $$G(n, \dfrac{1}{2})$$.

Plan: fix any large $$k$$, $$l$$, exists $$n$$, generate a random graph $$G \sim G(n, p)$$ and

$\begin{cases}Pr[\alpha(G) > n / k] < 1 / 2, \\ Pr[g(G) < l] < 1 / 2. \end{cases}$

# 9. Extremal Set Theory

What is extremal combinatorics?

How large or how small a collection of finite objects can be, if it has to satisfy certain restrictions.

## Sunflowers

Definition: $$\mathcal{F}$$ is a sunflower of size $$c$$ with center $$C$$ if

• $$|\mathcal{F}| = r$$
• $$\forall S, T \in \mathcal{F}, S \cap T = C$$

If $$\mathcal{F} \subseteq {[n] \choose k}$$ and $$|\mathcal{F}| > k!(r-1)^k$$, then there exists a sunflower $$\mathcal{G} \subseteq \mathcal{F}$$ such that $$|\mathcal{G}| = r$$.

Proof by induction on $$k$$.（太复杂，看讲义）

## Intersecting Families

$$\mathcal{F} \subseteq {[n] \choose k}$$, intersecting means $$\forall S, T \in \mathcal{F}$$, $$S \cap T \neq \emptyset$$.

Trival case: $$n < 2k$$, $$|\mathcal{F}| = 1$$.

How large can a nontrival intersecting family be?

$n \geqslant 2k \ \Longrightarrow \ |\mathcal{F}| \leqslant {n-1 \choose k-1}$

Proof by induction on $$n$$ and $$k$$. (Construct two subfamily by whether contains $$n$$ or not.)

### Shifting

• With fixed perimeter, what plane figure has the largest area?
• With fixed area, what plane figure has the smallest perimeter?

$$\forall T \in \mathcal{F}$$, write $$T_{ij} = (T \setminus \{j\}) \cup \{i\}$$.

$$(i, j)$$-shift $$S_{ij}(\cdot)$$ is defined as

S_{ij}(T) = \begin{cases} T_{ij} & \text{if } j \in T, i \notin T, \text{and } T_{ij} \notin \mathcal{F}, \\ T & \text{otherwise}. \end{cases}

$S_{ij}(\mathcal{F}) = \{S_{ij}(T) | T \in \mathcal{F}\}$

Properties:

• $$|S_{ij}(T)| = |T|$$ and $$S_{ij}(\mathcal{F}) = |\mathcal{F}|$$
• $$\mathcal{F}$$ intersecting $$\Longrightarrow$$ $$S_{ij}(\mathcal{F})$$ intersecting

Repeat applying $$(i,j)$$-shifting $$S_{ij}(\mathcal{F})$$ for all $$1 \leqslant i < j \leqslant n$$. Eventually, $$\mathcal{F}$$ is unchanged by any $$S_{ij}(\mathcal{F})$$, called $$\mathcal{F}$$ is shifted.

True for $$k=1$$. When $$n = 2k$$, at most one of $$S$$ and $$\bar{S}$$ is in $$\mathcal{F}$$, hence

$|\mathcal{F}| \leqslant \dfrac{1}{2}{n \choose k} = {n-1 \choose k-1}$

When $$n > 2k$$, induction on $$n$$. Suppose $$\mathcal{F}$$ is shifted (without loss of generality = WLOG), let

$\mathcal{F}_1 = \{ S \in \mathcal{F} | n \in S \}, \mathcal{F}_1' = \{ S \setminus \{n\} | S \in \mathcal{F}_1 \}$

We can prove that $$\mathcal{F}_1'$$ is intersecting (otherwise leads to a contradiction).

Let $$\mathcal{F}_0 = \{S \in \mathcal{F} | n \in S\}$$, we know $$\mathcal{F}_0$$ is intersecting. Therefore by induction hypothesis,

$|\mathcal{F}| \leqslant |\mathcal{F}_0| + |\mathcal{F}_1| \leqslant {n-2 \choose k-1} + {n-2 \choose k-2} = {n-1 \choose k-1}.$

### Katona's Proof

• $$k$$-arc: length $$k$$ path on a $$n$$-cycle
• intersecting arcs: arcs that share edges

Lemma: $$n \geqslant 2k$$. Suppose $$A_1, A_2, \dots, A_t$$ are distinct pairwise intersecting $$k$$-arcs, then $$t \leqslant k$$.

Proof: take an $$n$$-cycle $$\pi$$ of $$[n]$$, the family of all $$k$$-arcs in $$\pi$$ are

$\mathcal{G}_\pi = \{\{ \pi_{(i+j) \bmod n} | j \in [k] \} | i \in [n] \}.$

Double counting on $$X = \{ (S, \pi) | S \in \mathcal{F} \cap \mathcal{G}_\pi \}$$:

• Each $$n$$ cycle has at most $$k$$ intersecting $$k$$-arcs, there are $$(n-1)!$$ $$n$$-cycles, thus $|X| \leqslant k(n-1)!$
• Each $$S$$ is a $$k$$-arc in $$k!(n-k)!$$ cycles , thus $|X| = \sum_{S \in \mathcal{F}} |\{\pi | S \in \mathcal{G}_\pi\}| = |\mathcal{F}| k! (n-k)!$

Therefore we have $$|\mathcal{F}| \leqslant \dfrac{k(n-1)!}{k!(n-k)!} = \dbinom{n-1}{k-1}$$.

## Antichains

Definition: $$\mathcal{F} \subseteq 2^{[n]}$$ is an antichain if $$\forall A, B \in \mathcal{F}, A \nsubseteq B$$.

Theorem (Sperner 1928): For any antichain $$\mathcal{F}$$,

$\mathcal{F} \leqslant {n \choose \lfloor n/2 \rfloor}.$

For $$\mathcal{F} \subseteq {[n] \choose k}$$, define

• shade: $\nabla \mathcal{F} = \left\{ T \in {[n] \choose k+1} \vert \exists S \in \mathcal{F}, S \subset T \right\}$
• shadow: $\Delta \mathcal{F} = \left\{ T \in {[n] \choose k-1} \vert \exists S \in \mathcal{F}, T \subset S \right\}$

Lemma (Sperner): Let $$\mathcal{F} \subseteq {[n] \choose k}$$, then

• for $$k < n$$, $$|\nabla \mathcal{F}| \geqslant \frac{n-k}{k+1} |\mathcal{F}|$$,
• for $$k > 0$$, $$|\Delta \mathcal{F}| \geqslant \frac{k}{n-k+1} |\mathcal{F}|$$.

Corollary:

• If $$k \leqslant \frac{1}{2}(n-1)$$, then $$|\nabla \mathcal{F}| \geqslant |\mathcal{F}|$$.
• If $$k \geqslant \frac{1}{2}(n+1)$$, then $$|\Delta \mathcal{F}| \geqslant |\mathcal{F}|$$.

When $$k = \lfloor n/2 \rfloor$$, there is no decreasing of $$|\mathcal{F}|$$.

### Lubell's Proof

Length of a maximal chain in $$2^{[n]}$$ is $$n$$, # of maximal chains in $$2^{[n]}$$ is $$n!$$.

For all $$S \subseteq [n]$$, # of maximal chains containing $$S$$ is $$|S|! (n-|S|)!$$.

By definition, we have $\mathcal{F} \text{ is antichain} \Longrightarrow \forall C \text{ is chain}, |\mathcal{F} \cap C| \leqslant 1.$

Therefore # of maximal chains crossing $$\mathcal{F} \leqslant$$ # of all maximal chains.

$\sum_{S \in \mathcal{F}} |S|!(n-|S|)! \leqslant n!$

Since $${n \choose |S|} \leqslant {n \choose \lfloor n/2 \rfloor}$$, we can then conclude that $$|\mathcal{F}| \leqslant {n \choose \lfloor n/2 \rfloor}$$.

### LYM Inequality

LYM inequality: $$\mathcal{F} \subseteq 2^{[n]}$$ is an antichain, $\sum_{S \in \mathcal{F}} \dfrac{1}{{n \choose |S|}} \leqslant 1.$

Alon's proof (the probabilistic method): let $$\pi$$ be a random permutation of $$[n]$$, define

$\mathcal{C}_\pi = \{ \{\pi_1\}, \{\pi_1, \pi_2\}, \dots \}$

For all $$S \in \mathcal{F}$$, define random variable $$X_S = 1$$ iff $$S \in \mathcal{C}_\pi$$.

Let $$X = \sum\limits_{S \in \mathcal{F}} X_S = |\mathcal{F} \cap \mathcal{C}_\pi|$$. Since $$\mathcal{C}_\pi$$ contains precisely 1 $$|S|$$-set, we have

$E[X_S] = Pr[S \in \mathcal{C}_\pi] = \dfrac{1}{{n \choose |S|}}.$

Since $$\mathcal{F}$$ is antichain, we know

$X = \sum_{S \in \mathcal{F}} X_S = |\mathcal{F} \cap \mathcal{C}_\pi| \leqslant 1$

thus by probability method we know that $$1 \geqslant E[X] = \sum\limits_{S \in \mathcal{F}} E[X_S]$$ and thus LYM inequality is true.

## Shattering

Let $$\mathcal{F} \subseteq 2^{[n]}, R \subseteq [n]$$, define

• trace $$\mathcal{F}|_R = \{ S \cap R | S \in \mathcal{F} \}$$
• $$\mathcal{F}$$ shatters $$\mathcal{R}$$ if $$\mathcal{F}|_R = 2^R$$.

Sauer's Lemma: if $$|\mathcal{F}| > \sum\limits_{0 \leqslant i < k}{n \choose i}$$, then $$\exists R \in {[n] \choose k}$$ such that $$\mathcal{F}$$ shatters $$R$$.

Define VC-dimension of $$\mathcal{F}$$: size of the largest $$R$$ shattered by $$\mathcal{F}$$.

$\text{VC-dim}(\mathcal{F}) = \max \{ |R| | R \subseteq [n], \mathcal{F}|_R = 2^R \}$

### Heredity

$$\mathcal{F}$$ is hereditary if $$\forall B \subseteq A \in \mathcal{F}$$, $$B \in \mathcal{F}$$.

For any hereditary $$\mathcal{F}$$,

$\forall B \subseteq A \in \mathcal{F}, B \in \mathcal{F}$

therefore

$R \in \mathcal{F} \Longrightarrow \mathcal{F} \text{ shatters } R.$

### Down Shift

Define down-shift $$S_i(\cdot)$$:

$S_i(T) = \begin{cases} T \setminus \{i\} & \text{if } i \in T \in \mathcal{F}, \text{and } T \setminus \{i\} \notin \mathcal{F}, \\ T & \text{otherwise} \end{cases}$

$S_i(\mathcal{F}) = \{S_i(T) | T \in \mathcal{F}\}$

Properties:

• $$|S_i(\mathcal{F})| = |\mathcal{F}|$$
• $$|S_i(\mathcal{F})|_R| \leqslant |\mathcal{F}|_R|$$ for all $$R \subseteq [n]$$
• $$S_i(\mathcal{F})|_R \subseteq S_i(\mathcal{F}|_R)$$

Repeat applying down-shifting to $$\mathcal{F}$$ until $$\mathcal{F}$$ is unchanged by any $$S_i(\cdot)$$, then $$\mathcal{F}$$ is hereditary.

Since $$|\mathcal{F}| > \sum\limits_{0 \leqslant i < k} {n \choose i}$$, there exists a $$k$$-size subset $$R$$ of $$\mathcal{F}$$, thus $$\mathcal{F}$$ shatters $$R$$.

## Kruskal-Katona Theorem

How small can the shadow $$\Delta \mathcal{F}$$ be?

### Colex Order of Sets

• Lexicographic order: elements in increasing order, sets in lexicographic order.
• Co-lexicographic (colex) order: elements in decreasing order, sets in lexicographic order.

Define $$\mathcal{R}(m,k)$$ as the first $$m$$ members of $${\mathbb{N} \choose k}$$ in colex order.

$\mathcal{R} \left( {n \choose k}, k \right) = {[n] \choose k}$

### $$k$$-cascade Representation

For any positive integers $$m$$ and $$k$$, $$m$$ can be uniquely represented as

$m = \sum_{l=t}^{k} {m_l \choose l}.$

### K-K Theorem

$$\mathcal{F} \subseteq {[n] \choose k}$$, $$|\mathcal{F}| = m$$, the $$k$$-cascade of $$m$$ is $m = {m_k \choose k} + {m_{k-1} \choose k-1} + \dots + {m_t \choose t},$ then $|\Delta \mathcal{F}| \geqslant {m_k \choose k-1} + {m_{k-1} \choose k-2} + \dots + {m_t \choose t-1}.$

The first $$m$$ $$k$$-sets in colex order have the smallest shadow.

$|\Delta \mathcal{F}| \geqslant |\Delta \mathcal{R}(|\mathcal{F}|, k)|$

# 10. Ramsey Theory

• In any party of six people, either at least three of them are mutual strangers or at least three of them are mutual acquaintances.
• Color edges of $$K_6$$ with 2 colors, there must be monochromatic $$K_3$$.

Define $$R(k, l)$$ as the smallest integer satisfying: if $$n \geqslant R(k, l)$$, for any 2-coloring of $$K_n$$ there exists a red $$K_k$$ or a blue $$K_l$$.

## Ramsey Theorem

Ramsey Theorem: $$R(k, l)$$ is finite.

• $$R(3, 3) = 6$$
• $$R(k, 2) = k, R(2, l) = l$$ (why?)
• $$R(k, l) \leqslant R(k, l-1) + R(k-1, l)$$ (why?)

Take $$n = R(k, l-1) + R(k-1, l)$$ and an arbitrary node $$v$$, split $$n-1$$ nodes into two sets $$S$$ and $$T$$, where edges between $$v$$ and $$S$$ are blue, edges between $$v$$ and $$T$$ are red. Then discuss on the size of $$|S|$$ and $$|T|$$:

• $$|S| \geqslant R(k, l-1)$$: either $$K_k \subseteq S$$ or $$K_{l-1} \subseteq S$$, in the latter case $$K_l \subseteq S \cup \lbrace v \rbrace$$.
• $$|T| \geqslant R(k-1, l)$$: either $$K_{k-1} \subseteq T$$ or $$K_l \subseteq T$$, in the former case $$K_k \subseteq T \cup \lbrace v \rbrace$$.

### Upper Bound

By induction using $$R(k,l) \leqslant R(k,l-1) + R(k-1,l)$$, we can conclude that $R(k,l) \leqslant {k+l-2 \choose k-1}$

therefore $$R(k,l)$$ is finite and we complete the proof of Ramsey Theorem.

### Lower Bound

For a uniformly and independently random 2-coloring of $$K_n$$, each edge is red/blue with probability $$1 / 2$$.

Associate each $$k$$-size subset of $$[n]$$ $$S$$ with an event $$A_S$$ defined as $$S$$ is a monochromatic $$K_k$$, we know that $Pr[A_S] = \dfrac{2}{2^{{k \choose 2}}} = 2^{1-{k \choose 2}}$

For any subset $$S$$ and $$T$$, $$A_S$$ and $$A_T$$ are dependent if $$|S \cap T| \geqslant 2$$. Therefore the max degree in the dependency graph is (choose the $$2$$ nodes in both sets first and choose other $$k-2$$ nodes) $d \leqslant {k \choose 2}{n-2 \choose k-2} \leqslant {k \choose 2}{n \choose k-2}$

For some $$n = ck2^{k / 2}$$ with constant $$c$$, $e 2^{1-{k \choose 2}} (d+1) \leqslant 1$

and by Lovasz Local Lemma, $$Pr\left[ \bigwedge\limits_{S \in {[n] \choose k}} \overline{A_S} \right] > 0$$, thus we know that $R(k,k) \geqslant n = \Omega(k 2^{k / 2})$

$\Omega(k 2^{k / 2}) \leqslant R(k, k) \leqslant {2k-2 \choose k-1} = O \left( \dfrac{4^k}{\sqrt{k}} \right)$

### Multicolor

Similarly, define $$R(r; k_1, k_2, \dots, k_r)$$: if $$n \geqslant R(r; k_1, k_2, \dots, k_r)$$, for any $$r$$-coloring of $$K_n$$, there exists a monochromatic $$k_i$$-clique with color $$i$$.

The mixing color trick:

$R(r; k_1, \dots, k_{r-2}, k_{r-1}, k_r) \leqslant R(r-1; k_1, \dots, k_{r-2}, R(2; k_{r-1}, k_r))$

Ramsey Theorem: $$R(r; k_1, k_2, \dots, k_r)$$ is finite.

### Hypergraph

If $$n \geqslant R_t(r; k_1, k_2, \dots, k_r)$$, then for any $$r$$-coloring of $${[n] \choose t}$$ there exists a monochromatic $${S \choose t}$$ with color $$i$$ and $$|S| = k_i$$ for smoe $$i$$.

A complete $$t$$-uniform hypergraph $${[n] \choose t}$$

$$r$$-coloring function $$f: {[n] \choose t} \rightarrow \lbrace 1, 2, \dots, r \rbrace$$

### Partition of Set Family

If $$n \geqslant R_t(r; k_1, k_2, \dots, k_r)$$, then for any $$r$$-partition of $${[n] \choose t} = C_1 \cup \dots \cup C_r$$, there exists an $$S \subseteq [n]$$ such that $$|S| = k_i$$ and $${S \choose t} \subseteq C_i$$ for some $$i$$.

Erdos-Rado partition arrow $$n \rightarrow (k_1, k_2, \dots, k_r)^t$$

Theorem by Ramsey:

• $$R_t(r; k_1, k_2, \dots, k_r)$$ is finite.
• $$R_t(r; k) \overset{\Delta}{=} R_t(r; k, \dots, k)$$ is finite.

## Happy Ending Problem

Any 5 points in the plane with no three on a line, has a subset of 4 points that form a convex quadrilateral.

Theorem (Erdos-Szekeres 1935): $$\forall m \geqslant 3$$, $$\exists N(m)$$ such that any set of $$n \geqslant N(m)$$ points in the plane with no three on a line, contains $$m$$ points that are the vertices of a convex $$m$$-gon. （凸$$m$$边形）

A convex polygon:

• The line between any two nodes in the polygon is completely in the polygon.
• No vertice is covered by the triangles formed by other three vertices.

Result: $$N(m) = R_3(2; m, m)$$ (why?)

For any set of points in the plane with no 3 on a line, denoted as $$X$$, $$|X| \geqslant N(m)$$. For all $$f: {X \choose 3} \rightarrow \lbrace 0, 1 \rbrace$$, $$\exists S \subseteq X$$, $$|S| = m$$ that there is a monochromatic $${S \choose 3}$$.

We claim that $$S$$ is a convex $$m$$-gon. (why?) For all $$a, b, c \in X$$, define $$\Delta_{abc}$$ as the # of points in triangle $$abc$$. $f(\lbrace a, b, c \rbrace) = |\Delta_{abc}| \bmod 2$

In this case, if there is point $$d$$ in triangle $$abc$$, then we have $f(abc) = f(abd) + f(acd) + f(bcd) + 1$ which is impossible because $${S \choose 3}$$ cannot be monochromatic if this equation holds.

## Data Structures

• Data universe $$[N]$$
• Key $$x \in [N]$$
• Data set $$S \in {[N] \choose n}$$

Problem: is $$x \in S$$?

Solution: sorted table as data structure

Complexity: $$\geqslant \log_2 n$$ memory accesses in the worst case

Theorem (Yao 1981): If $$N \geqslant 2n$$, on sorted table, any search algorithm requires $$\Omega(\log n)$$ accesses in the worst-case.

Proof by induction on $$n$$ using equation （具体看讲义） $1 + \log \dfrac{n}{2} = \log n$

# 期末复习

## 1 - 基本计数

balls per binany$$\leqslant 1$$$$\geqslant 1$$
$$n$$ distinct balls, $$m$$ distinct bins$$m^n$$$$(m)_n$$$$m!{n \brace m}$$
$$n$$ identical balls, $$m$$ distinct bins$$\left({m \choose n}\right)$$$${m \choose n}$$$${n-1 \choose m-1}$$
$$n$$ distinct balls, $$m$$ identical bins$$\sum\limits_{k=1}^{m} {n \brace k}$$$$\begin{cases}1 \text{ if } n \leqslant m \\ 0 \text{ if } n > m\end{cases}$$$${n \brace m}$$
$$n$$ identical balls, $$m$$ identical bins$$\sum\limits_{k=1}^m p_k(n)$$$$\begin{cases}1 \text{ if } n \leqslant m \\ 0 \text{ if } n > m\end{cases}$$$$p_m(n)$$

• 二项式系数 ${n \choose k} = \dfrac{n!}{k!(n-k)!}$
• $$n$$个不同的篮子放$$k$$个不同的球，每个篮子最多一个（单射、$$n$$的$$k$$个元素的排列）： $(n)_k = \begin{cases} \dfrac{n!}{(n-k)!} & k \leqslant n, \\ 0, & k > n. \end{cases}$
• $$n$$个不同的篮子放$$k$$个相同的球（$$n$$大小集合的$$k$$-multiset，一个球代表对应的元素出现一次；插板法）： $\left({n \choose k}\right) = {n+k-1 \choose n-1} = {n+k-1 \choose k}$
• $$n$$个相同的篮子放$$k$$个不同的球，每个篮子至少一个球（集合划分成恰好$$k$$份，考虑最后一个元素加入前$$k$$个子集或者单独成一个子集）： ${n \brace m} = k{n-1 \brace k} + {n-1 \brace k-1}$
• $$n$$个相同的篮子放$$k$$个相同的球，每个篮子至少一个球（整数划分成恰好$$k$$份）：
• $$p_k(n) = p_{k-1}(n-1) + p_k(n-k)$$（考虑所有项都大于1或者把1去掉）
• $$p_k(n) = \sum\limits_{j=1}^k p_j(n-k)$$（把整数$$n$$划分成$$k$$份等价于划分成若干份，其中最大值为$$k$$）

## 2 - 生成函数

• 写出$$a_n$$的递归定义（如$$a_n = a_{n-1} + a_{n-2}$$）
• 两边同时乘以$$x^n$$，左边即为生成函数$$G(x)$$，并将右边化为$$G(x)$$的形式
• 求解$$G(x)$$，得到关于$$x$$的函数
• 对$$G(x)$$进行级数展开，得到$$a_n$$
• 泰勒展开：$$G(x) = \sum\limits_{n \geqslant 0} \dfrac{G^{(n)}(0)}{n!} x^n$$
• 几何级数展开：$$\dfrac{1}{1-z} = \sum\limits_{n \geqslant 0} z^n$$
• Newton's Formula：$$(1+x)^\alpha = \sum\limits_{n \geqslant 0} {\alpha \choose n} x^n$$

• shift：$$x^kG(x) = \sum\limits_{n \geqslant k} g_{n-k} x^n$$
• addition：$$F(x) + G(x) = \sum\limits_{n \geqslant 0} (f_n + g_n) x^n$$
• convolution：$$F(x)G(x) = \sum\limits_{n \geqslant 0} \sum\limits_{n=0}^k f_k g_{n-k} x^n$$
• differentiation：$$G'(x) = \sum\limits_{n \geqslant 0} (n+1) g_{n+1} x^n$$

## 3 - 筛法

$|A_1 \cup \dots \cup A_2| = - S_0 + S_1 - S_2 + S_3 + \dots + (-1)^{n-1} S_n$ $|\bar{A_1} \cap \dots \cap \bar{A_2}| = S_0 - S_1 + S_2 - S_3 + \dots + (-1)^{n} S_n$

$$[n]$$到$$[m]$$的满射的数量：

• 定义坏事件$$A_i$$为$$[m]$$中的$$i$$不在值域中，有$$|A_i| = (m-1)^{n}$$个映射满足条件，
• 定义坏事件$$A_I$$为$$[m]$$中的子集$$I$$不在值域中，$$|A_i| = (m-|I|)^{n}$$，
• 带入筛法得到满射的数量是$$\sum\limits_{k=1}^m (-1)^{m-k} {m \choose k} k^n$$。

${n \brace m} = \dfrac{1}{m!}\sum\limits_{k=1}^m (-1)^{m-k} {m \choose k} k^n$

• 定义坏事件$$A_I$$为在新排列中$$I$$中元素的位置没变，有$$(n-|I|)!$$种排列
• 带入求得错排的个数约为$$\dfrac{n!}{e}$$

• 将排列转换为一组二维坐标
• 假设$$B$$是一个不符合条件的位置的集合
• $$r_k$$表示在$$B$$中选$$k$$个不同的位置的方法
• 则满足条件的$$n$$排列的个数为$$N_0 = \sum\limits_{k=0}^n (-1)^k r_k (n-k)!$$

Polya计数法不考

## 5 - Cayley公式

$$n$$个不同的点组成的树的个数为$$n^{n-2}$$。

Repeatedly remove $$u_i$$ from tree $$T_i$$ to get $$T_{i+1}$$, where $$u_i$$ is the smallest leaf in $$T_i$$. $$u_i$$ has only one edge $$(u_i, v_i)$$, we get Prufer code for $$T$$ with all $$v_i$$s.

2       5
|      /
4--3--1
|   \
6    7

u: 2,4,5,6,3,1
v: 4,3,1,3,1,7


E.g. the tree above has prufer code $$(4,3,1,3,1,7)$$.

For each $$i$$, the edge $$(u_i, v_i)$$ can be determined because $$u_i$$ is the smallest number not in $$\lbrace u_1, \dots, u_{i-1} \rbrace \cup \lbrace v_i, \dots, v_{n-1} \rbrace$$.

• 双重计数（数两遍）
• 编码与解码（将一棵树转换为一个编码）
• 构造双射求出个数

## 6 - 存在性问题

• 组合中存在两个数可以互相整除（考虑2的幂次）
• 单调增/减序列（将最长增/减序列的长度转换为二维坐标）
• Dirichlet's approximation：将$$[0, 1]$$划分为$$n$$个区间，填入$$n+1$$个数

## 7 - 概率法

Theorem: Let $$G(V, E)$$ be a graph on $$n$$ vertices with $$m$$ edges. Then $$G$$ has an independent set with at least $$\dfrac{n^2}{4m}$$ vertices.

• 设计事件
• 边的方向以$$1 / 2$$的概率随机
• 点/边以$$p$$为概率被选入集合中（此后求解使期望最小/大的$$p$$值）
• 求解概率
• 直接计算概率，可能会用到$$(1-p)^x = e^{-px}$$
• 利用$$E \left[ \sum\limits_{i=1}^n a_i X_i \right] = \sum\limits_{i=1}^n a_i \cdot E[X_i]$$求随机变量的期望

Lovasz Local Lemma：

• 条件1：对任意的$$i$$，$$Pr[A_i] \leqslant p$$
• 条件2：事件的依赖图中的最大度数为$$p$$，且$$ep(d+1) \leqslant 1$$
• 则$$Pr\left[ \bigwedge\limits_{i=1}^n \bar{A_i} \right] > 0$$

## 8 - 极值图论

Mantel's Theorem: Suppose $$G(V, E)$$ is a graph on $$n$$ vertices without triangles, then $$|E| \leqslant \dfrac{n^2}{4}$$.

Turan's Theorem: Let $$G(V, E)$$ be a graph with $$|V| = n$$. If $$G$$ has no $$r$$-clique, $$r \geqslant 2$$, then $$|E| \leqslant \dfrac{r-2}{2(r-1)} n^2$$.

## 9 - 极值集合论

If $$\mathcal{F} \subseteq {[n] \choose k}$$ and $$|\mathcal{F}| > k!(r-1)^k$$, then there exists a sunflower $$\mathcal{G} \subseteq \mathcal{F}$$ such that $$|\mathcal{G}| = r$$.

$n \geqslant 2k \ \Longrightarrow \ |\mathcal{F}| \leqslant {n-1 \choose k-1}$

Theorem (Sperner 1928): For any antichain $$\mathcal{F}$$,

$|\mathcal{F}| \leqslant {n \choose \lfloor n/2 \rfloor}.$

## 10 - Ramsey理论

Define $$R(k, l)$$ as the smallest integer satisfying: if $$n \geqslant R(k, l)$$, for any 2-coloring of $$K_n$$ there exists a red $$K_k$$ or a blue $$K_l$$.

Ramsey Theorem:

• $$R(k, l)$$ is finite.
• $$R(r; k_1, k_2, \dots, k_r)$$ is finite.
• $$R_t(r; k_1, k_2, \dots, k_r)$$ is finite.
• $$R_t(r; k) \overset{\Delta}{=} R_t(r; k, \dots, k)$$ is finite.

Theorem (Erdos-Szekeres 1935): $$\forall m \geqslant 3$$, $$\exists N(m)$$ such that any set of $$n \geqslant N(m)$$ points in the plane with no three on a line, contains $$m$$ points that are the vertices of a convex $$m$$-gon. （凸$$m$$边形）

$N(m) = R_3(2; m, m)$

## 11 - 匹配论

System of distince representatives (SDR) for a sequence of sets $$S_1, S_2, \dots, S_m$$ is a sequence of distince elements $$x_1, x_2, \dots, x_m$$ such that $$x_i \in S_i$$.

Hall's Theorem: The sets $$S_1, S_2, \dots, S_m$$ have a system of distince representatives (SDR) if and only if $$\left\vert \bigcup\limits_{i \in I} S_i \right\vert \geqslant |I|$$ for all $$I \subseteq [m]$$.

The condition $$\left\vert \bigcup\limits_{i \in I} S_i \right\vert \geqslant |I|$$ is called the Hall's condition.