集合S={1,2,...,10},元素的偶数个数不少于奇数个数的所有非空子集的个数答案是637请问如何思考?

Question

集合S={1,2,...,10},元素的偶数个数不少于奇数个数的所有非空子集的个数
答案是637 请问如何思考?

Answer 1

问:集合S={1,2,...,10},元素的偶数个数不少于奇数个数的所有非空子集的个数
先计算这样的子集的个数:该子集中偶数个数和奇数个数相同.
为此,把 S 分为 A = {1,3,5,7,9} 与 B = {2,4,6,8,10} 的并 (注意A和B是不相交的).
我们从A中选k个元素构成子集E,再从B中选k个元素构成子集F(这意味着我们从B中选 5-k 个元素构成子集 B\F ).
那么,E并F就是一个"偶数个数和奇数个数"的子集,而且这样的子集都可以用这种方式得到.
因此,"偶数个数和奇数个数相同"的子集的个数就是 E并F 的个数.
而上述的个数,与 E并(B\F) 的个数相同.
注意 E并(B\F) 相当于从S中选出5个元素,所以,E并(B\F) 的个数是C(10,5).
结论是:"偶数个数和奇数个数相同"的子集的个数为C(10,5).
下面,把S的所有子集分成三类:
第一类:该子集中偶数个数大于奇数个数;
第二类:该子集中偶数个数等于奇数个数;
第三类:该子集中偶数个数小于奇数个数.
显然,第一类子集的个数等于第三类子集个数,
第一类子集的个数 = (1/2)*(第一类子集的个数 + 第三类子集的个数)
= (1/2)*(S的子集个数 - 第二类子集的个数).
所以,"偶数个数不少于奇数个数"的子集个数
= 第一类子集的个数 + 第二类子集的个数
= (1/2)*(S子集个数 + 第二类子集的个数)
= (1/2)*[2^10 + C(10,5)]
= 638.
最后,去掉空集,所求的子集个数为637.