概率相关的知识

记录一些学习过程中发现的有趣的概率问题

Danger

相互独立，交事件可以拆开变成概率相乘；且若AB独立，则A与B的补事件也独立

P(A \cap B) = P(A) \cdot P(B)

互不相交(互斥)，并事件可以拆开变成概率相加。

P(A \cup B) = P(A) + P(B)

n 个球放入m个不同的盒子

球	盒	允许空	方案数
不同	不同	是	$m^n$
不同	不同	否	$m! \cdot S(n, m)$
不同	相同	是	$\sum_{k=0}^{m} S(n, k)$
不同	相同	否	$S(n, m)$
相同	不同	是	$\binom{n+m-1}{m-1}$
相同	不同	否	$\binom{n-1}{m-1}$
相同	相同	是	$dp(n, m)$
相同	相同	否	$dp(n-m, m)$

其中 $S(n,m)$ 为第二类 Stirling 数（Stirling numbers of the second kind）是组合数学中的一个重要概念，用来描述如何将 $n$ 个不同的元素划分为 $m$ 个非空的无序子集。更具体地说， $S(n, m)$ 表示的是有多少种方法可以把一个包含 $n$ 个元素的集合划分成 $m$ 个非空子集。

计算公式

第二类斯特林数 $S(n, m)$ 的递推公式如下：

S(n, m) = m \cdot S(n-1, m) + S(n-1, m-1)

其中，边界条件是：

$S(0, 0) = 1$
对于 $n > 0$ ， $S(n, 0) = 0$ 且 $S(n, n) = 1$

$m \cdot S(n-1, m)$ ：将第 $n$ 个元素放入现有的 $m$ 个子集中的某一个。共有 $m \cdot S(n-1, m)$ 种。
$S(n-1, m-1)$ ：将第 $n$ 个元素作为一个新的子集。

例如， $S(3, 2) = 3$ ，表示有 3 种方法可以将 3 个元素分成 2 个非空子集，分别是：

{1, 2}, {3}
{1, 3}, {2}
{2, 3}, {1}

Stirling 公式

n! \approx \sqrt{2\pi n} \left( \frac{n}{e} \right)^n