排列组合二十个题型

一、两大基本原理

所有复杂的组合计数问题，都可以回归到两个最基本的原理：加法原理和乘法原理。

1. 加法原理 (Rule of Sum)

如果完成一件事情有 nn 类方法，在第一类方法中有 m1m_1 种不同的方式，在第二类方法中有 m2m_2 种不同的方式，……，在第 nn 类方法中有 mnm_n 种不同的方式，那么完成这件事情共有 N=m1+m2+⋯+mnN = m_1 + m_2 + \dots + m_n 种不同的方式。

核心：分类。各类方法之间相互独立，任何一种方法都可以独立完成事件。

示例：从北京到上海，可以乘飞机（3个航班）、乘高铁（5个车次）、乘普速火车（2个车次）。那么从北京到上海共有 3+5+2=103 + 5 + 2 = 10 种不同的旅行方式。

2. 乘法原理 (Rule of Product)

如果完成一件事情需要分成 nn 个步骤，完成第一个步骤有 m1m_1 种不同的方式，完成第二个步骤有 m2m_2 种不同的方式，……，完成第 nn 个步骤有 mnm_n 种不同的方式，那么完成这件事情共有 N=m1×m2×⋯×mnN = m_1 \times m_2 \times \dots \times m_n 种不同的方式。

核心：分步。各个步骤缺一不可，必须依次完成所有步骤才能完成整个事件。

示例：从上衣（3件不同）、裤子（4条不同）、鞋子（2双不同）中各选一件搭配。总搭配方案数为 3×4×2=243 \times 4 \times 2 = 24 种。

二、排列与组合的核心定义

1. 排列 (Permutation)

从 nn 个不同元素中，取出 mm (m≤nm \le n) 个元素，并按照一定的顺序排成一列，这个过程称为排列。排列数用 AnmA_n^m (或 PnmP_n^m) 表示。

计算公式：

$$A_n^m = n(n-1)(n-2)\cdots(n-m+1) = \frac{n!}{(n-m)!} $$

当 m=nm=n 时，称为全排列，记作 Ann=n!A_n^n = n!。

核心：有序。元素的顺序会影响结果。例如，(A, B) 和 (B, A) 是两种不同的排列。

2. 组合 (Combination)

从 nn 个不同元素中，取出 mm (m≤nm \le n) 个元素，不考虑顺序地并成一组，这个过程称为组合。组合数用 CnmC_n^m (或 (nm)\binom{n}{m}) 表示。

计算公式：

Cnm=Anmm!=n!m!(n−m)!C_n^m = \frac{A_n^m}{m!} = \frac{n!}{m!(n-m)!}

核心：无序。元素的顺序不影响结果。例如，{A, B} 和 {B, A} 是同一个组合。

组合数的两个重要性质：

  1. Cnm=Cnn−mC_n^m = C_n^{n-m} (从n个里选m个，等于从n个里不选n-m个)
  2. Cnm=Cn−1m+Cn−1m−1C_n^m = C_{n-1}^m + C_{n-1}^{m-1} (杨辉三角/帕斯卡恒等式)

三、排列组合问题的20种核心题型

我们将问题分为几大类：基础应用、特殊元素/位置约束、重复元素问题、分组与分配、特殊结构、以及高级计数方法。

A. 基础与约束型

题型1：无约束排列

问题：从5本不同的书中选出3本送给3个不同的人，每人一本，有多少种送法？ 方法：相当于从5个元素中选3个进行排列。 计算：A53=5×4×3=60A_5^3 = 5 \times 4 \times 3 = 60。

题型2：无约束组合

问题：从一个有5名男队员和3名女队员的队伍中，选出4人组成一个小组，有多少种选法？ 方法：相当于从总共8人中选4人，不考虑顺序。 计算：$C_8^4 = \frac{8 \times 7 \times 6 \times 5}{4 \times 3 \times 2 \times 1} = 70$。

题型3：相邻问题——捆绑法 (Bundling Method)

