组合数学之基础计数

The twelvefold way

  • $f: N\to M$, $|N|=n$, $|M|=m$

12foldway1

  • 等价于

12foldway2

Basic Enumation

Tuples

  • $[m]=\\{0,1,2,\cdots, m-1\\}$

  • $n$-tuple of $[m]$: $[m]^n$

  • $|[m]^n|=m^n$, 可以通过The product rule严格证明

  • The product rule: 对于任意有限集$S$和$T$, $|S\times T|=|S|\cdot|T|$

Functions

考虑计算$[n]$到$[m]$的映射数问题.

  • 等价于数$[m]$的$n$-tuple数
  • 对于任意$f:[n]\to[n]$, 定义一个tuple$v_f\in [m]^n$, $v_f(i)=f(i-1)$, $i=1,2,\cdots, n$. 易证这是个双射.
  • The bijection rule: 如果在有限集$|S|$和$|T|$之间存在双射, 则$|S|=|T|$
  • 因此$[n]$到$[m]$的映射数等于$[m]^n$的tuple数, 即$m^n$

Subsets

数一个集合的子集数.

  • $S=\\{x_1,x_2,\cdots, x_n\\}$为$n$元集, $2^S=\\{T|T\subset 2^S\\}$为$S$所有子集的集合, 即$S$的幂集.

  • 下证$|2^S|=2^n$:

    • 每个$T\in 2^S$对应一个独特的位向量$v\in \\{0,1\\}^S$, $v_i$对应是否$x_i\in T$.

    • 定义映射$\phi: 2^S\to \\{0,1\\}^n$, $\phi(T)=(v_1,v_2\cdots,v_n)$, 其中

    • 易证$\phi$也是双射

    • 因此$|2^S|=|\\{0,1\\}^n|=2^n$

  • 证法2:

    • 定义$f(n)=|2^{S_n}|$, $S_n=\\{x_1,x_2, \cdots, x_n\\}$.
    • 证明$f(n)=2f(n-1)$. (分含不含$x_n$的情况)
    • $f(0)=1$
    • 因此$|2^S|=f(n)=2^n$

Subsets of fixed size

某集合的固定大小的子集的数量

  • 定义$\left(\begin{array}{cc} S \\\\k \end{array}\right)$为$S$的$k$元子集. $\left(\begin{array}{cc} S \\\\k \end{array}\right)=\\{T\subseteq S||T|=k\\}$. $\left(\begin{array}{cc} n \\\\k \end{array}\right)=\left|\left(\begin{array}{cc} S \\\\k \end{array}\right)\right|$, 读作”n选k”
  • 定理: $\left(\begin{array}{cc} n \\\\k \end{array}\right)=\frac{n(n-1)\cdots(n-k+1)}{k(k-1)\cdots 1}=\frac{n!}{k!(n-k)!}$, 常记做$(n)_k$

Binomial coefficient

  • $\left(\begin{array}{cc} n \\\\k \end{array}\right)=\left(\begin{array}{cc} n \\\\n-k \end{array}\right)$
  • $\sum_{k=0}^n \left(\begin{array}{cc} n \\\\k \end{array}\right)=2^n$

  • 二项式定理: $(1+x)^n=\sum_{k=0}^n \left(\begin{array}{cc} n \\\\k \end{array}\right)x^k$

  • 推论: $n$元集的奇数势子集和偶数势子集数量相同

Compositions of an integer

  • $n$的composition为将$n$表示为有序的正整数的和. $n$的$k$-composition是将$n$表示为$k$个有序的正整数的和

  • 形式化地, $n$的$k$-composition是一个$k$-tuple$(a_1,a_2,\cdots,a_k)\in\\{1,2,\cdots,n\\}^k$, 满足$a_1+a_2+\cdots +a_k=n$.

  • 根据隔板法(略), $n$的$k$-composition数为$\left(\begin{array}{cc} n -1 \\\\k -1\end{array}\right)$

  • 严格证明: 构建$n$的$k$-composition和$\left(\begin{array}{cc} \\{1,2,\cdots, n-1\\} \\\\k-1 \end{array}\right)$之间的双射:

    • $\phi((a_1,a_2,\cdots,a_k))=\\{a_1,a_1+a_2,\cdots, a_1+a_2+\cdots+a_{k-1}\\}=\\{\sum_{i=1}^ja_i|1\le j<k \\}$
    • 将每个$k$-composition映射到$\\{1,2,\cdots,n-1\\}$的一个$(k-1)$子集, 易证为双射, 得证.
  • $n$的$k$-composition等价于$x_1+x_2+\cdots+x_k=n$的正整数解的数量, 而$x_1+x_2+\cdots+x_k=n$的非负整数解称作$n$的弱$k$-composition.

    • $n$的弱$k$-composition是tuple$(x_1,x_2,\cdots,x_k)\in [n+1]^k$满足$x_1+x_2+\cdots+x_k=n$
    • 对于一个$n$的弱$k$-composition$(x_1,x_2,\cdots, x_k)$, 我们定义$y_i=x_i+1>0$, 则$y_1+y_2+\cdots+y_k=n+k$, $(y_1,y_2,\cdots,y_k)$是$n+k$的$k$-composition.
    • 因此$n$的弱$k$-composition数为$\left(\begin{array}{cc} n+k -1 \\\\k -1\end{array}\right)$
  • 下面数$x_1+x_2+\cdots+x_k\le n$的非负整数解.

    • 令$x_{k+1}=n-(x_1+x_2+\cdots+x_k)\ge 0$. 因此$x_1+x_2+\cdots+x_{k+1}=n$.
    • 问题转化为上式的非负整数解的数量. 答案是$\left(\begin{array}{cc} n + k \\\\k\end{array}\right)$

