杨辉三角Pascals Triangle本质上就是组合数的三角形排列。它包含了排列组合中最核心的递推关系所有公式都可以从组合数中推导出来。https://www.bilibili.com/video/BV1bFXPBWEH2/?spm_id_from333.337.search-card.all.clickvd_source93e6c6375fca5150774297f9e50d1f66一、核心递推公式帕斯卡法则这是杨辉三角最根本的公式几何意义每个数等于它左上方和右上方两个数之和。text1 1 1 1 2 1 1 3 3 1 1 4 6 4 1例如第4行第2个数3 第3行第1个数1 第3行第2个数2。二、行和公式第n行所有数之和三、对称公式杨辉三角左右对称例如第4行1, 4, 6, 4, 1\binom{4}{1} \binom{4}{3} 4。四、单行递推公式单行递推公式是组合数学中一个非常实用的工具。它允许我们利用第 kk 个组合数快速计算出同一行第 k1k1 个组合数从而在无需计算阶乘或依赖杨辉三角上一行的情况下高效地生成整行数据。已知第n行第k个数推第k1个数示例第5行已知\binom{5}{2} 10则\binom{5}{3} 10 \times \frac{5-2}{21} 10 \times 1 10。记忆口诀分子递减分母递增。公式证明由组合数定义出发例如得到第 7 行1, 7, 21, 35, 35, 21, 7, 1。可以发现使用单行递推公式时计算过程会自动体现左右对称性。当计算到行中间之后由于分子逐渐减小、分母逐渐增大比例因子变为分数组合数开始递减。与帕斯卡规则的对比在算法竞赛中的应用应用1O(n) 时间输出杨辉三角第 n 行void printRow(int n) { long long cur 1; // C(n, 0) 1 cout cur ; for (int k 0; k n; k) { cur cur * (n - k) / (k 1); cout cur ; } }时间复杂度 O(n)空间复杂度 O(1)。应用2求二项式展开中系数最大的一项二项式系数随着 kk 递增而先增后减单行递推可用于快速定位最大值位置。应用3配合取模运算当模数 MM 为质数时用费马小定理求逆元可处理 nn 很大的情况。五、杨辉三角第 n 行公式直接计算第 k 个第n行第k个数从0开始六、杨辉三角与二项式定理杨辉三角的第n行正好是展开式的系数七、常见二级结论公式八、奇偶性与位置洛谷P2822 前置知识杨辉三角第n行的奇数个数 其中 popcount(n) 是 n 的二进制中 1 的个数例如第0行1popcount(0)0201201正确第3行1,3,3,14个奇数3的二进制11popcount24正确九、CSP-J 常见考法考法1直接求组合数杨辉三角第6行第2个数是多少解15考法2求某行所有数之和杨辉三角第10行所有数之和为多少解考法3已知前一行推下一行已知第7行某几个数求第8行对应数。解用帕斯卡法则考法4找规律填数杨辉三角中某位置缺一个数用递推关系补上。十、核心公式速查表十一、记忆口诀每行两端都是1中间等于肩上和。行号n和是2ⁿ左右对称不会错。第k个用组合排列公式直接算。二项展开看系数杨辉三角全都有。如果想进一步练习可以试试这道CSP-J常考题杨辉三角第2024行共有多少个奇数提示用公式2024的二进制是111111010001的个数为6让我数一下答案是64。