概率论的两个问题-球盒模型、匹配问题

怎样利用“数数”的基本公式,来正确(不漏、不重)数出具体问题的数,并不是件容易的事儿。

基础概念

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个排列组合问题来体会。

  1. 8个相同的球放进3个相同的盒子里,每盒至少一个,有几种方法

取球最少的盒子取1,取球第二少的盒子可以取[1,3] 3种 取球最少的盒子取2,取球第二少的盒子可以取[2,3] 2种 取球最少的盒子取3,此情况不存在,一共5种 按取球多寡来分类讨论可以做到不遗漏,不重复

  1. 8个相同的球放进3个不同的盒子里,每盒至少一个,有几种方法

插板法,$C_7^2=21$

  1. 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.$

  1. 8个不同的球放进3个不同的盒子里,每盒至少一个,有几种方法

4问中的966种情况,每种情况的三个元素都是互异的,比如 116(因为球是不同的),这三个元素进行全排列$P_3^3=6$, 乘以 966=5796 即为所求

  1. 8个相同的球放进3个相同的盒子里,有几种方法

最少盒子取0,次盒子取[0,4]
最少盒子取1,次盒子取[1,3]
最少盒子取2,次盒子取[2,3]
一共 5+3+2=10 种

  1. 8个相同的球放进3个不同的盒子里,有几种方法
    预先在三个盒子种各放入一小球,则问题转化为11同球放3不同盒子,每盒至少1个,几种方法? 用插板法,$C_10^2=45$

  2. 8个不同的球放进3个不同的盒子里,有几种方法

每个球都有3种选择,8个球就有$3^8=6561$.

  1. 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!}$$

我只是试试,自己给自己转点钱!