每日一题[2728]离散集数

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

答案    49

解析   

法一

设集合 N={1,2,,n}nNn)的所有子集中离散集的个数为 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=0x_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}

 

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

发表回复