Question

设集合A=｛1,2,3,4,5,6｝,B=｛4,5,6,7,8｝,则满足S包含于A且S∩B≠空集的集合S的个数是多少

Answer 1

s为A子集,且s与B有交集,则

算法一：直接法

先确定S∩B的可能个数,即在4、5、6中选择：C1/3+C2/3+C3/3=3+3+1=7

再确定其他可能个数,即在1、2、3中选择：C0/3+C1/3+C2/3+C3/3=1+3+3+1=8

以上两步相互独立,所以总数=7*8=56

算法二：排除法

作为A的子集,总个数为：C0/6+C1/6+C2/6+.+C6/6=1+6+15+20+15+6+1=64

与B无交集的个数,即在1、2、3中选择：C0/3+C1/3+C2/3+C3/3=1+3+3+1=8

所以总数=64-8=56