如果集合 P 中至少含有 2 个元素,且其中任意两个元素的差的绝对值不小于 3,则称 P 为离散集,则集合 M={1,2,3,⋯,10} 的所有子集中离散集的个数为_______.
答案 49.
解析
法一
设集合 N={1,2,⋯,n}(n∈N∗ 且 n⩾)的所有子集中离散集的个数为 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}