# How do I do Combinatorics / Counting?

If someone could give answers and explain, it would be greatly appreciated. Help required studying for a final.

One hundred tickets, numbered 1,2,3,…,100, are sold to 100 different people for a drawing. Four different prizes are awarded, including a grand prize (a trip to Tahiti).

A) How many ways are there to award the prizes?

B) How many ways are there to award the prizes if the person holding ticket 47 wins the grand prize?

C) How many ways are there to award the prizes if the person holding ticket 47 wins one of the prizes?

D) How many ways are there to award the prizes if the person holding ticket 47 does not win a prize?

E) How many ways are there to award the prizes if the people holding tickets 19 and 47 both win prizes?

F) How many ways are there to award the prizes if the people holding tickets 19, 47, 73, and 97 all win prizes?

G) How many ways are there to award the prizes if none of the people holding tickets 19, 47, 73, and 97 wins a prize?

H) How many ways are there to award the prizes if the grand prize winner is a person holding ticket 18, 47, 73, or 97?

I) How many ways are there to award the prizes if the people holding tickets 19 and 47 win prizes, but the people holding tickets 73 and 97 do not win prizes?

• I'm not sure where to start. – Math Student Nov 22 '10 at 2:09
• 100 * 99 * 98 * 97 might be the answer for part A. But, I don't think the same rule would apply for part B or C. I'm tried a lot of things so far but I'm not sure it's right. If the same rule applied, the answer to B would be 99*98*97, which would be the same answer to C, but my intuition thinks that is incorrect. – Math Student Nov 22 '10 at 2:11
• Well, how many ways are there to award 1 prize? And 2? If that is already too difficult, then what if there are only 3 people and you are awarding 2 prizes? You are asking, where to start: start with simple examples, until you think that you have some understanding of what is going on. Then come back here with more specific questions. – Alex B. Nov 22 '10 at 2:12

The two basic rules of counting are:

1. Sum rule: If one event can occur in $n$ different ways, and another, independent, event can occur in $m$ different ways, then the number of different ways in which either one or the other event can occur is $n+m$.

2. Product rule: If one event can occur in $n$ different ways, and another, independent, event can occur in $m$ different ways, then the number of different ways in which both evens can occur is $nm$.

When making choices, you have two basic kinds: if the order in which you make the choices matters, they are called permutations. (For example, choosing the Caesar salad as an appetizer and the shrimp cocktail as the main course is different from choosing the shrimp cocktail as an appetizer and the Caesar salad as a main course). If the order in which you make the choices does not matter, you have combinations. (For example, when choosing teams, it doesn't matter if Bill is chosen first to join team A and Clara is chosen second also for team A, or if Clara is chosen first to join team A and Bill is chosen second also for team A; all that matters is that both Bill and Clara are in team A).

Combining these, you get some basic formulas:

• The number of ways in which you can make $n$ choices, with $m$ options for each, allowing repetitions but where the order of the choice matters (permutations with repetitions), is $m^n$.

• The number of ways in which you can make $n$ choices, with $m$ possibilities, where the order matters but with repetitions not allowed (permutations without repetitions) is $m(m-1)(m-2)\cdots(m-n+1) = \frac{m!}{(m-n)!}$.

• The number of ways in which you can make $n$ choices out of $m$ options, if the order does not matter and repetitions are not allowed, is $\binom{m}{n} = \frac{m!}{n!(m-n)!}$ (called "$m$-choose-$n$", because you are choosing $n$ out of $m$). These are "combinations".

• The number of ways in which you can make $n$ choices, with $m$ options, if the order does not matter and repetitions are allowed is $\binom{m+n-1}{n}$. (Combinations with repetitions).

You probably knew all that, but still...

That said:

A. You need to choose 4 tickets, out of 100 possibilities; you are not allowed to choose the same ticket twice (no repetitions). Since the prizes are all different, the order in which you make the choices matters (draw for the 4th prize, then the 3rd prize, then the 2nd prize, then the Grand Prize; or in whichever order you want). So, which formula above applies, and what is the answer?

B. If ticket 47 will win the Grand Prize, you still need to assign the remaining three prizes. They have to be awarded to people other than ticket 47, no repetitions, but order still matters. How many options do you have, and how many choices to do you need to make? Order matters, no repetitions.

C. This is similar to the above, but this time, ticket 47 may win the Grand Prize, the second, the third, or the fourth place prize. Count each of the four outcomes separately, then apply the Sum rule.

D. Well, if you are going to exclude ticket 47, you have to choose from among the remaining 99 tickets. Order still matters, repetitions are not allowed. So the only difference is the number of options you have.

E. Well, you have two prizes awarded, and two more to award. First award the other two prizes (i.e., count how many ways you can do that). Then decide which prizes go to tickets 19 and 47: you have four prizes you can award, so you need to choose two prizes (to give to 19 and 47); order matters (first prize chosen goes to 19, second to 47), no repetitions. Count that. In total, you need to (i) pick to other winners; pick them in order, so first winner gets the top prize not awarded to 19 or 47, second gets the lower prize not awarded); and (ii) pick which prizes to give to 19 and to 47. You need both things to happen, so you should then use the Product rule.

F. Now you know who the four winners are; you just need to figure out which prizes they get. Count how many ways you can distribute the prizes among the four winners.

G. Similar to D, but now you have to exclude four people instead of one.

H. First decide who wins the Grand Prize. Then pick the other three winners. Then use the Product rule.

I. This is a combination of the ideas from E and D. Use the same method as in E to figure out how many ways there are to award prizes to 19 and 47; then figure out how many ways there are to assign the remaining two prizes to the remaining people if you exclude 73 and 97. Then combine the two answers using an appropriate rule mentioned above.

• What an wonderful explanation! Anybody could actually learn combinatorics out of it! :) – Quixotic Nov 22 '10 at 5:40

Try to solve the questions one award at a time, for each award asking yourself how many people could receive this award? Note that this approach may lead to branching, question C for instance you would get 100*99*98 for the first 3 awards, but the number of persons who may receive the final award is either 1 or 97 depending on whether ticket 47 has already been awarded.

Some of the questions may be simpler to answer if you initially consider what awards a specific person or persons may have, and thereafter how the rest may be distributed.