专题地图 › 排列组合
一试训练题
F2填空题排列组合
给定正整数 n,子集 T⊆{1,…,n} 的权重是 ∏j∈T2/[j(j+3)]。求所有非空子集的权重和。
作答
分数写 a/b,根号写 √ 或 sqrt,π 写 pi 也可以。
标准答案:n+32n
解析
思路
每个位置只有选与不选两个状态,把全部子集权重装进一个乘积。
解答
计入空集权重1,有 1+∑T=∅w(T)=∏j=1n(1+j(j+3)2)=∏j=1nj(j+3)(j+1)(j+2)=(n+1)n+33。减去空集项,所求为 n+32n。
复核
n=1 时唯一项是 2/(1⋅4)=1/2,公式也给出1/2;n=2 时三项为1/2、1/5、1/10,总和4/5。乘积恒等式对n=1仍成立,不需假设n至少为3。
方法总结
子集权重积可以逐元素展开;最后必须扣除空方案,再检验短乘积的边界。
为什么评为 F2(会透露解法方向)
展开乘积编码子集,再把二次因子分解成两条可约的乘积链。
用到的方法(会透露解法方向)
核心工具:各步独立选择的乘法原理、裂项相消
专题卡:子集、集合对的计数:给每个元素列状态,再相乘