概率相关的知识

约 428 个字 预计阅读时间 1 分钟

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

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\) 个元素作为一个新的子集。

Eg

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

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