设集合A的元素个数为n,则集合A的含奇数个元素的子集的个数是?
问题描述：
设集合A的元素个数为n,则集合A的含奇数个元素的子集的个数是?
RT
是1/2n吗？
答
A中含有k个元素的子集的数目是C(n,k) = n!/k!(n-k)!,则奇数个元素的子集数为:
C(n,1) + C(n,3) + C(n,5) +...+ C(n,n) 当n是奇数时
或 C(n,1) + C(n,3) + C(n,5) +...+ C(n,n-1) 当n是偶数时.我列过，不论奇偶数都是1/2，是吗？
答案是肯定的。奇偶子集数各占半数。
简单计算一下即可得到。
应用组合公式 C(n-1, k-1) + C ( n-1, k) = C(n, k) 我们有:
C(n-1, 0) + C(n-1, 1) = C(n,1)
C(n-1, 2) + C(n-1, 3) = C(n,3)
......
C(n-1, 2k) + C(n-1, 2k+1) = C(n,2k+1)
也就是说，右边是所有奇数项的和，而左边是关于n-1的二次项目系数。
如果n是偶数，且2k+1 = n-1， 则 左边和 = 2^(n-1)
如果n是奇数，且2k = n-1，则 左边和仍然等于 2^(n-1),
所不论n是奇数还是偶数，奇数子集的个数都是2^(n-1)，而全部子集个数是2^n, 所以奇偶各占半数都是2^(n-1)个。