杨辉三角进阶-北京尧图网络

杨辉三角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。

杨辉三角进阶

相关推荐

从单卡到集群，代码一行不改？Qwen3.5联手Twinkle把大模型训练玩出了新高度！

用 tri-forge 造一个合规 skill，版本门和 junction 先给我上了两课

论文对策建议太空怎么办？普通大学生先让每条建议对应一个问题

更多资讯

5 分钟部署 OpenClaw：从零到运行的完整流程（含 TaoToken 统一 Key 配置）

Linux自学第13天：系统管理与Shell脚本入门

3个核心步骤搞定灰烬攻略，实战项目避坑指南

基于mongoose + MFC 搭建本地HTTP服务器：TaoToken 统一 Key 接入与 curl 联调配置

3步搞定dc电源线选型，这份速查手册让项目不再翻车

三国志13下载报错多？一文搞懂5种方案

今日更新

2k显示屏性能优化踩坑：版本升级后API全变了，这份源码解析救了我

3步搞定美眉图实战项目，告别官方文档抓不住重点

3步搞定黄金大劫案项目搭建从入门到精通

本周精选

深入解析Transformer多头注意力机制与工程优化

OpenClaw 的 Skills 跑学习任务，模型通道改到 TaoToken 通道行不行？

ChatGPT报错Oops, an error occurred! 全链路排查指南

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？