每日一题[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}$$