问题：有A, B, C, D, E五个人排成一队，要求A和B必须站在一起，有多少种排法？ 方法：将必须相邻的元素（A, B）看作一个整体"X"。现在问题变成对X, C, D, E四个元素进行全排列。之后，再考虑"X"内部元素的排列。 计算：

  1. 捆绑：(A,B) 视为一个大元素X。
  2. 排列外部：对 X, C, D, E 进行全排列，有 A44=4!=24A_4^4 = 4! = 24 种。
  3. 排列内部：对 (A,B) 内部进行全排列，有 A22=2!=2A_2^2 = 2! = 2 种。
  4. 总数（乘法原理）：A44×A22=24×2=48A_4^4 \times A_2^2 = 24 \times 2 = 48 种。

题型4：不相邻问题——插空法 (Insertion Method)

问题：有A, B, C, D, E五个人排成一队，要求A和B不能相邻，有多少种排法？ 方法：先排列其他没有限制的元素，然后在它们形成的空隙中插入有不相邻要求的元素。 计算：

  1. 先排列 C, D, E，有 A33=3!=6A_3^3 = 3! = 6 种。
  2. C, D, E 排好后，形成4个空隙（包括两端）：_ C _ D _ E _。
  3. 将 A, B 插入这4个空隙中，相当于从4个位置选2个给A, B排列，有 A42=12A_4^2 = 12 种。
  4. 总数（乘法原理）：A33×A42=6×12=72A_3^3 \times A_4^2 = 6 \times 12 = 72 种。 另一种思路（正难则反）：总排列数减去A,B相邻的排列数。A55−48=120−48=72A_5^5 - 48 = 120 - 48 = 72。

题型5：特定位置——优先法 (Priority Method)

问题：用数字0, 1, 2, 3, 4组成没有重复数字的五位数，其中偶数有多少个？ 方法：优先考虑有限制条件的元素或位置。 计算：

  1. 个位有限制（必须是偶数）。但0比较特殊，不能作首位。因此需要分类讨论。
  2. Case 1：个位是0。
    • 个位已定（1种选择）。
    • 万位从剩下4个非0数字中选，有4种选择。
    • 其余3位从剩下3个数字中全排列，有 A33=6A_3^3=6 种。
    • 此情况共 1×4×A33=241 \times 4 \times A_3^3 = 24 个。
  3. Case 2：个位是2或4。
    • 个位有2种选择（2或4）。
    • 万位不能是0且不能是已选的偶数，有3种选择。
    • 其余3位从剩下3个数字中全排列，有 A33=6A_3^3=6 种。
    • 此情况共 2×3×A33=362 \times 3 \times A_3^3 = 36 个。
  4. 总数（加法原理）：24+36=6024 + 36 = 60 个。

题型6：顺序固定——除法模型 (Division Model)

问题：有A, B, C, D, E五个人排成一队，要求A必须在B的左边（不一定相邻），有多少种排法？ 方法：对于任意一种排列，A和B的位置关系只有两种可能：A在B左边，或者B在A左边。这两种情况的数目是完全对称的。因此，满足条件的排法占总数的一半。 计算：总排列数为 A55=120A_5^5 = 120。A在B左边的排法为 120/2=60120 / 2 = 60 种。 另一种思路：先从5个位置中选2个位置给A和B，有 C52C_5^2 种。因为A必须在B左边，所以这两个位置上它俩的放法是固定的（1种）。然后，剩下3个元素在剩下3个位置上全排列，有 A33A_3^3 种。总数 C52×1×A33=10×6=60C_5^2 \times 1 \times A_3^3 = 10 \times 6 = 60 种。

B. 重复元素问题

题型7：有重复元素的全排列

问题：用2个A，3个B，1个C组成一个六位数的字符串，有多少种不同的字符串？ 方法：先将所有元素视为不同（如 A1,A2,B1,B2,B3,CA_1, A_2, B_1, B_2, B_3, C）进行全排列，然后除以重复元素内部的全排列，以消除因相同元素交换位置而产生的重复计数。 计算：

