怎样利用“数数”的基本公式，来正确（不漏、不重）数出具体问题的数，并不是件容易的事儿。
基础概念
1. 可重复组合数
从 $n$ 种不同的元素中取 $m$ 个元素（方法是从 $n$ 个元素中每次取出一个后，放回，再取另外一个，直到取出 $m$ 个元素）有 $C_{n+m-1}^m$ 个不同的结果。
证明（顺便提到球盒模型用到的“隔板法”）：
首先明确，所谓有重复组合就是不考虑取出的元素的顺序，通俗来说，你第一次取出 $1$ 号元素第二次取出 $3$ 号元素和你第一次取出 $3$ 号元素第二次取出 $1$ 号元素是一样的情况。
可以把该过程看作是一个“放球模型”； $n$ 个不同的元素看作是 $n$ 个格子，去掉头尾之后中间一共有 $n-1$ 块相同的隔板；用 $m$ 个相同的小球代表取 $m$ 次；则原问题可以简化为将 $m$ 个不加区别的小球放进 $n$ 个格子里面，问有多少种放法；
注意到格子的头尾两块隔板无论什么情况下位置都是不变的，故去掉不用考虑；相当于 $m$ 个相同的小球和 $n-1$ 块相同的隔板先进行全排列：一共有 $(m+n-1)!$ 种排法，再由于m个小球和（n-1）块隔板是分别不加以区分的，所以除以重复的情况：$m!*(n-1)!$;
于是答案就是：$\frac{(m+n-1)!}{m!*(n-1)!}=C_{n+m-1}^{m}$。
2. 第二类Stiring数：
$n$ 个人分成 $k$ 组的分组方案的数量。 $$S(n,k) = \frac{1}{k!}\sum_{j=1}^{k}(-1)^{k-j}C_k^j j^n$$ $S(n,n-1)=C_n^2=\frac{n(n-1)}{2}$
3. Jordan公式：
概率加法公式的推广 $$ P(\bigcup_{i=1}^{n}A_i) = S_1-S_2+S_3-\cdots+(-1)^{n-1}S_n \\ S_k = \underset{1< i_1 < i_2 < \cdots< i_k < n}{\sum}P(A_{i_1}A_{i_2}\cdots A_{i_k}) $$
球盒模型
简例 - 1
先从简单的例子讲起，$m$ 个球随机放入 $n$ 个盒子中，$n$ 个盒子都有球的概率。 其中，“随机”的含义，可分两种情况讨论：
1）球可分辨
记 $B=n\text{个盒子中至少一个为空}$ ,$A_i = $第 $i$ 个盒子为空 于是$$B=\bigcup_{i=1}^{n}A_i$$ 因而$$P(B) = p(\bigcup_{i=1}^{n}A_i). \\ P(A_i)=\frac{(n-1)^m}{n^m}, P(A_1A_2)=\frac{(n-2)^m}{n^m},\cdots \\ P(A_1\cdots A_{n-1})=\frac{1}{n^m},P(A_1\cdots A_{n}) = 0.$$ 按 Jordan 公式 $$P(B)=\sum_{i=1}^{n}(-1)^{i-1}C_n^i \frac{(n-i)^m}{n^m}$$ 所求事件概率为 $1-P(B)$
2）球不可分辨
记 $A=n\text{个盒子都有球}$, 可根据上述可重复组合数公式得$P(A)=C_{n+m-1}^{m}$，即数出 $n$ 个盒子都有球的情况数。
标准模型
标准的球盒模型，分别讨论球是否有区别、盒子是否有标志以及是否存在空盒，共计 $2^3=8$ 种状态。
| Seq | Ball | Box | Amt in Box |
|---|---|---|---|
| 1 | Non-Diff | Mark | No-limit |
| 2 | Non-diff | Mark | No empty box |
| 3 | Non-diff | Unmark | No-limit |
| 4 | Non-diff | Unmark | No empty box |
| 5 | Diff | Mark | No-limit |
| 6 | Diff | Mark | No empty box |
| 7 | Diff | Unmark | No-limit |
| 8 | Diff | Unmark | No empty box |
简例 - 2
简化上述理论，从8个排列组合问题来体会。
- 8个相同的球放进3个相同的盒子里，每盒至少一个，有几种方法
取球最少的盒子取1，取球第二少的盒子可以取[1,3] 3种 取球最少的盒子取2，取球第二少的盒子可以取[2,3] 2种 取球最少的盒子取3，此情况不存在，一共5种 按取球多寡来分类讨论可以做到不遗漏，不重复
- 8个相同的球放进3个不同的盒子里，每盒至少一个，有几种方法
插板法，$C_7^2=21$
- 8个不同的球放进3个相同的盒子里，每盒至少一个，有几种方法
取球最少盒子取 1 时，有116, 125, 134三种情况，分别有$C_8^6=28,C_8^1*C_7^2=168, C_8^1*C_7^3=280$. 取球最少盒子取 2 时，有224，233二种情况，分别有$\frac{C_8^2*C_6^2}{2}=210,\frac{C_8^3*C_5^3}{2}=280$.一共 $28+168+280+210+280=966.$
- 8个不同的球放进3个不同的盒子里，每盒至少一个，有几种方法
4问中的966种情况，每种情况的三个元素都是互异的，比如 116（因为球是不同的），这三个元素进行全排列$P_3^3=6$, 乘以 966=5796 即为所求
- 8个相同的球放进3个相同的盒子里，有几种方法
最少盒子取0，次盒子取[0,4]
最少盒子取1，次盒子取[1,3]
最少盒子取2，次盒子取[2,3]
一共 5+3+2=10 种
-
8个相同的球放进3个不同的盒子里，有几种方法
预先在三个盒子种各放入一小球，则问题转化为11同球放3不同盒子，每盒至少1个，几种方法？ 用插板法，$C_10^2=45$ -
8个不同的球放进3个不同的盒子里，有几种方法
每个球都有3种选择，8个球就有$3^8=6561$.
- 8个不同的球放进3个相同的盒子里，有几种方法
(7问) 中的一般情况(3个元素都相异)，比如116，一共有6种排列(球是不同的)，此问中，盒子是相同的，因此这6种排列都只算一种情况。 但如果2个元素相同的时候，有且只有008，只有3种排列，我们多添加3种进去，令其也重复6次，则6561+3就是 所有的情况都重复了6次，$\frac{6561+3}{6}=1094$ 即为所求。
匹配问题
问题：两套各标上号码 $1$ 至 $n$ 的卡片被随机地匹配， 1）问至少有一对匹配成功的概率为多少？ 2）问至少有$k(k\leq n)$ 对匹配成功的概率为多少?
记$B=\text{至少有一对匹配成功}$， $A_i=\text{第i对卡片匹配成功},i=1,2,\cdots ,n$
事件 $B$ 跟较简单的事件$A_1,A_2,\cdots ,A_n$间有如下关系， $$B=\bigcup_{i=1}^{n}A_i$$
按Jordan公式，为求 $P(B)$ ，需求 $S_1,S_2,\cdots ,S_n$。为此，先来求 $P(A_1)$
$$P(A_1)=\frac{(n-1)!}{n!} = \frac{1}{n}$$
$P(A_2)=P(A_3)=\cdots =P(A_n)=P(A_1)$，所以 $S_1=n\cdot \frac{1}{n}=1$
至于 $S_1,S_2,\cdots ,S_n$ 类似求得 $$P(A_1A_2)=\frac{(n-2)!}{n!}=\frac{1}{n(n-1)}, \quad S_2=C_n^2 \frac{1}{n(n-1)}=\frac{1}{2!} ;$$ $$P(A_1A_2A_3)=\frac{1}{n(n-1)(n-2)}, \quad S_3=C_n^3 \frac{1}{n(n-1)(n-2)}=\frac{1}{3!} ;$$ $$\cdots \cdots \cdots$$ $$P(\bigcap_{i=1}^{n}A_i)=\frac{1}{n!}, \quad S_n = \frac{1}{n!} $$
$$P(B) = 1-\frac{1}{2!}+\frac{1}{3!}-\cdots +(-1)^{n-1}\frac{1}{n!}$$
其中，
$$1-e^{-1} = 1-\frac{1}{2!}+\frac{1}{3!}-\cdots +(-1)^{n-1}\frac{1}{n!}+\cdots = \sum_{n=1}^{\inf}\frac{(-1)^{n-1} }{n!}$$
