# Discrete Math Pascal's Triangle and n choose k

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.

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

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

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

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$.