$$\frac{6!}{2! \cdot 3! \cdot 1!} = \frac{720}{2 \cdot 6 \cdot 1} = 60 $$

题型8：可重复选择的组合——隔板法 (Stars and Bars)

问题：有10个相同的糖果，分给3个小朋友，每人至少分到1个，有多少种分法？ 方法：将10个糖果排成一排 o o o o o o o o o o。它们之间形成了9个空隙。要分成3份，只需要在这9个空隙中插入2个“隔板”。 计算：从9个空隙中选择2个位置放隔板，有 C92=9×82=36C_9^2 = \frac{9 \times 8}{2} = 36 种分法。

题型9：隔板法变种（允许为空）

问题：有10个相同的糖果，分给3个小朋友，允许有人分不到，有多少种分法？ 方法：先借给每个小朋友1个糖果，这样总共有 10+3=1310+3=13 个糖果。现在问题转化为，将13个糖果分给3个小朋友，每人至少1个。 计算：13个糖果形成12个空隙，插入2个隔板。有 C122=12×112=66C_{12}^2 = \frac{12 \times 11}{2} = 66 种分法。 通用公式：将 nn 个相同物品分给 kk 个不同的人（允许为空），方案数为 Cn+k−1k−1C_{n+k-1}^{k-1}。

C. 分组与分配问题

题型10：有序分配问题 (Distinguishable items to distinguishable boxes)

问题：将5本不同的书分给3个人，每人至少一本，有多少种分法？ 方法：这是个复杂问题，通常使用容斥原理或第二类斯特林数。

  1. 第二类斯特林数：将5个不同元素分成3个非空集合的方案数，记作 S(5,3)S(5,3)。然后再将这3个集合分配给3个人。
    • S(5,3)=25S(5,3) = 25。（计算较复杂，见题型12）
    • 分配给3个人，有 3!3! 种方式。
    • 总数：S(5,3)×3!=25×6=150S(5,3) \times 3! = 25 \times 6 = 150 种。
  2. 容斥原理（见题型18）：总方案数（每本书可以给3个人中的任意一个，353^5）减去“至少有一个人没分到”的，加上“至少有两个人没分到”的。
    • C31×(3−1)5C_3^1 \times (3-1)^5：指定一个人没分到。
    • C32×(3−2)5C_3^2 \times (3-2)^5：指定两个人没分到。
    • 总数：$3^5 - C_3^1 \cdot 2^5 + C_3^2 \cdot 1^5 = 243 - 3 \cdot 32 + 3 \cdot 1 = 243 - 96 + 3 = 150$。

题型11：无序分组问题 (Distinguishable items to indistinguishable boxes)

问题：将5本不同的书分成3堆，每堆至少一本，有多少种分法？ 方法：这就是第二类斯特林数 (Stirling Numbers of the Second Kind) S(n,k)S(n, k) 的定义。 计算：S(5,3)S(5,3) 的计算可以通过分组情况的枚举：

  • 分组为 (3, 1, 1): 先选3本 C53C_5^3。C53=10=10C_5^3 = 10 = 10 种。
  • 分组为 (2, 2, 1): 先选1本 C51C_5^1，再从剩下4本中选2本 C42C_4^2，剩下2本自动成堆。同样，两个(2,2)堆无区别，除以 2!2!。(C51×C42)/2!=(5×6)/2=15(C_5^1 \times C_4^2) / 2! = (5 \times 6) / 2 = 15 种。
  • 总数：10+15=2510 + 15 = 25 种。

题型12：整数划分问题 (Indistinguishable items to indistinguishable boxes)

问题：将5个相同的苹果分成3堆，允许有空堆，有多少种分法？ 方法：这是整数划分问题。即把整数5表示成3个非负整数之和。 计算：通过枚举：

  • 5 = 5 + 0 + 0
  • 5 = 4 + 1 + 0
  • 5 = 3 + 2 + 0
  • 5 = 3 + 1 + 1
  • 5 = 2 + 2 + 1 总共有5种分法。整数划分没有简单的通用公式，通常用动态规划求解。

