Find count of subsets which have at least one even number

Question

I have this set $S = \{1, 2, 3, ..., 30\}$ a I have to find count of subsets of subset $S$ which have at least one even number.

I solved it that I substracted from total count of subsets ($2^{30}$) that subsets which have only odd numbers. Like that:

$2^{30}-\sum\limits_{i=0}^{15} {15\choose i}$

Is my solution correct?

Note the to be a subset of only odd numbers is the same as being a subset of {1,3,... 29} which has 15 elements so the total number of odd only subsets is $2^{15}$. Which I think is the same result. (Does $\sum { n \choose i} = 2^n?$ It seems to me that it does but I'm being fast and dirty. — fleablood, Nov 21 '15 at 23:43

score 1 · Accepted Answer · answered Nov 21 '15 at 23:30

1

It’s correct but incomplete: $\sum_{i=0}^{15}\binom{15}i$ is just the total number of subsets of a set of $15$ things, so you can simplify the summation to ... ?

answered Nov 21 '15 at 23:30

Brian M. Scott

616,228

$2^{30} - 2^{15}$? – Johny Nov 21 '15 at 23:34
1

@MLN96: Exactly. Or you can write it as $2^{15}(2^{15}-1)$, though I don’t think that this is really a simplification. – Brian M. Scott Nov 21 '15 at 23:36
thanks for answer :) – Johny Nov 21 '15 at 23:37
@MLN96: You’re welcome. – Brian M. Scott Nov 21 '15 at 23:37

Find count of subsets which have at least one even number

1 Answers1