Chapter 6 Counting(计数)

小学奥数？

The Basics of Counting(计数基础)

• Product Rule(乘法原理): If there are $n_1$ ways to do the first task and $n_2$ ways to do the second task, then there are $n_1 \times n_2$ ways to do both tasks.

• Sum Rule(加法原理): If there are $n_1$ ways to do the first task and $n_2$ ways to do the second task, and the tasks cannot be done at the same time, then there are $n_1 + n_2$ ways to do one of the tasks.

• The Sum Rule for Counting(求和法则): If a set $S$ is the union of $k$ disjoint subsets $S_1, S_2, \cdots, S_k$, then $|S| = |S_1| + |S_2| + \cdots + |S_k|$.

• Subtraction Rule(减法原理): If there are $n_1$ ways to do a task and $n_2$ other ways to do the task, then there are $n_1 + n_2$ minus the number of ways that are duplicated. (实则就是容斥原理)

• Division Rule(除法原则): There are n/d ways to do a task if it can be done using a procedure that can be carried out in n ways, and for every way w, exactly d of the n ways correspond to way w.

The Pigeonhole Principle(鸽巢原理)

即抽屉原理

• The Pigeonhole Principle(鸽巢原理): If $k$ is a positive integer and $k+1$ or more objects are placed into $k$ boxes, then there is at least one box containing two or more of the objects.

• Generalized Pigeonhole Principle(广义鸽巢原理): If $N$ objects are placed into $k$ boxes, then there is at least one box containing at least $\lceil N/k \rceil$ objects.

  • proof: by contraposition, if all boxes contain less than $\lceil N/k \rceil$ objects, then the total number of objects is less than $k \times \lceil N/k \rceil = N$, which is a contradiction.

Eg

在用鸽巢原理证明时，最关键的是要找到一个合适的“盒子”和“鸽子”的对应关系。例如下面的例子：

Permutations and Combinations(排列与组合)

• Permutation(排列): An arrangement of $r$ objects from a set of $n$ objects is called a permutation of $n$ objects taken $r$ at a time. The number of permutations of $n$ objects taken $r$ at a time is denoted by $P(n, r)$

$$P(n, r) = n \times (n-1) \times \cdots \times (n-r+1) = \frac{n!}{(n-r)!}$$

• Combination(组合): An arrangement of $r$ objects from a set of $n$ objects, where the order of the objects does not matter, is called a combination of $n$ objects taken $r$ at a time. The number of combinations of $n$ objects taken $r$ at a time is denoted by $C(n, r)$.

$$C(n, r) = \frac{P(n, r)}{r!} = \frac{n!}{r!(n-r)!}$$

• $C(n, r) = C(n, n-r)$
• $C(n, r) = C(n-1, r) + C(n-1, r-1)$

剩下的希望能请神请到高三的自己

Binomial Coefficients(二项式系数)

• Binomial Theorem(二项式定理): For any positive integer $n$ and any real numbers $x$ and $y$, $(x+y)^n = \sum_{k=0}^{n} C(n, k) \times x^{n-k} \times y^k$
• Binomial Coefficients(二项式系数): $C(n, k)$ is the coefficient of $x^{n-k} \times y^k$ in the expansion of $(x+y)^n$,also denoted by $\binom{n}{k}$.
• Corollary(推论1): $\sum_{k=0}^{n} C(n, k) = 2^n$
• Corollary(推论2): $\sum_{k=0}^{n} (-1)^k \times C(n, k) = 0$
  • proof: $(1-1)^n = \sum_{k=0}^{n} C(n, k) \times 1^{n-k} \times (-1)^k = \sum_{k=0}^{n} (-1)^k \times C(n, k)$

• Corollary(推论3): $\sum_{k=0}^{n} 2^k \times C(n, k) = 3^n$

  • proof: $(1+2)^n = \sum_{k=0}^{n} C(n, k) \times 1^{n-k} \times 2^k = \sum_{k=0}^{n} 2^k \times C(n, k)$

