一道“交替和”的计数题

kuing

对于集合 N={1, 2, 3, ..., n} 的每一个非空子集，定义一个“交替和”如下：按照递减的次序重新排列该子集，然后从最大数开始交替地减、加后继的数。例如集合 {1, 2, 4, 6, 9} 的交替和是 9-6+4-2+1=6，集合 {5} 的交替和为 5。当集合 N 中的 n=2 时，集合 N={1, 2} 的所有非空子集为 {1}, {2}, {1, 2}，则它的“交替和”的总和 S2=1+2+(2-1)=4，则当时 n=3 时，S3=_____；根据 S1、S2、S3，猜想集合 N={1, 2, 3, ..., n} 的每一个非空子集的“交替和”的总和 Sn=__________。

下面直接求 `S_n`。

考虑所有“交替和”中各数出现的次数及其前面的正负号。

对于数 `n`，它最大，符号一定是正，其后的 `n-1` 个数任意出现，所以 `n` 一共出现 `2^{n-1}` 次，加起来就是 `n\cdot2^{n-1}`。

对于数 `k`（`k<n`），如果排在它前面的数有偶数个，它的符号就是正的，否则就是负的。
前面的数有 `n-k` 个数可选，所以：
有 `C_{n-k}^0+C_{n-k}^2+C_{n-k}^4+\cdots` 种情况是正的，
有 `C_{n-k}^1+C_{n-k}^3+C_{n-k}^5+\cdots` 种情况是负的。
注意到恒等式 `(1-1)^{n-k}=C_{n-k}^0-C_{n-k}^1+C_{n-k}^2-C_{n-k}^3+\cdots`，这说明正的次数与负的次数必定相同，全部加起来就抵消掉了。

综上，`S_n=n\cdot2^{n-1}`。

其妙

很早的老题了，好像起源于早年美国AIME数学竞赛题吧，
doc88.com/p-3418619867831.html