概率论、组合数学知识点汇总

1、概率论知识点

• 全概率公式：如果事件B1,B2,…,Bn是样本空间的一个划分，则：
• 贝叶斯定理：
• 协方差：协方差用来衡量两个变量之间的变化趋势是否一致，公式为
• 相关系数（Pearson）：标准化协方差，取值范围 [−1,1]，公式为
  • 独立和相关：独立必不相关，不相关未必独立
• 大数定律：大数定律描述了当试验次数趋于无穷大时，随机变量的平均值趋于其期望值
• 中心极限定理：中心极限定理描述了当试验次数趋于无穷大时，随机变量和/均值的分布趋近于正态分布

2、常见概率分布

离散分布

• 二项分布：X∼B(n,p)，表示n次独立试验中成功次数的概率分布。

• 几何分布：用于描述在一系列独立的伯努利试验中，首次成功出现所需的试验次数。如果每次试验成功的概率为p，则第k次试验首次出现成功的概率为，几何分布期望为，方差为

• 泊松分布：X∼Poisson(λ)，表示单位时间内事件发生的次数的概率分布。

连续分布

• 均匀分布：X∼U(a,b)，概率密度函数为：

• 正态分布：X∼N(μ,σ^2)，概率密度函数为：

3、组合数学知识点

排列与组合

• 排列：从n个元素中取出k个元素有序排列的方案数
• 组合：从n个元素中取出k个元素无序组合的方案数
• 重要性质：
  • 递推公式：
  • 二项式定理：

 鸽巢原理（抽屉原理）

• 基本形式：将n个物品放入k个容器，若n>k，则至少有一个容器包含超过一个物品

• 一般形式：如果有n个物品放入k个容器中，则至少有一个容器中包含至少⌈n/k⌉个物品

• 作用：鸽巢原理是一个非常直观的概念，尽管简单，但在组合数学、数论和计算机科学中有广泛的应用。它可以用于证明某些存在性问题，即证明某种情况必然存在，而不需要构造具体的例子

球盒问题

问题类型	公式	示例
球相同，盒子不同，允许空盒	C(n+k−1, k−1)	方程 x1+x2+⋯+xk​=n 的非负整数解数
球相同，盒子不同，不允许空盒	C(n-1, k-1)	方程 x1+x2+⋯+xk=n 的正整数解数
球不同，盒子相同，允许空盒	第二类斯特林数S(n,k)	集合划分问题

第二类斯特林数

• 定义：表示将n个不同的元素划分为k个非空且无序集合的方式数，记作S(n,k)

• 递推公式：

  • 解释：第n个元素单独成一组：S(n−1,k−1)；第n个元素加入已有的k组中的任意一组：kS(n−1,k)

• 边界条件：S(n,1)=1；S(n,n)=1；S(n,k)=0 (若k>n)

卡特兰数

• 卡特兰数是组合数学中的一组重要数列，广泛应用于解决各种计数问题
• 显式公式：
• 递推公式：
• 应用：
  • 给定n对括号，卡特兰数表示所有合法的括号组合的数量
  • 给定n个不同的树节点，卡特兰数表示具有n个节点的不同二叉搜索树的数量

4、常见题型

• 几何概率：一根木棒，截成三截，组成三角形的概率是多少？

  • 设木棒的总长度为1，随机截断两次，得到两个截点x和y（假设x<y）

  • 三截木棒的长度分别为x、y-x、1-y，三角形不等式转化为x<0.5,y<x+0.5,y>0.5

  • (x,y)分布区域总面积1/2，可行区域面积1/8，所以组成三角形的概率为1/4

• 随机变量问题：设X和Y是独立同分布的随机变量，求 Z=X+Y的分布

  • 对于两个独立随机变量X和Y，它们的和Z=X+Y的概率密度函数可以通过卷积公式计算：

• 概率与算法结合：设计一个随机算法，从一个未知长度的数据流中均匀随机选择m个元素

  • 蓄水池抽样算法：假设总共有n个元素，对于第k个元素（k > m），它被选中的概率是m/k，之后每个后续元素j（j > k）都有1 - m/j * 1/m = 1 - 1/j的概率不替换掉第k个元素。所以，第k个元素最终留在蓄水池中的概率是m/k * [k/(k+1)] * [(k+1)/(k+2)] * ... * (n-1)/n) = m/n

• 期望计算：抛一个六面的色子，连续抛直到抛到6为止，问期望的抛的次数是多少？

  • 思路1：
  • 思路2：根据几何分布的期望为1/p，得到答案

• 期望计算：假设有一个六面骰子，求掷出所有面至少一次所需的期望次数

  • 分阶段计算在收集到 i−1 种不同优惠券后，再收集到第 i 种新优惠券所需的期望次数。将各阶段的期望次数累加起来，得到总的期望掷骰次数：

• 期望计算：一个木桶里面有m个白球，每分钟从桶中随机取出一个球涂成红色（无论白或红都涂红）再放回，问将桶中球全部涂红的期望时间是多少？

  • 设E(k)表示桶中还有k个白球时，将所有球涂红的期望时间

  • 每次涂红一个球时，有两种可能：涂红一个白球：概率为k/m​，状态从k转移到k-1；涂红一个红球：概率为(m-k)/m​，状态仍为k

  • 因此，期望时间E(k)满足递推关系：，所以答案

• 贝叶斯问题：已知某疾病的发病率为 0.1%，检测准确率为 99%，求检测结果为阳性时实际患病的概率

  • 贝叶斯公式 + 全概率公式

• 概率计算（生日问题）：假设有n个人（n <= 365），每个人的生日在一年中的任意一天，在这n个人中，至少有两个人生日相同的概率是多少？

  

• 概率计算：54张牌，平均分成三堆，大小王在同一堆的概率？

  • 固定大王的位置，计算小王与大王的相对位置关系。大王所在的堆已有1张牌，剩余17个空位，小王需从剩下的53个位置中选择与大王同一堆的17个位置，所以概率为17/53

• 概率计算（脑筋急转弯）：一个桶里面有白球、黑球各100个，现在按下述规则取球：1）每次从桶里面拿出来两个球；
  2）如果取出的是两个同色球，就再放入一个黑球；3）如果取出的是两个异色球，就再放入一个白球。最后桶里面只剩下一个黑球的概率是多少？

  • 白球数量始终保持偶数，剩下一个黑球的概率100%