Counting in Subset help

Oct 2007
517
6
Santiago
Hey guys need help with this question..


Let
S = {0,1,2,....,20}


(a) How many subsets of S are there?
(b) How many subsets of S contain numbers divisible by 3?
(c) How many subsets of S contain 7, 9 and 15?
(d) How many subsets of S do not contain 7, 9 and 15?
(e) How many subsets of S contain 7, 9 and 15 but not 11 and 12?

My Solutions

a) \(\displaystyle \sum_{i=0}^{20} = \binom{20}{i}\)

b) \(\displaystyle \sum_{i=0}^{7} = \binom{7}{i}\)​

c) \(\displaystyle \sum_{i=0}^{3} = \binom{3}{i}\)​

d) \(\displaystyle \sum_{i=0}^{18} = \binom{18}{i}\)​

e) c) \(\displaystyle \sum_{i=0}^{3} = \binom{3}{i}\)


Are my solutions correct? thanks :)
 
May 2010
4
1
a)the number of subsets is 2^21

this is because every element is either in or not in the subset

this gives 2 combinations for each element.

b) this one is tricky....do they mean contain ALL numbers divsible by 3 ? or some number divisible by 3?

if they are looking for the first ...then
7 of the elements are IN...the rest can be either IN or not IN.
2^24

c)2^18

d)2^18

e)2^16
 
Oct 2007
517
6
Santiago
a)the number of subsets is 2^21

this is because every element is either in or not in the subset

this gives 2 combinations for each element.

b) this one is tricky....do they mean contain ALL numbers divsible by 3 ? or some number divisible by 3?

if they are looking for the first ...then
7 of the elements are IN...the rest can be either IN or not IN.
2^24

c)2^18

d)2^18

e)2^16
For b) they are looking for "contain ALL numbers divisible by 3. Sorry why is it 2^24? where did the 24 come from and also could you explain the why you use 2^ and c),d) and e).... thank you..
 
May 2010
4
1
first think about the "powerset" as a string of 0's and 1's.

0 if the element is not in the set and 1 if it is.

the number of possible subsets is the same as the number of combos for the string....the string has the same number of characters as there are elements in the set.

that is why you get 2^n subsets for a set with n elements.


for b)
typo from me....ofc it should be 2^14 subsets

since there are 7 numbers from 0-20 that are divisible by 3
0,3,6,9,12,15,18 that leaves 14 elements that can be either in or not in the subset.
 
  • Like
Reactions: jvignacio