D. 特殊结构问题

题型13：环形排列 (Circular Permutation)

问题：5个人围着一张圆桌坐，有多少种不同的坐法？ 方法：与直线排列相比，环形排列旋转后相同视为一种。可以先固定一个人不动，剩下的人进行全排列。 计算：固定一个人，剩下4人全排列。(5−1)!=4!=24(5-1)! = 4! = 24 种。 通用公式：nn 个不同元素的环形排列数是 (n−1)!(n-1)!。

题型14：项链问题（可翻转的环形排列）

问题：用5颗不同颜色的珠子串成一个项链，有多少种不同的串法？ 方法：项链除了可以旋转，还可以翻转。大部分情况下，翻转会产生新的不同排列（相对于仅旋转），但对于对称的排列则不会。一个简单的处理方法是，如果排列数大于2，翻转会使得不同的排列数减半。 计算：先按环形排列计算 (5−1)!=24(5-1)! = 24 种。由于5是奇数，不存在对称的排列，所以所有排列都可以两两配对（一个和它翻转后的那个）。所以总数是 24/2=1224 / 2 = 12 种。 注意：这是一种简化模型。严格的解法需要使用伯恩赛德引理或波利亚枚举定理。

题型15：错位排列 (Derangement)

问题：有5封写好的信和5个写好地址的信封，要求每封信都不能装入正确的信封中，有多少种装法？ 方法：这是一个经典的错位排列问题，记作 DnD_n 或 !n!n。 递推公式：Dn=(n−1)(Dn−1+Dn−2)D_n = (n-1)(D_{n-1} + D_{n-2})。基础情况 D1=0,D2=1D_1=0, D_2=1。

  • D3=2(D2+D1)=2(1+0)=2D_3 = 2(D_2 + D_1) = 2(1+0) = 2。
  • D4=3(D3+D2)=3(2+1)=9D_4 = 3(D_3 + D_2) = 3(2+1) = 9。
  • D5=4(D4+D3)=4(9+2)=44D_5 = 4(D_4 + D_3) = 4(9+2) = 44。 通项公式：Dn=n!∑k=0n(−1)kk!D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}。

E. 高级计数原理与方法

题型16：二项式定理应用

问题：求 (2x−y)10(2x - y)^{10} 的展开式中 x7y3x^7y^3 项的系数。 方法：根据二项式定理 (a+b)n=∑k=0nCnkan−kbk(a+b)^n = \sum_{k=0}^{n} C_n^k a^{n-k} b^k。 计算：

  1. 令 a=2x,b=−y,n=10a=2x, b=-y, n=10。
  2. 我们需要 an−kbka^{n-k}b^k 中 xx 的指数是7，y的指数是3。所以 (2x)10−k(−y)k(2x)^{10-k}(-y)^k 应该匹配 x7y3x^7y^3。
  3. 显然 k=3k=3。该项为 $C_{10}^3 (2x)^{10-3}(-y)^3 = C_{10}^3 (2x)^7 (-y)^3$。
  4. 系数为 $C_{10}^3 \cdot 2^7 \cdot (-1)^3 = 120 \cdot 128 \cdot (-1) = -15360$。

