基本原理

加法原理：分类统计，方案数相加

乘法原理：分步统计，方案数相乘

二项式系数

• 符号：(nk)(kn​) 或 CnkCnk​
• 含义：从 nn 个元素中选取 kk 个的方案数

递推计算：

(nk)=(n−1k−1)+(n−1k)(kn​)=(k−1n−1​)+(kn−1​)

递推起点：

(n0)=(nn)=1(0n​)=(nn​)=1

递推式也称为杨辉三角，帕斯卡三角

公式计算：

(nk)=n!k!(n−k)!(kn​)=k!(n−k)!n!​

性质一：

• (nk)=(nn−k)(kn​)=(n−kn​)
• 原理：nn 个选 kk 个，意味着 nn 个不选 n−kn−k 个，方案数必定相同。

性质二：

• ∑i=0n(ni)=2n∑i=0n​(in​)=2n
• 原理：对每个元素，均有选或不选两种可能，根据乘法原理，有 2n2n 种选法。

二项式系数：

(a+b)n=(n0)anb0+(n1)an−1b1+…+(nn−1)a1bn−1+(nn)a0bn(a+b)n=(0n​)anb0+(1n​)an−1b1+…+(n−1n​)a1bn−1+(nn​)a0bn

基本模型——盒子与小球

问题模型：将 n  n 个小球放入 m  m 个盒子中，有多少种放法？

该问题需要分情况讨论，主要分盒子是否相同、小球是否相同、是否允许盒子为空等三种状态，共计八种情况模型。

---

1、小球相同，盒子不同，不允许空箱

可以采用隔板法（插空法）考虑该问题。因为小球相同，故考虑将“小球入盒”想成“隔板隔开小球”，隔板个数为 m−1 m−1，例如 6  6 个小球和 3  3 个盒子：

放法示例：OOO∣OO∣O小球示例：OOOOOO隔板示例：　∣　∣　放法示例：OOO∣OO∣O小球示例：OOOOOO隔板示例：　∣　∣　​

故 n  n 个球形成了 n−1  n−1 个间隙,用 m−1  m−1 个隔板分成 m  m 组，相当于从 n−1  n−1 个间隙中选 m−1  m−1 个位置放隔板。

故方案数为  Cn−1m−1 Cn−1m−1​

因为不允许空盒，故要求 n≥m  n≥m 

---

2、小球相同，盒子不同，允许空箱

因为允许空箱，故可以考虑再增加 m  m 个小球，将 m  m 个小球放入 m  m 个盒子中，每个盒子放一个，剩下的问题就转化为不允许空箱的问题了。

故方案数为  Cn−1+mm−1 Cn−1+mm−1​

---

3、小球不同，盒子不同，允许空箱

因为小球不同且允许空箱，故每个球的方法是独立的，每个球都有 m  m 种放法，根据乘法原理，方案数为  mn mn。

---

4、小球不同，盒子相同，不允许空箱

该问题属于经典第二类斯特林数问题（第4、5、6种情况均属于该问题的变形），一般用递推法解决。定义 f[i][j]  f[i][j] 表示 i  i 个球 j  j 个盒子的方案，则：

• 边界条件：
• f[0][0]=1f[0][0]=1，即没有盒子也没有小球时，有一种放法（什么也不放）
• f[k][0]=0, ∀k∈[1, n]f[k][0]=0, ∀k∈[1, n]，即有小球没盒子时，无法找到符合要求的放法
• 一般情况分两种情况讨论：
• 如果将第 i  i 个小球放入第 j  j 个新盒子，则该操作有一种放法，在放之前已经完成了第 i−1  i−1 个小球放入 j−1  j−1 个盒子的操作，故放法数为  f[i−1][j−1] f[i−1][j−1]；
• 如果将第 i  i 个小球放入现有的盒子中，现有 j  j 个盒子，共有 j  j 种放法；而之前已经完成了第 i−1  i−1 个小球放入 j  j 个盒子的操作，故放法数为 kf[i−1][j] kf[i−1][j]；
• 上述两种情况根据加法原理相加即可，得到递推式：
  f[i][j]=f[i−1][j−1]+kf[i−1][j]f[i][j]=f[i−1][j−1]+kf[i−1][j]

故总方案数表示为：f[n][m]f[n][m]

5、小球不同，盒子不同，不允许空箱

该情况和上述情况基本相同，但因为盒子不同，故还需要计算盒子的排列数。

故方案数为：Ammf[n][m]=m!f[n][m]Amm​f[n][m]=m!f[n][m]

6、小球不同，盒子相同，允许空箱

因为允许空箱，故可以在第 4  4 种情况下，分别计算使用 1  1 个盒子、使用 2  2 个盒子、使用 3  3 个盒子、……、使用 m  m 个盒子的方案数，加起来即可。

故总方案数为：

∑i=1mf[n][i]=f[n][1]+f[n][2]+f[n][3]+...+f[n][m]=​i=1∑m​f[n][i]f[n][1]+f[n][2]+f[n][3]+...+f[n][m]​

---

7、小球相同，盒子相同，允许空箱

该问题属于经典递推问题。设 dp[i][j]  dp[i][j] 为 i  i 个球、j j 个盒子的方案数，则：

dp[i][j]={1　i=0或j=1，即无小球或仅一个盒子时显然只有一种放法dp[i][j]=dp[i][i]i<j，即小球数小于盒子数，多余的盒子对放法无影响dp[i][j]=dp[i−j][j]+dp[i][j−1]i≥j，即小球数大于等于盒子数时，在所有盒子各放一个球，或拿掉一个盒子dp[i][j]=⎩⎨⎧​1dp[i][j]=dp[i][i]dp[i][j]=dp[i−j][j]+dp[i][j−1]​　​i=0或j=1，即无小球或仅一个盒子时显然只有一种放法i<j，即小球数小于盒子数，多余的盒子对放法无影响i≥j，即小球数大于等于盒子数时，在所有盒子各放一个球，或拿掉一个盒子​

最终方案数是  dp[n][m] dp[n][m]。

实际编程求解时用递归更简单。

8、小球相同，盒子相同，不允许空箱

该问题和上述问题基本一致。既然不允许空箱，那么每个箱子至少需要一个球，故先将每个箱子放上一个球后，剩下的问题就变成允许空箱的情况了。

最终方案数是  dp[n−m][m] dp[n−m][m]。

多项式系数（Multinomial Coefficient）

(nk1,k2,…,km)=n!k1!k2!⋯km!(k1​,k2​,…,km​n​)=k1​!k2​!⋯km​!n!​

等于将 nn 个元素划分为大小分别为 k1,k2,…,kmk1​,k2​,…,km​ 的子集的方式数，其中 k1+k2+…+km=nk1​+k2​+…+km​=n。多项式系数可以看作二项式系数的推广；当 m=2m=2 时，上述公式对应二项式系数公式。

容斥原理

∣A∪B∣=∣A∣+∣B∣−∣A∩B∣∣A∪B∣=∣A∣+∣B∣−∣A∩B∣∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣A∩C∣−∣B∩C∣+∣A∩B∩C∣∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣A∩C∣−∣B∩C∣+∣A∩B∩C∣

子集大小为奇数的情况做加法，偶数的情况做减法。

错排

递推式：

• D(1)=0D(1)=0
• D(2)=1D(2)=1
• D(n)=(n−1)D(n−1)+(n−1)D(n−2)D(n)=(n−1)D(n−1)+(n−1)D(n−2)