每日一题[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.\]

此条目发表在每日一题分类目录,贴了标签。将固定链接加入收藏夹。

发表回复