一道集合计数竞赛题的求解、应用及探究（上海市育才中学龚新平201801）发表在华东师范大学《数学教学》2008第9期在刚结束的2008年上海市高中数学竞赛（新知杯）中出现了一道关于集合计数的问题，笔者还发现此类问题也经常出现在其他各类竞赛中，下面呈现的是笔者对该问题的求解和应用及几点简单探究。1．问题：用表示集合的不含连续整数的元子集的个数，求。解一：（归纳法）当时，；当时，含1的子集有，共个，含2的子集有，共个，依次类推，；当时，含1的子集有，共个，及，共个，直至子集，共个；含2的子集有，共个，及，共个，即含2的子集共，依次类推，直至最后含的惟一子集，所以；由此猜想：。集合的元子集按是否含元素，有恒等式，从而有，当时，，此时式成立，所以猜想正确。解二：（构造法）显然，；当，且时，；当，且时，设是中不含连续整数的元子集，且，则是的元子集。由集合与是一一对应，所以。2．应用例1：从中任取三个彼此不相邻的自然数（不计顺序），共多少种取法？解：原命题等价于求集合的不含连续整数的三元子集的个数，即。例2：已知集合，求该集合具有下列性质的子集个数：每个子集至少含有两个元素，且每个子集中任意两个元素差的绝对值大于1。（96年上海数竞）解：个。3．探究一：设是集合不含连续整数的子集个数的总和，则有：证明：设是集合不含连续整数且至少含两个元素的子集个数的总和，则集合不含连续整数且至少含两个元素的子集分两类：（1）包含元素的有（即每个有题设性质的子集与的并集，以及（2）不包含元素的有个。从而得递推关系，从而，设，则，显然故，（其中为斐波那契数列），从而，而单元集个，空集一个，故结论成立。例2另解：满足条件的子集个数为。例3：求所有的自然数的个数，，使得在二进制表示下，没有连续的三个数码相同。（99年保加利亚赛题）解：由题意，类似探究的过程，等价于求。例4：由前面的问题与探究一，容易证明下面的组合恒等式：4．探究二：用表示集合的元子集（其中，且）的个数，求。解：当，且时，；当，且时，由集合与是一一对应，所以。例5：集合有多少个至少包含两项且任意两项差的绝对值不小于3的子集？解：满足条件的子集个数为个。5．探究三：用表示集合的元子集（其中，且）的个数，求。解：当，且时，；当，且时，易得。6．探究四：用表示集合的元子集（其中，且）的个数，求。解：当，且时，；当，且时，由集合与是一一对应，故。参考文献：1．一道赛题的解法一览龚新平包志旻《数理天地》2004第9期