• Pascal's Identity(帕斯卡恒等式): $C(n, k) = C(n-1, k) + C(n-1, k-1)$

  • proof: $(x+y)^n = \sum_{k=0}^{n} C(n, k) \times x^{n-k} y^k = \sum_{k=0}^{n} C(n-1, k) \times x^{n-k} y^k + \sum_{k=0}^{n} C(n-1, k-1) \times x^{n-k} y^k$

其实就是杨辉三角。

• Vandermonde's Identity(范德蒙恒等式): $C(m+n, r) = \sum_{k=0}^{r} C(m, r-k) \times C(n, k)$

Proof

$$\begin{aligned} (x+y)^{m+n} &= (x+y)^m \times (x+y)^n \\ &= \sum_{k=0}^{m} C(m, k) \times x^{m-k} \times y^k \times \sum_{j=0}^{n} C(n, j) \times x^{n-j} \times y^j \\ &= \sum_{r=0}^{m+n} \sum_{k=0}^{r} C(m, k) \times C(n, r-k) \times x^{m+n-r} \times y^r \end{aligned}$$

也可以理解为从分别有m和n个元素的集合A和B中选r个元素.

• Corollary(推论): $C(2n, n) = \sum_{k=0}^{n} C(n, k)^2$
  • proof: $C(2n, n) = \sum_{k=0}^{n} C(n, k) \times C(n, n-k) = \sum_{k=0}^{n} C(n, k)^2$
• Corollary(推论): $C(n+1, k+1) = \sum_{j=0}^{n} C(j, k)$
  • proof: $C(n+1, k+1) = C(n, k) + C(n, k+1) = C(n, k) + C(n-1, k) + C(n-1, k+1) = \cdots = \sum_{j=0}^{n} C(j, k)$

Generalized Permutations and Combinations(广义排列与组合)

• Permutations with Repetition(重复排列)

  The number of permutations of $n$ objects taken $r$ at a time with repetition allowed is $n^r$.

• Combinations with Repetition(重复组合)

  The number of combinations of $n$ objects taken $r$ at a time with repetition allowed is $C(n+r-1, r)$

  高中的“隔板法”：n个物体放进r个盒子，允许为空。

• Permutations with Indistinguishable Objects(相同物体的排列)

  The number of permutations of $n$ objects taken $r$ at a time, where there are $n_1$ indistinguishable objects of type 1, $n_2$ indistinguishable objects of type 2, ..., and $n_k$ indistinguishable objects of type k, is $C(n, n_1, n_2, \cdots, n_k) = \frac{n!}{n_1!n_2!\cdots n_k!}$.

• Distributing Objects into Boxes(将物体分配到盒子中)

  高中“隔板法”plus

  • Distinguishable Objects and Distinguishable Boxes(可区分的物体和盒子)

    $n$ objects into $k$ boxes: $\frac{n!}{n_1!n_2!\cdots n_k!}$

  • Indistinguishable Objects and Distinguishable Boxes(不可区分的物体和可区分的盒子)

    并没有闭公式，要分类讨论； 但是有求和公式：

    n个物体放进k个盒子，每个盒子至少有一个物体的方案数为： $\sum_{j=0}^{k} S(n, j)$

    Stirling numbers of the second kind

    将n元集合写成k个非空disjoint的方法数，详见这里

  • Indistinguishable Objects and Indistinguishable Boxes(不可区分的物体和盒子)

    只能枚举了貌似

Generating Permutations and Combinations(生成排列与组合)

Generating Permutations(生成排列)

• Lexicographic Order(字典序): A permutation of a set of objects is said to be in lexicographic order if for some k, $a_1 = b_1, a_2 = b_2, \cdots, a_{k-1} = b_{k-1}$ and $a_k < b_k$.例如：$123 < 132 < 213 < 231 < 312 < 321$

Generating Combinations(生成组合)

• To generate all combinations of the elements of a finite set which has $n$ elements:

  • Use a binary bit string to represent a combination of the set.
  • The bit string has $n$ bits, and the $i$th bit is 1 if the $i$th element is in the combination, and 0 otherwise.

• To generate all r-combinations of the elements of a finite set which has $n$ elements:

  • Find the last element in the combination that cannot be increased.
  • Replace the next element,etc.

---

最后更新: 2024年5月10日 02:41:31
创建日期: 2024年4月16日 01:44:06