离散数学
与组合计数

答案：B. 15

C(6,2) = 6×5 / (2×1) = 30/2 = 15

考点：组合数 C(n,m) 表示「从 n 个不同元素中取 m 个、不计顺序」的取法数，公式为 n!/(m!(n−m)!)。

易错：算成 6×5=30，忘记除以 2! 去序。

答案：C. 24

P(4,3) = 4×3×2 = 24

考点：排列数 P(n,m) 计较顺序，等于从 n 开始连续往下乘 m 个因子：n×(n−1)×…×(n−m+1)。

易错：与组合数混淆，错选 C(4,3)=4，忽略了取出的 3 个元素还要排顺序。

答案：A. 10

不分角色→组合：C(5,2) = 5×4/2 = 10

考点：题干强调「不分角色」，说明两人交换位置是同一种选法，应当用组合而不是排列。

易错：看到「从 5 人中选 2 人」就按排列算成 5×4=20。

答案：B. 32

第n行之和 = 2ⁿ，第5行 = 2⁵ = 32。
验证：1+5+10+10+5+1 = 32 ✅

考点：杨辉三角第 n 行恰好是 (1+1)ⁿ 的二项式系数，所以该行所有数之和等于 2ⁿ。

易错：把「第 5 行」当成只有 5 个数，或误以为从第 1 行起算而得 2⁴=16。

#include <iostream>
using namespace std;

int main() {
    int n = 6, m = 3;                  // 求 C(6, 3)

    // 方法一：组合数公式 C(n,m) = [n(n-1)…(n-m+1)] / m!
    // 边乘边除，每一步结果都是整数，可避免中间溢出
    long long c = 1;
    for (int i = 1; i <= m; i++)
        c = c * (n - m + i) / i;       // 依次乘 4、5、6，依次除 1、2、3
    cout << "C(6,3) = " << c << endl;  // 20

    // 方法二：杨辉三角递推 C(n,m) = C(n-1,m-1) + C(n-1,m)
    long long tri[10][10] = {0};
    for (int i = 0; i <= n; i++) {
        tri[i][0] = 1;                 // 每行第一个都是 1
        for (int j = 1; j <= i; j++)
            tri[i][j] = tri[i - 1][j - 1] + tri[i - 1][j];
    }
    cout << "杨辉三角 C(6,3) = " << tri[n][m] << endl;   // 20
    return 0;
}

答案：C(6, 3) = 20。所以 3×3 网格从左下走到右上共有 20 条最短路径。

思路：从左下走到右上，一共要走 3 步向右 + 3 步向上 = 6 步。只要决定"这 6 步里哪 3 步是向右"，整条路线就唯一确定了，所以有 C(6,3) 种走法：C(6,3) = 6×5×4 ÷ (3×2×1) = 120 ÷ 6 = 20。程序里给了两种实现：公式法（边乘边除）和杨辉三角递推法（C(n,m)=C(n-1,m-1)+C(n-1,m)，本质就是程序里的网格 DP f[i][j] = f[i-1][j] + f[i][j-1]）。

考点：组合数 C(n,m) 的意义与公式、杨辉三角递推、"网格路径 = 组合计数"这个经典模型。

易错：① 数步数别弄错：3×3 网格要走 3 步右 + 3 步上共 6 步，所以是 C(6,3)，不是 C(3,3)；② 公式里分子是 6×5×4、分母是 3×2×1，别只除一半；③ 数据范围要留意：组合数增长极快——C(20,10) = 184756、C(30,15) = 155117520 都还装得下 int，但 C(34,17) = 2333606220 就已经超过 int 上限 2147483647，C(67,33) = 14226520737620288370 更是连 64 位整数都装不下，这时要用 long long、高精度，或者直接在模意义下用杨辉三角 / 逆元来算。

答案：C. 81

每封信有3种选择，4封信独立：3⁴ = 81。
这是可重排列，不是P也不是C！

考点：「每封信可自由选择信箱」是分步计数：4 封信各做一次独立选择，把每步的方案数相乘即 3×3×3×3。

易错：误用隔板法 C(3+4−1,4)=15，隔板法只适用于「相同物品」，而信是互不相同的。

答案：B. C(11,4)

杨辉三角递推：C(n,m)+C(n,m+1)=C(n+1,m+1)
C(10,3)+C(10,4)=C(11,4)=330

考点：这是杨辉三角（帕斯卡）递推恒等式 C(n,m) + C(n,m+1) = C(n+1,m+1) 的直接应用。

易错：把下标或上标直接相加，错拼成 C(20,7) 之类不成立的组合数。

答案：B. 5

卡特兰数 Cat(3) = C(6,3)/4 = 20/4 = 5
列举：((())), (()()), (())(), ()(()), ()()()

考点：n 对括号的合法排列数是卡特兰数 Cat(n) = C(2n,n)/(n+1)，它同时对应出栈序列、二叉树形态等问题。

易错：直接把 C(6,3)=20 当作答案，忘了要去掉形如 )( 开头的非法序列。

答案：A. 2×9!

捆绑法：把甲乙绑在一起看作1个整体，共9个元素全排列=9!

甲乙内部可以互换：×2

总计 = 2 × 9! = 2 × 362880 = 725760

考点：「必须相邻」用捆绑法：把甲乙看成一个整体参与排列，再乘上整体内部的顺序。

易错：只算 9! 就交卷，忘记甲乙两人还可以互换位置，漏乘 2。

答案：A. 2450

和为偶数 → 两数同奇或同偶

奇数50个：C(50,2)=50×49/2=1225

偶数50个：C(50,2)=1225

总计 = 1225+1225 = 2450（加法原理）

考点：按奇偶分类讨论：两数之和为偶数，当且仅当它们同奇或同偶，再用加法原理把两类取法相加。

易错：直接用 C(100,2)=4950 当答案，忽略「同奇或同偶」这一限制条件。

答案：B. 14

Cat(4) = C(8,4)/5 = 70/5 = 14

卡特兰数前几项：Cat(0)=1, Cat(1)=1, Cat(2)=2, Cat(3)=5, Cat(4)=14

考点：卡特兰数满足递推 Cat(n) = C(2n,n)/(n+1)，n 个元素的合法出栈序列数正是 Cat(n)。

易错：与 4! = 24 混淆，或错把 C(8,4) = 70 当作答案而漏除 n+1。

答案：A. 150

方法：容斥原理

无限制分配：3⁵ = 243

减去至少1人空手：C(3,1)×2⁵ = 3×32 = 96

加回至少2人空手：C(3,2)×1⁵ = 3×1 = 3

243 - 96 + 3 = 150

考点：「每人至少 1 本」适合用容斥原理：先算无限制方案数 3⁵，再扣去有人空手的情况并逐层加减。

易错：只用 3⁵ − C(3,1)×2⁵ 就结束，漏掉最外层「加回至少 2 人空手」的 +3 这一项。