培玉 · 一试

专题地图 › 经典的计数模型

2009 年河南预赛 · 第 14 题

F3解答题经典的计数模型

（13 分）设集合 $I = {1, 2, 3, \dots, n}$ （ $n \in N^{*}$ ）。选择 $I$ 的两个非空子集 $A$ 和 $B$ ，使 $B$ 中最小的数大于 $A$ 中最大的数，记不同的选择方法数为 $a_{n}$ ，显然 $a_{1} = 0, a_{2} = (2 2) = 1$ 。

（1）
求 $a_{n}$ ；
（2）
记数列 ${a_{n}}$ 的前 $n$ 项和为 $S_{n}$ ，求 $S_{n}$ 。

作答

这是解答题，请在纸上写出完整过程。写完后对照解答给自己评分。

解析

为什么评为 F3（会透露解法方向）

需建立并集加切口的唯一编码，再求加权二项式和与加权等比和，两次求和都要检查初始边界。

用到的方法（会透露解法方向）

核心工具：把对象唯一编码后分类计数、算两次与贡献法

专题卡：所有子集的元素和：固定一个元素，数它出现几次