Multisets

  • $n$的$k$子集也称为$k$-combination of $S$ without repetitions. 下面考虑$k$-combination of $S$ with repetitions. 也就是我们选择$S$中的$k$元素, 不管顺序, 允许重复. 也称为multisets.
  • 形式化地, 考虑映射$m: S\to \mathbb N$. 对于任意$x\in S$, $m(x)\ge 0$是$x$在$M$中的重复次数, 称为multiplicity. $|M|=\sum_{x\in S}m(x)$称为$M$的势. $k$-multiset满足$|M|=k$
  • $S$的$k$-multisets表示为$\left(\left(\begin{array}{cc} S \\\\k \end{array}\right)\right)$. 记$n=|S|$, 表示$\left(\left(\begin{array}{cc} n \\\\k \end{array}\right)\right)=\left|\left(\left(\begin{array}{cc} S \\\\k \end{array}\right)\right)\right|$

  • $\left(\left(\begin{array}{cc} n \\\\k \end{array}\right)\right)=\left(\begin{array}{cc} n+k-1 \\\\n-1\end{array}\right)=\left(\begin{array}{cc} n+k-1 \\\\k\end{array}\right)$, 因为其实就是$m(x_1)+m(x_2)+\cdots+m(x_n)=k$的解的数量

  • 直观解释:
    • 给定一个$[n]$上的$k$-multiset $0\le a_0\le a_1 \le \cdots \le a_{k-1}\le n-1$, 定义$b_i=a_i+i$, 则$\\{b_0,b_1,\cdots,b_{k-1}\\}$是$[n+k-1]$的$k$-subset. 同样的, 给定$b_i$满足$0\le b_0\le b_1\le \cdots b_{k-1}\le n+k-2$, 也能定义对应的$a_i=b_i-i$, $\\{a_0,a_1,\cdots.a_{k-1}\\}$是$[n]$上的$k$-multiset. 因此就有了$\left(\left(\begin{array}{cc} [n] \\\\k \end{array}\right)\right)$到$\left(\begin{array}{cc} [n+k-1] \\\\k \end{array}\right)$的双射.

Multinomial coefficients

  • $\left(\begin{array}{cc} n \\\\k \end{array}\right)$理解为将$n$个元素分成两组, $k$个在第一组, 剩下的在第二组, 即下面说的$\left(\begin{array}{cc} n \\\\k,n-k \end{array}\right)$

  • $(a_1,a_2,\cdots, a_m)$为和为$n$的非负tuple. $\left(\begin{array}{cc} n \\\\a_1,a_2 ,\cdots, a_m\end{array}\right)$为把$n$元集的每个元素配分到$m$个组$G_1,G_2\cdots,G_m$之一的种数, 称为多项式系数. 也可以理解为$n$个标记了的球分配到$m$个标记了的箱子, 第$i$个箱子有$a_i$个球的种数

  • 还可以被理解为multiset的排列数. $n$元集$S$的排列$\pi$可以用一下两种等价方法定义:

    • 双射$\pi: S\to S$
    • tuple $\pi=(x_1,x_2,\cdots,x_n)\in S^n$, $x_i$不同

    $n$元集有$n!$中排列

  • A permutation of a multiset$M$是一个tuple $\pi=(x_1,x_2,\cdots,x_n)$满足$x_i\in M$出现$m(x_i)$次

  • 例子: 某个单词重排的种数

  • 因此$\left(\begin{array}{cc} n \\\\a_1,a_2 ,\cdots, a_m\end{array}\right)$也是multiset$M$的排列数, 其中$|M|=n$.

  • $\left(\begin{array}{cc} n \\\\a_1,a_2 ,\cdots, a_m\end{array}\right)$是$(x_1+x_2+\cdots+x_m)^n$中$x_1^{a_1}x_2^{a_2}\cdots x_m^{a_m}$的系数

    • 证明: $n$因子中任意一个对应一个不同的球, $x_1,x_2,\cdots,x_m$对应$m$个组, $x_1^{a_1}x_2^{a_2}\cdots x_m^{a_m}$的系数等于把$n$个球放入$m$个不同的箱子, 其中第$i$个箱子有$x_i$个球, 也就是上面的式子.

