Note10 Counting

• 笔记

• First Rule of Counting --- order matter

  • 如果一个对象可以通过连续k次选择构造而成，第一次选择有n1种方式，对于每一种第一次选择的方式第二次选择有n2种方式，对于每一种前两次选择的方式第三次选择有n3种方式，依此类推直到第nk次选择，那么可以通过这种方式构造的不同对象总数为乘积n1 ×n2 ×n3 ×···×nk

• Second Rule of Counting --- order don't matter

  • 假设一个对象通过一系列选择构成，且这些选择的顺序无关紧要。设A为有序对象的集合，B为无序对象的集合。如果存在一个从A到B的m对1函数f，则我们可以先计算有序对象的数量（假设顺序重要），然后除以m（每个无序对象对应的有序对象数量），从而得到|B|，即无序对象的数量
  • 请注意，我们假设每个无序对象对应的有序对象数量是相同的；否则该规则无法应用

• sample with replacement and order matter

  • order mater 可以使用 First Rule of Counting，由于 with replacement可放回，因此每次选择都是 n种方式，那么k次选择构造不同对象数 \(n^k\)

• sample with replacement and order don't matter

  • multisets (sets with repetition) --- 从 n 个元素集合中，选择k次，构成的 multisets的可能数
  • 由于每个无序对象对应的有序对象数量是不一定相同的，因此 Second Rule of Counting 无法应用，我们需要将问题转化为 字符串，即 n 个类别视作n个桶，选择视作往桶里扔球，那么可以用 1 作为桶的分割，0 作为球，那么问题转化为0\1字符串
  • 共有 k+n-1 个 位置选择k个位置放0, 即无放回且顺序无关的选择k个元素，即\(\begin{pmatrix}n+k-1 \\ k \end{pmatrix}\)
    • 顺序相不相关主要从结果看，比如本例中，先选位置1再选位置2，和先选位置2再选位置1 属于同一个结果（先放A再放B与先放B再放A）
    • 放不放回更简单，就看能否被反复选择，本例中一个位置只能选一次，就是不放回

• Zeroth Rule of Counting

  • 如果集合A可以与集合B建立一一对应关系（即能找到两者之间的双射——一组可逆的映射，将A的元素映射到B，反之亦然），则|A| = |B|
  • 它反映的其实是将问题变换一个角度来看(转换为等结果的另一个问题或者等价的小规模问题)
    • 一是，将问题转换为可以用 First Rule + Second Rule 能解决的描述，比如上述向字符串的问题转换
    • 二是，将问题转换为小规模等价的形式能够形成递推，比如下面的错排递推定理的得出
    • 寻找一一对应关系。（A中的每一个都有B中的一个对应，B中的每一个都有A中的一个对应）

• Combinatorial Proofs --- 组合证明，采用计数的直观理解而非繁琐的代数计算，也是使用Zeroth Rule of Counting的主要证明

  • Binomial Theorem --- \((a+b)^n=\sum_{k=0}^{n}C_{n}^{k}a^kb^{n-k}\) \(for \ all\ n \in \mathbb{N}\)
  • 恒等式 --- \(C_{n}^{k+1} = C_{n-1}^{k}+C_{n-2}^{k}+...+C_{k}^{k}\)
    • 从基数为n的集合S中，确定基数为k+1的子集个数(左侧)
    • 那么我们将其转化为
    • 选择基数为k+1的子集中最小的元素并构成子集的个数，二者等价，因为每个子集肯定有最小元素(因为基数为k+1)，那么最小元素为1，则从比他大的 n-1个元素中再选k个，依次类推(右侧)

• Permutations and Derangements 排列与错排

  • fixed point --- 我们将待排列的事物从 1-n 进行编号，固定点是指排列后，编号与位次一致的点
    • 比如 {1,2,3} 的排列有6种，其中{1,2,3}有3个固定点，{1,3,2}有1个固定点(1)等等
  • Derangements --- 没有固定点的排列称为错排
  • 错排递推定理 --- 递推式一定是从规模上来推的，从规模小往规模大推 Zeroth Rule of Counting
    • 对于任意正整数 n ≥ 3，集合 {1,...,n} 的错排数 Dn 满足 \(D_n=(n-1)(D_{n-1}+D_{n-2})\)
    • 分析\(D_n\) 它包含的排列 \(\{\pi_1,\pi_2,...,\pi_n\}\)，其中 \(\pi_n \ne n\), 因此\(\pi_n = j\in \{1,2,...,n-1\}\)，共有 (n-1)种情况，还剩\(\{\pi_1,\pi_2,...,\pi_{n-1}\}\) 没有安排，编号还有 {1,2,...,j-1,j+1,...,n}
      • 如果 \(\pi_j=n\) 则相当于 n、j互换，其余也要全部错排(恰好剩余编号和位次是对应的)，即\(D_{n-2}\)
      • 如果 \(\pi_j \ne n\)则把n视作j，此时\(D_{n-1}\)中，不会将 j(n) 排到\(\pi_j\)，而 j(n) 排到其它位置前后是一致的效果，因此等价于 排 {1,2,...,n-1} 即 \(D_{n-1}\)
    • 综上， \(D_n=(n-1)(D_{n-1}+D_{n-2})\)

• 容斥定理及其证明

  • \(P(A_{1}\cup A_{2}... \cup A_{n}) = \sum_{k=1}^{n}(-1)^{k-1}\sum_{S\subseteq \{1,...,n\}:|S|=k}{P(\cap_{i\in S} A_{i})}\)

• 一些常见的交并集计算

  • \(\bar{A\cap B}= \bar{A} \cup \bar{B}\)
  • \(\bar{A\cup B}= \bar{A} \cap \bar{B}\)
  • \(A=总情况数-\bar{A}\)

---