每日一题[1274]小构造

已知 $n$ 是正整数，集合 $M=\{x\mid 1\leqslant x\leqslant n,x\in\mathbb N^{\ast}\}$ 的元素和为奇数的非空子集的个数为_______．

答案    $2^{n-1}$．

解析    

构造一    设 $$f(x)=\prod_{k=1}^n\left(1+x^k\right)$$ 则题中所求非空子集的个数为 $f(x)$ 的展开式中 $x$ 的奇次项的系数之和，为 $$\dfrac {f(1)-f(-1)}2=2^{n-1}.$$

构造二    记符合题意的非空子集组成集合 $P$，集合 $M$ 的所有子集组成集合 $N$，则集合 $P$ 与集合 $\complement_{N}P$，那么存在一一映射 $$f:P\to \complement_{N}P,x\mapsto \begin{cases} x-\{1\},&1\in x,\\ x\cup\{1\},&1\notin x.\end{cases}$$ 因此 $${\rm Card}(P)={\rm Card}\left(\complement_{N}P\right)=\dfrac 12{\rm Card}(N)=2^{n-1}.$$