# Combinatorics problem - please check my answer and reasoning

Just want to check if my answer and reasoning is correct for the following problem (Not a homework problem - it is a sample question for a test I'm preparing for)

In a survey, viewers were given a list of 20 TV Shows and are asked to label 3 favourites not in any order. Then they must tick the ones that they have heard of before, if any. How many ways can the form be filled, assuming everyone has 3 favourites?

My reasoning:

1) Choose 3 shows out of 20: $c(20,3)$

2) Choosing 0-17 shows from 17 choices: $c(17,0) + c(17,1) + c(17,2) + ... + c(17,16) + c(17,17)$

and add 1) and 2) together for the final answer.

Would this be correct? Is there a better way of doing the second part that doesn't involve so many calculations?

-
Woops- I made a mistake there. Supposed to be multiply 1) and 2) – Arvin May 22 '11 at 4:57

## 1 Answer

Yes, your reasoning is correct up to the last part (implicit in your second part is that they must have heard of their favorites, so that they only need to check or not check the remaining 17). However, the final part is incorrect: you don't add (1) and (2), you multiply them: each person must select both their three favorites and those other programs that they have heard of. Multiplication, not addition, is appropriate here.

As for fewer calculations: what you need to do is pick a subset of the remaining 17 shows to represent the shows you have heard of. There are $2^{17}$ possible subsets, so that's what you want. Alternatively, for each of the remaining 17 programs, you can either have heard of it before or not; so you have one of two choices for each of the remaining 17 programs. That means making a choice from 2 possibilities, 17 times, or $2^{17}$ possibilities.

And alternatively, $$C(17,0) + C(17,1) + \cdots + C(17,17) = (1+1)^{17} = 2^{17}$$ by the binomial theorem, so that's another way to see that the big sum you have is simply $2^{17}$.

So the correct answer is $2^{17}\times\binom{20}{3}$.

-
Ahh thanks, so it actually comes down to choosing if you have or haven't heard of something 17 times which is actually the multiplicative counting principle. Thanks again as always, Arturo =) – Arvin May 22 '11 at 4:44
Also, yes I did mean Multiply 1 and 2, not sure why I said Add instead! – Arvin May 22 '11 at 4:53