Lesson 1

  • combinatorial $\sim$ discrete & finite

    • solution combinatorial object
    • constraint combinatorial structure

  • Enumeration: How many solutions satisfying the constraints

  • Existence: Does there exist a solution
  • Extremal: How large/small a solution can be to preserve/avoid structure
  • Ramsey: when a solution is sufficiently large, some structures must emerge
  • Optimization: find the optimal solution

  • Construction: construct a solution

  • Enumeration(Counting)

    • How many ways are there:
      1. $n!$ to rank $n$ people
      2. $12^n$ to assign $m$ zodiac signs to $n$ people
      3. $n \choose m$ to choose $m$ people out of $n$ people
      4. $n-1 \choose m-1$ to partition $n$ people into $m$ groups
      5. $?$ to distribute $m$ yuan to $n$ people
      6. $?$ to partition $m$ yuan to $n$ parts
Name Description Notation Number Repetition Ordered
Tuple $n$-tuples of $[m]$ $[m]^n$ $m^n$ Y Y
Nultiset $k$-multiset of $n$-set - ${n+k-1\choose k}$ Y N
Subset $k$-uniform of $n$-set, $\ S\ =n$ - $\binom{n}{k}$ N N
Partition $k$-partition of $n$-set - $\{ {n\atop k} \}$ N N
  • The product rule: $|S\times T|=|S|\cdot|T|$
  • The bijection rule: if there exists a bijection between finite sets $S$ and $T$, then $|S|=|T|$.
  • Tuples
    • $[m]=\{1,2,\cdots,m\}$
    • $[m]^n=[m] \times [m] \times\cdots\times [m]$
    • $#$ of tuples: $|[m]^n|=m^n$
  • Functions
    • $f:[n]\to[m]$
    • $#$ of functions: $m^n$

      Proof: $f:[n]\to[m]\Leftrightarrow v_f\in[m]^n$

  • Subsets
    • Power set: $2^{[n]}={S|S\subseteq [n]}$
    • $|2^{[n]}|=2^n$
    • Proof: $S\subseteq [n]\leftrightarrow \{0,1\}^n$
  • Subsets of fixed size
    • $#$ of $k$-uniform: ${n \choose k}=\frac{n!}{k!(n-k)!}$
    • $(n)_k=n(n-1)\cdots(n-k+1)$ is $n$ lower factorial of $k$
  • Binomial coefficients
    • ${n \choose k}={n\choose n-k}$
    • $\sum_{k=0}^{n}{n \choose k}=2^n$
    • $(1+x)^n=\sum_{k=0}^{n}{n \choose k}x^k$

      Proof: $(1+x)^n=(1+x)(1+x)\cdots(1+x)$, $#$ of $x^k$ is $n\choose k$

    • $S=\{x_1, x_2,\cdots,x_n\}$, $#$ of odd subsets $=$ $#$ of even subsets

      proof: let $x=-1$

  • Compositions of an integer
    • $k$-composition of $n$: $k$-tuple that $x_1+x_2+\cdots+x_n=n$, $x_i\in\{1,2,\cdots x_n\}$
    • $#$ of $k$-composition: $n-1 \choose k-1$
    • weak $k$-composition of $n$: $x_i$ can be 0, aka $(x_1+1)+(x_2+1)+\cdots+(x_n+1)=n+k$
    • $#$ of weak $k$-composition: $n+k-1\choose k-1$
  • Multisets
    • Combinations with repetitions can be formally defined as multisets.
    • $({n \choose k})={n+k-1\choose k}$
  • Multinomial coefficients
    • $\binom{n}{m_1,m_2,\cdots, m_k}=\frac{n!}{m_1!m_2!\cdots m_k!}$, $\sum_i m_i=n$
    • $\binom{n}{m, n-m}=\binom{n}{m}$
    • $(x_1,x_2,\cdots,x_k)^n=\sum_{m_1+m_2+\cdots+m_k=n}\binom{n}{m_1,m_2,\cdots, m_k}x_1^{m_1}\cdots x_k^{m_k}$
  • Partitions of a set
    • partition of $S$: $P={S_1,S_2,\cdots,S_k}$, $S_i\ne\emptyset$, $S_i\cap S_j$ if $i\ne j$, $\bigcup S_i=S$
    • if $|P|=k$, then $P$ is a $k$-partition of $S$
    • $#$ of $k$-partitions of a $n$-set is $\{ {n\atop k} \}$
    • Stirling number of the second kind
  • The twelvfold way
$n$ balls $m$ bins unrestricted $\leq 1$ for all bin $\geq 1$ for all bin
distinct distinct $m^n$ $(m)_n=n!\binom{m}{n}$ $m!\{ {n\atop m} \}$
identical distinct $(\binom{m}{n})$ $m\choose n$ $\binom{m-1}{n-1}$
distinct identical $\sum_{k=1}^m\{ {n\atop k} \}$ $1$ $\{ {n\atop m} \}$
identical identical $-$ $-$ $-$