题型17：卢卡斯定理 (Lucas's Theorem)

问题：计算 C10030(mod7)C_{100}^{30} \pmod{7}。 方法：卢卡斯定理用于计算大组合数模小质数 pp。它将 nn 和 mm 写成 pp 进制，然后对每一位分别计算组合数再相乘。 Cnm≡∏i=0kCnimi(modp)C_n^m \equiv \prod_{i=0}^k C_{n_i}^{m_i} \pmod{p}，其中 n=nkpk+⋯+n1p+n0n = n_k p^k + \dots + n_1 p + n_0，m=mkpk+⋯+m1p+m0m = m_k p^k + \dots + m_1 p + m_0。 计算：

  1. p=7p=7。
  2. 100100 的7进制：100=2⋅49+0⋅7+2=(202)7100 = 2 \cdot 49 + 0 \cdot 7 + 2 = (202)_7。
  3. 3030 的7进制：30=0⋅49+4⋅7+2=(042)730 = 0 \cdot 49 + 4 \cdot 7 + 2 = (042)_7。
  4. $C_{100}^{30} \equiv C_2^0 \cdot C_0^4 \cdot C_2^2 \pmod{7}$。
  5. C20=1C_2^0 = 1, C04=0C_0^4 = 0 (因为 0<40<4), C22=1C_2^2 = 1。
  6. C10030≡1⋅0⋅1=0(mod7)C_{100}^{30} \equiv 1 \cdot 0 \cdot 1 = 0 \pmod{7}。

题型18：容斥原理 (Inclusion-Exclusion Principle)

问题：求1到1000之间不能被5、6、8中任意一个整除的数的个数。 方法：总数 - (能被5整除的) - (能被6整除的) - (能被8整除的) + (能被5和6整除的) + (能被5和8整除的) + (能被6和8整除的) - (能被5、6、8都整除的)。 计算：

  • ∣S∣=1000|S|=1000。
  • ∣A5∣=⌊1000/5⌋=200|A_5| = \lfloor 1000/5 \rfloor = 200。
  • ∣A6∣=⌊1000/6⌋=166|A_6| = \lfloor 1000/6 \rfloor = 166。
  • ∣A8∣=⌊1000/8⌋=125|A_8| = \lfloor 1000/8 \rfloor = 125。
  • $|A_{5,6}| = \lfloor 1000/\text{lcm}(5,6) \rfloor = \lfloor 1000/30 \rfloor = 33$。
  • $|A_{5,8}| = \lfloor 1000/\text{lcm}(5,8) \rfloor = \lfloor 1000/40 \rfloor = 25$。
  • $|A_{6,8}| = \lfloor 1000/\text{lcm}(6,8) \rfloor = \lfloor 1000/24 \rfloor = 41$。
  • $|A_{5,6,8}| = \lfloor 1000/\text{lcm}(5,6,8) \rfloor = \lfloor 1000/120 \rfloor = 8$。
  • 结果: $1000 - (200+166+125) + (33+25+41) - 8 = 1000 - 491 + 99 - 8 = 600$。

题型19：卡特兰数 (Catalan Numbers)

问题：一个栈（先进后出）的进栈序列为1, 2, 3, ..., n，有多少个不同的出栈序列？ 方法：这是卡特兰数的经典应用之一。其他应用包括：nn个节点的二叉树形态数、凸n+2n+2边形三角剖分数、n×nn \times n 格网上从左下到右上不穿过对角线的路径数等。 公式：

$$C_n = \frac{1}{n+1} C_{2n}^n = \frac{C_{2n}^n - C_{2n}^{n-1}}{1} $$

计算：对于 n=3n=3，出栈序列数是 C3=14C63=14⋅20=5C_3 = \frac{1}{4} C_6^3 = \frac{1}{4} \cdot 20 = 5。

题型20：动态规划计数 (DP for Counting)

问题：在一个 N×MN \times M 的网格中，从左上角走到右下角，每次只能向右或向下走，有多少种不同的路径？ 方法：虽然这题有组合公式 CN+M−2N−1C_{N+M-2}^{N-1}，但其思想是DP的。更复杂的情况（如网格中有障碍物）必须用DP。 DP模型：

  • 状态：dp[i][j]dp[i][j] 表示从左上角 (0,0)(0,0) 走到 (i,j)(i,j) 的路径数。
  • 转移方程：要到达 (i,j)(i,j)，只能从 (i−1,j)(i-1,j) 向下或 (i,j−1)(i,j-1) 向右。所以 dp[i][j]=dp[i−1][j]+dp[i][j−1]dp[i][j] = dp[i-1][j] + dp[i][j-1]。
  • 初始化：dp[j]=1dp[j] = 1, dp[i]=1dp[i] = 1。
  • 答案：dp[N−1][M−1]dp[N-1][M-1]。

四、练习

A. 选择题

  1. 将4个不同的小球放入3个不同的盒子，且不允许盒子为空，共有多少种方法？ A. A43A_4^3 B. C43C_4^3 C. S(4,3)×3!S(4,3) \times 3! D. S(4,3)S(4,3)

  2. 5对夫妇参加晚会，从中选出4个人组成一个小组，要求这4个人中不能有任何一对夫妇，有多少种选法？ A. C104−5⋅C82C_{10}^4 - 5 \cdot C_8^2 B. C54×24C_5^4 \times 2^4 C. A54×24A_5^4 \times 2^4 D. C104−5C_{10}^4 - 5

  3. 计算 C(10,0)+C(10,1)+⋯+C(10,10)C(10,0) + C(10,1) + \dots + C(10,10) 的值是？ A. 10! B. 100 C. 1024 D. 512

答案与解析:

  1. C. 这是“有序分配问题”（题型10），也叫“满射”计数。将4个不同物品分成3个非空组（S(4,3)S(4,3)），再将这3组分配给3个不同盒子（3!3!）。
  2. B. 分步解决：第一步，从5对夫妇中选出4对，有 C54C_5^4 种选法。第二步，从选出的每一对夫妇中各选一人，每对都有2种选择，共 242^4 种选法。总数 C54×24C_5^4 \times 2^4。
  3. C. 根据二项式定理，$(1+1)^{10} = \sum_{k=0}^{10} C_{10}^k \cdot 1^k \cdot 1^{10-k} = \sum_{k=0}^{10} C_{10}^k$。所以结果是 210=10242^{10} = 1024。

B. 程序代码题

问题：计算组合数模大质数 题意概括：给定 n,m,pn, m, p，计算 Cnm(modp)C_n^m \pmod p 的值。pp 是一个大质数。 核心思路：Cnm=n!m!(n−m)!(modp)C_n^m = \frac{n!}{m!(n-m)!} \pmod p。除法在模运算中用乘以逆元来代替。根据费马小定理，当 pp 为质数时，ap−2≡a−1(modp)a^{p-2} \equiv a^{-1} \pmod p。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

ll p; // 模数

// 快速幂计算 (a^b) % p
ll qpow(ll a, ll b) {
    ll res = 1;
    a %= p;
    while (b) {
        if (b & 1) res = (res * a) % p;
        a = (a * a) % p;
        b >>= 1;
    }
    return res;
}

// 计算 a 在模 p 下的逆元
ll inv(ll a) {
    return qpow(a, p - 2);
}

// 计算组合数 C(n, m) % p
ll C(ll n, ll m) {
    if (m > n) return 0;
    if (m == 0 || m == n) return 1;
    if (m > n / 2) m = n - m;

    ll num = 1, den = 1;
    // 计算分子 n * (n-1) * ... * (n-m+1)
    for (ll i = 0; i < m; ++i) {
        num = (num * (n - i)) % p;
    }
    // 计算分母 m!
    for (ll i = 1; i <= m; ++i) {
        den = (den * i) % p;
    }
    
    // 结果 = 分子 * 分母的逆元
    return (num * inv(den)) % p;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll n, m;
    cin >> n >> m >> p;
    cout << C(n, m) << endl;
    return 0;
}
  • 复杂度分析：
    • 时间复杂度: O(mlog⁡p)O(m \log p)。计算分子分母需要 O(m)O(m)，求逆元用快速幂需要 O(log⁡p)O(\log p)。
    • 空间复杂度: O(1)O(1)。
  • 优化：如果需要多次计算组合数，可以预处理 11到 nn 的阶乘和阶乘的逆元，将单次查询复杂度降至 O(1)O(1)（预处理复杂度为 O(n)O(n)）。
  1. 评测队列
  2. 服务状态
  3. 兼容模式
  4. 主题
  2. 陕ICP备2025061476号
  3. Worker 0, 207ms
  4. Powered Dong Dong