2
$\begingroup$

A juggling club has 5 male members and 4 female members.

a) I know the answer to this: "How many nonempty sets of juggling club members can be chosen to perform in a show" is Answer: 2^9 - 1. However,

b) How many nonempty subsets of juggling club members containing at least one female can be chosen? Answer: Shouldn't it be 2^9 - 2^5 - 1? My professor had the answer as just 2^9 - 2^5 without the minus one. But we still need to exclude the empty set right?

Also how can we solve this using n choose k? I am really starting to understand n choose k and it's relation with Pascal's Triangle, but I would like to apply it to this question here.

$\endgroup$
3
$\begingroup$

$$\underbrace{(2^9 - 1)}_{\text{non-empty subsets}} - \underbrace{(2^5 - 1)}_{\text{non-empty sets of men only}} = 2^9 - 2^5$$

$\endgroup$
2
  • $\begingroup$ You might be interested in this entry which explains why $$\sum_{k = 0}^n \binom nk = 2^n$$ $\endgroup$
    – amWhy
    Mar 10 '14 at 17:59
  • $\begingroup$ Concise and clear answer! $\endgroup$
    – user63181
    Mar 11 '14 at 13:11
1
$\begingroup$

It should be the number of nonempty sets you can build with 9 elements, $\sum{9 \choose k}$ which is $2^9 - 1$ MINUS the number of nonempty sets you can build with 5 elements which would correspond to the number of sets in which there are no female jugglers, which would be $\sum{5 \choose k}$, which equals $2^5-1$

Your teacher is correct because the two "$-1$" compensate each other

If you didn't know about the $\sum {n \choose k} = 2^n$ I suggest you try to prove it by induction or you visit http://en.wikipedia.org/wiki/Binomial_coefficient

$\endgroup$
1
$\begingroup$

Although formulas are very useful, it is helpful to do a full analysis each time.

There is a total of $2^9-1$ ways to choose a non-empty subset of our group. Pity about not counting the empty set: I would prefer the performance.

Call a choice of jugglers bad if it is all male. The same analysis shows there are $2^5-1$ bad choices.

Thus the number of good choices is $(2^9-1)-(2^5-1)$. This is $2^9-2^5$.

Or else we could have not worried about the empty set. There are $2^9$ ways to choose a subset, possibly empty. There are $2^5$ ways to choose a subset of the boys. So the number of subsets that contain at least $1$ girl (and are therefore non-empty) is $2^9-2^5$.

The binomial coefficients approach is unpleasant, so we compromise and use a mixed approach.

$1$ girl: There are $\binom{4}{1}$ ways to choose her, and for each choice there are $2^5$ ways to choose a subset of the boys to keep her company. That gives a total of $\binom{4}{1}2^5$ choices.

$2$ girls: There are $\binom{4}{2}$ ways to choose them, and $2^5$ ways to choose a subset of the boys to keep them company.

$3$ girls: There are $\binom{4}{3}$ ways to choose them, and $\dots$.

$4$ girls: There are $\binom{4}{4}$ ways to choose them, and $\dots$.

Add up.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.