MIT 6.041 Probabilistic Systems Analysis and Applied Probability - 4.Counting
4.Counting 计数
这课难度较低，主要是讨论计数方法。不管是在高中还是离散数学都有介绍，小学生都会（暴论）（小学数学奥赛内容），所以这课不赘述，简单地罗列下课上讲的概念。
Discrete Uniform Law
第一课我们提到过对于有限样本空间来说，有 Discrete Uniform Law：
若所有结果等可能
则
\[P(A) = \frac{A的元素个数}{所有采样点} = \frac{\|A\|}{\|\Omega \|}\]其中$\Omega$是有限的样本空间
所以，为了更好更快地得出A和$\Omega$的元素个数，我们需要一些计数工具。
Product Rule 乘法原理
假设有$n_i$种方法完成任务$a_i$，如果所有任务之间互相独立，那么就有$\prod_{i=1}^nn_i$种不同的方法完成所有任务$a_i$
Permutation & k-permutation 排列和k-排列
把n个不同元素排好的情况的数量称为排列 Permutation，= $n!$
n个不同元素选k个排好的情况的数量称为k-排列 k-permutation = $\frac{n!}{(n-k)!}$
这不难理解，第一个元素有n个情况，第二个元素有n-1个情况，一直到第k个元素有n-k+1个情况，根据乘法原理乘起来就是上述公式。
拓展
集合论中对排列的定义如下：
一个有限集$A$的排列是一个双射$\pi:A\rightarrow A$
若$|A| = n$，那么所有这样的双射（排列）的集合用$S_n$表示
\[\|S_n\| = n!\]所以事实上我们说的方法的数量是排列的数量
$(S_n,\circ)$是一个对称群，其中$\circ$代表映射复合的运算
所有排列$\pi\in S_n$能被有序序列$\pi(1),\cdots,\pi(n)$唯一确定
这个序列的任意k长度的子序列称为k-排列 k-permutation ，用$P_n^k$表示所有这样的子序列的集合
\[\|P^k_n\| = \frac{n!}{(n-r)!}\]
Combination 组合
在n个元素中选择k个，不排序，则称所有方法的数量为组合 combination $=\binom{n}{k}=\frac{n!}{k!(n-k)!}$
其中$\binom{n}{k}$称为二项式系数 binomial coefficient 部分地方也用$C_{r}^{n}$表示
一些公式
\[\sum_{k=0}^n \binom{n}{k} = 2^n\]计算了所有子集的数量，所以是$2^n$
Pascal’s identity
\[\binom{n}{k}+\binom{n}{k+1} = \binom{n+1}{k+1}\quad for\ r+1\leq n\]Vandermonde’s Identity
对于$m,n,k\in \mathbb{N}$，$k\leq m,n$ ，有
\[\binom{m+n}{k} = \sum_{i=0}^k\binom{m}{k-i}\binom{n}{i}\]后两个公式是自己加的
Binomial Distribution 二项分布
还没提到随机变量，所以此处粗略描述一下
n次重复独立的伯努利实验（即非A即B）中，每次试验中事件A发生的概率为p. 那么事件“n次试验中事件A恰好发生k次”的概率为
\[\binom{n}{k}p^k(1-p)^{n-k}\]且易知所有这样的事件之和（并）的概率为1，i.e.
\[\sum_{k=0}^n\binom{n}{k}p^k(1-p)^{n-k} = 1\]Partitions 划分问题
把n个不同的元素划分成k部分，第i部分的元素个数为$m_i$，则一共有
\[\frac{n!}{m_1!\cdots m_k!}\]种方法
- 可以从组合的角度考虑
先选出$m_1$个元素，再在剩下的$n-m_1$个元素中选出$m_2$个元素…即
\[\binom{n}{m_1}\binom{n-m_1}{m_2}\cdots \binom{n-\sum_{i=1}^{k-1}m_i}{m_k} \\= \frac{n!}{m_1!(n-m_1)!}\frac{(n-m_1)!}{m_2!(n-m_1-m_2)!}\dots\\= \frac{n!}{m_1!\cdots m_k!}\]会发现都可以约掉
- 也可以从除法法则的角度考虑
先排好n个，n!，然后讲重复的情况全部除去，即除以$m_1!\cdots m_k!$
参考资料：MIT6.041公开课程及讲义