How do I do Combinatorics / Counting?

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.