每日一题[2728]离散集数

如果集合 $P$ 中至少含有 $2$ 个元素,且其中任意两个元素的差的绝对值不小于 $3$,则称 $P$ 为离散集,则集合 $M=\{1,2,3,\cdots,10\}$ 的所有子集中离散集的个数为_______.

答案    $49$.

解析   

法一

设集合 $N=\{1,2,\cdots,n\}$($n\in\mathbb N^{\ast}$ 且 $n\geqslant 4$)的所有子集中离散集的个数为 $x_n$,按离散集中的元素个数 $k$ 分类,在映射\[(a_1,a_2,\cdots,a_k)\mapsto \big(a_1,a_2+2,\cdots,a_k+2(k-1)\big)\]下问题转化为在集合 $\{1,2,\cdots,n-2(k-1)\}$ 中挑选 $k$ 个数(然后依次在每个数上加上 $0,2,\cdots,2(k-1)$ 即得题中要求的离散集),有 $\dbinom{n-2(k-1)}{k}$ 种方法,因此所求\[x_n=\sum_{k=2,\cdots,\left[\frac {n+2}3\right]}\dbinom{n-2(k-1)}{k},\]将 $n=10$ 代入,有\[x_{10}=\dbinom 82+\dbinom63+\dbinom44=28+20+1=49.\]

法二

设集合 $N=\{1,2,\cdots,n\}$($n\in\mathbb N^{\ast}$ 的所有子集中离散集的个数为 $x_n$,则 $x_1=x_2=x_3=0$,$x_4=1$. 当 $n\geqslant 5$ 时,将 $N$ 的子集中的离散集(简称为离散子集)分为两类.

第一类    包含元素 $n$ 的.此时离散子集有两种情形,第一种是形如 $\{m,n\}$ 的二元集合,其中 $m\in\{1,2,\cdots,n-3\}$.第二种是形如 $T\cup\{n\}$ 的集合,其中 $T$ 为集合 $\{1,2,\cdots,n-3\}$ 的离散子集.因此第一类离散集个数为\[(n-3)+x_{n-3}.\]

第二类    不包含元素 $n$ 的.此时离散子集即 $\{1,2,\cdots,n-\}$ 的离散子集,共 $x_{n-1}$ 个.

综上所述,有 $x_n=(n-3)+x_{n-3}+x_{n-1}$,于是\[\begin{array}{c|cccccccccc}\hline n&1&2&3&4&5&6&7&8&9&10\\ \hline x_n&0&0&0&1&3&6&11&19&31&49\\ \hline\end{array}\]

 

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

发表评论