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 bin	any	$\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

把$n$个人分到$k$艘船上，每艘船至少一个人

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