Partitions of a set

  • 有限集$S$的划分Partition是collection$P=\\{S_1,S_2,\cdots,S_k\\}$, 为$S$的子集, 满足

    • 对任意$i$, $S_i\ne\emptyset$
    • 任意$i\ne j$, $S_i\cap S_j=\emptyset$
    • $S_1\cup S_2\cup \cdots S_k=S$

    每个$S_i$称为划分$P$的一个块block. $P$是$k$-partition如果$|P|=k$

  • 定义$\left\\{\begin{array}{cc} n \\\\k\end{array}\right\\}$为$n$元集的$k$划分数量. 注意我们并不关心$S_1,S_2,\cdots,S_k$的顺序. 也称为第二型斯特林数

  • 递归式

    • 证明时分两类:
      • $n$单独一个块
      • $n$非单独一块
  • 定义$B_n=\sum_{k=1}^n\left\\{\begin{array}{cc} n \\\\k\end{array}\right\\}$. 称作Bell数

Partitions of a number

  • 数$n$相同元素分到$k$无序集合的数量, 等价于数把数$n$划分到$k$个无序部分的种类

  • $n$的$k$划分是multiset$\\{x_1,x_2,\cdots,x_k\\}$满足$x_i\ge 1$, 且$x_1+x_2+\cdots+x_k=n$, 其数量定义为$p_k(n)$

  • 等价地, 我们可以定义其为$k$-tuple $(x_1,x_2,\cdots,x_k)$满足

    • $x_1\ge x_2\ge \cdots \ge x_k\ge 1$
    • $x_1+x_2+\cdots+x_k=n$

    其数量为$p_k(n)$

  • $p(n)=\sum_{i=1}^n p_k(n)$是$n$的所有分割数, 称为partition number.

    • 证明不妨设$x_1\ge x_2\ge \cdots \ge x_k\ge 1$
    • 分成$x_k=1$和$x_k>1$两种
  • 定理:

    证明

    • 考虑$(x_1,x_2,\cdots, x_k)$为$n$的$k$-Partition. 则$x_1+x_2+\cdots+x_k=n$, $x_1\ge x_2\ge \cdots x_k\ge 1$
    • 因为每个$n$的$k$-composition都对应至少一个$(x_1,x_2,\cdots, x_k)$的$k!$个排列
      • $n$的$k$-composition有$\left(\begin{array}{cc} n -1 \\\\ k -1\end{array}\right)$个
      • 所以$k!p_k(n)\ge \left(\begin{array}{cc} n -1 \\\\k -1\end{array}\right)$
    • 令$y_i=x_i+k-i$, 则一定有
      • $y_1 > y_2 > \cdots > y_k \ge 1$
      • $y_1+y_2+\cdots+ y_k=n+\frac{k(k-1)}{2}$
      • $(y_1,y_2,\cdots,y_k)$的每个排列都落在不同的$n+\frac{k(k-1)}{2}$的$k$排列中, 因为所有的$y_i$都是不同的
      • 因此$k!p_k(n)\le \left(\begin{array}{cc} n+\frac{k(k-1)}{2} -1 \\\\k -1\end{array}\right)$
    • 综上$\frac{\left(\begin{array}{cc} n -1 \\\\k -1\end{array}\right)}{k!}\le p_k(n)\le \frac{\left(\begin{array}{cc} n+\frac{k(k-1)}{2} -1 \\\\k -1\end{array}\right)}{k!}$

Ferrers diagram

  • 数字$n$的partition可以用Ferrers图表示. $(x_1,x_2,\cdots,x_k)$, $x_1\ge x_2 \ge \cdots \ge x_k\ge 1$是$n$的一个划分. 则对应的Ferrers图有$k$行, 第$i$行包含$x_i$个点(或方块). 如下图

Ferrer1

  • 对偶划分: 把Ferrers图的行和列交换, 如下图:

    Ferrer2

  • 显然:

    • 不同划分的对偶不同
    • 每个划分都有对偶
  • 命题:

    • $n$的每份至多为$k$的划分数为$p_k(n)$

      • 因为对于每个$k$-partition都有对应的每份至多为$k$的对偶partition, 反之亦然.
    • $n$划分成$k$份的种数等于把$n-k$划分成至多$n-k$份的种数, 即

      • Ferrers图去掉左边一列