杨辉三角与组合数逐层相邻求和模型及例题详解杨辉三角是数论与组合数学的基础结构它最核心的价值在于将“多轮递推求和”的复杂过程转化为简单的组合数加权和。一、杨辉三角基础1. 定义杨辉三角是一个三角形数阵第 0 行只有 1 个元素1第 k 行有 k1 个元素首尾均为 1中间每个元素等于它正上方两个元素之和2. 组合数对应关系杨辉三角的第 n 行第 i 个位置从 0 开始编号恰好等于组合数C ( n , i ) \boldsymbol{C(n, i)}C(n,i)即从 n 个元素中选 i 个的方案数。递推公式C(n, i) C(n-1,i-1) C(n-1,i)边界条件C ( n , 0 ) C ( n , n ) 1 C(n,0) C(n,n) 1C(n,0)C(n,n)13. 常用性质对称性C(n, i) C(n,n-i)每行数字左右对称行和性质第 n 行所有数之和为2 n 2^n2n二项式定理杨辉三角本质是二项式展开的系数表二、核心模型逐层相邻求和的终值公式问题描述给定长度为 n 的序列a 0 , a 1 , … , a n − 1 a_0,a_1,\dots,a_{n-1}a0,a1,…,an−1每一轮将相邻两项相加得到新序列重复操作直到只剩一个数求最终的数值。核心结论最终结果 每个元素乘以杨辉三角第 n-1 行对应位置的组合数再求和a n s ∑ i 0 n − 1 C ( n − 1 , i ) × a i \boldsymbol{ans \sum_{i0}^{n-1} C(n-1,\ i) \times a_i}ansi0∑n−1C(n−1,i)×ai数学归纳法证明基例n1 时结果就是a 0 a_0a0系数 C(0,0)1结论成立。归纳假设假设长度为 k 的序列满足结论即终值为∑ i 0 k − 1 C ( k − 1 , i ) ⋅ a i \sum_{i0}^{k-1} C(k-1,i) \cdot a_i∑i0k−1C(k−1,i)⋅ai。归纳推导长度为 k1 的序列第一轮相加得到长度为 k 的序列b i a i a i 1 b_i a_i a_{i1}biaiai1。根据归纳假设终值为∑ i 0 k − 1 C ( k − 1 , i ) ⋅ b i ∑ i 0 k − 1 C ( k − 1 , i ) ( a i a i 1 ) \sum_{i0}^{k-1} C(k-1,i) \cdot b_i \sum_{i0}^{k-1} C(k-1,i)(a_ia_{i1})i0∑k−1C(k−1,i)⋅bii0∑k−1C(k−1,i)(aiai1)展开整理后结合组合数递推公式C ( k , i ) C ( k − 1 , i ) C ( k − 1 , i − 1 ) C(k,i) C(k-1,i)C(k-1,i-1)C(k,i)C(k−1,i)C(k−1,i−1)即可推导出终值为∑ i 0 k C ( k , i ) ⋅ a i \sum_{i0}^k C(k,i) \cdot a_i∑i0kC(k,i)⋅ai结论成立。实例验证以 n5 为例对应杨辉三角第 4 行系数1, 4, 6, 4, 1。若序列为2, 1, 4, 5, 3则终值为2 × 1 1 × 4 4 × 6 5 × 4 3 × 1 53 2\times1 1\times4 4\times6 5\times4 3\times1 532×11×44×65×43×153与题目样例结果完全一致。三、例题精讲牛客竞赛 130226 E 题E-E体育课_蓝桥杯多校模拟赛1. 题目重述已知 n 和 sum构造一个 1~n 的排列使得该排列经过上述逐层相邻相加后结果恰好等于 sum。若存在多组解输出字典序最小的排列。数据范围n ≤ 12 n \le 12n≤12保证有解2. 题意转化根据上面的核心结论问题可以直接转化为给 1~n 每个数分配一个位置每个位置 i 有权重w i C ( n − 1 , i ) w_i C(n-1,i)wiC(n−1,i)使得所有数乘以对应权重的总和等于 sum。要求排列本身的字典序最小。这一步转化是解题的关键它把复杂的多轮递推模拟题变成了一道带权的排列构造搜索题。3. 解题思路因为 n ≤ 12我们可以用DFS枚举排列配合剪枝高效求解。预处理先计算出每个位置的权重杨辉三角第 n-1 行搜索顺序按位置从左到右依次填数每个位置从小到大枚举可用数字这样第一个找到 - 这样第一个找到的合法解就是字典序最小的排列找到后直接输出退出即可剪枝优化如果当前累计的加权和已经超过 sum直接回溯无需继续向下搜索4. 完整代码与解析#includebits/stdc.h#defineintlonglongusingnamespacestd;constintN16;intn,sum;intc[N];// 每个位置的权重杨辉系数intp[N];// 存储当前排列boolst[N];// 标记数字是否被使用// u: 当前填到第u个位置// cnt: 当前累计的加权和voiddfs(intu,intcnt){// 剪枝当前和已超过目标直接回溯if(cntsum)return;// 所有位置填充完毕if(un){if(cntsum){for(inti0;in;i)coutp[i] ;exit(0);// 找到第一个解直接退出保证字典序最小}return;}// 从小到大枚举数字保证字典序for(inti1;in;i){if(!st[i]){st[i]true;p[u]i;dfs(u1,cnti*c[u]);st[i]false;p[u]0;}}}signedmain(){cinnsum;// 特判 n1if(n1){cout1;return0;}// 预处理杨辉三角第 n-1 行的系数// 递推公式C(n-1, i) C(n-1, i-1) * (n - i) / ic[0]1;for(inti1;in;i){c[i]c[i-1]*(n-i)/i;}dfs(0,0);return0;}5. 代码要点说明系数计算使用递推公式C ( n − 1 , i ) C ( n − 1 , i − 1 ) × ( n − i ) / i C(n-1,i) C(n-1,i-1) \times (n-i) / iC(n−1,i)C(n−1,i−1)×(n−i)/i无需预处理整张杨辉三角表一行循环即可算出所有系数。字典序保证搜索时按位置从左到右、每个位置从小到大尝试数字第一个合法解必然是字典序最小的找到后直接exit(0)终止程序。剪枝优化每一步都检查当前累计和是否超过 sum超过则立即回溯大幅减少无效搜索量。特判 n1避免循环不执行导致系数错误直接输出 1。6. 样例验证输入5 53预处理系数第 4 行 →[1, 4, 6, 4, 1]DFS 搜索到排列2 1 4 5 3时加权和 2×1 1×4 4×6 5×4 3×1 53符合条件直接输出。四、总结题型识别只要题目出现“相邻两项反复相加直到剩一个数”立刻联想到杨辉三角加权和模型。核心转化将多轮递推转化为静态的线性加权和系数为杨辉三角第 n-1 行的组合数。构造策略求字典序最小的排列时按位置从左到右、从小到大枚举数字的 DFS 是最直接的写法配合和的剪枝可轻松通过 (n \le 12) 的数据。
)
