每日一题[2113]构造母函数

定义：有限非空数集 $\Omega$ 的所有元素的”乘积“称为数集 $\Omega$ 的”积数“，例如：集合 $\Omega=\{1,2,3\}$，其积数为 $1\cdot 2\cdot 3=6$．

1、若有限数集 $A=\{a_1,a_2,a_3\}$，求证：集合 $A$ 的所有非空子集的积数之和

$$S_A=(1+a_1)(1+a_2)(1+a_3)-1.$$

2、根据第 $(1)$ 小题的结论，对于有限非空数集 $A=\{a_1,a_2,\cdots,a_n\}$（$n\in\mathbb N^{\ast}$，$n\geqslant 2$），记集合 $A$ 的所有非空子集的积数之和为 $S_n$，写出 $S_n$ 的表达式，并利用数学归纳法予以证明．

3、若有限集 $\Omega=\left\{\dfrac 12,\dfrac 13,\dfrac 14,\cdots,\dfrac1{100}\right\}$，求出 $\Omega$ 中所有奇数个元素构成的非空子集的积数之和 $M$ 以及 $\Omega$ 中所有偶数个元素构成的非空子集的积数之和 $N$．

解析

1、根据题意，有

$$(1+a_1)(1+a_2)(1+a_3)-1=a_1+a_2+a_3+a_1a_2+a_2a_3+a_3a_1+a_1a_2a_3,$$ 即集合 $A$ 的所有非空子集的积数之和，命题得证．

2、集合 $A$ 的子集的积数（空集的积数视为 $1$）与

$$(1+a_1)(1+a_2)\cdots (1+a_n)$$ 展开后的项一一对应，因此 $$S_n=(1+a_1)(1+a_2)\cdots(1+a_n)-1.$$ 该命题在 $n=1$ 时显然成立；假设该命题对 $n$ 成立，则对于 $n+1$ 个元素的集合 $A$，它的所有子集的积数可以按包含元素 $a_{n+1}$ 和不包含元素 $a_{n+1}$ 的分类计算，于是 $$S_{n+1}+1=(S_n+1)+(S_n+1)\cdot a_{n+1}=(S_n+1)(1+a_{n+1}),$$ 即 $$S_{n+1}=(1+a_1)(1+a_2)\cdots (1+a_n)(1+a_{n+1})-1,$$ 命题得证．

3、根据题意，有

$$\begin{cases} M+N=(1+a_1)(1+a_2)\cdots (1+a_n)-1,\\ M-N=(1-a_1)(1-a_2)\cdots (1-a_n)-1,\end{cases}$$ 因此 $$\begin{cases} M+N=\left(1+\dfrac 12\right)\left(1+\dfrac 13\right)\cdots\left(1+\dfrac1{100}\right)-1=\dfrac{99}2,\\ M-N=\left(1-\dfrac 12\right)\left(1-\dfrac 13\right)\cdots\left(1-\dfrac1{100}\right)-1=-\dfrac{99}{100},\end{cases}$$ 解得 $M=\dfrac{4851}{200}$，$N=\dfrac{5049}{200}$．

比如 $n=3$ 时，有

$$M-N=-a_1-a_2-a_3+a_1a_2+a_2a_3+a_3a_1-a_1a_2a_3=(1-a_1)(1-a_2)\cdots (1-a_n)-1.$$