6.4: Summary

Most of the time, counting problems all boil down to a variation of one of the following three basic situations:

• \(n^k\) — this is when we have \(k\) different things, each of which is free to take on one of \(n\) completely independent choices.

• \(n^{\underline{k}}\) — this is when we’re taking a sequence of \(k\) different things from a set of \(n\), but no repeats are allowed. (A special case of this is \(n!\), when \(k=n\).)

• \(\binom{n}{k}\) — this is when we’re taking \(k\) different things from a set of \(n\), but the order doesn’t matter.

Sometimes it’s tricky to deduce exactly which of these three situations apply. You have to think carefully about the problem, and ask yourself whether repeated values would be allowed, and whether it matters what order the values appear in. This is often subtle.

As an example, suppose my friend and I work out at the same gym. This gym has 18 different weight machines to choose from, each of which exercises a different muscle group. Each morning, we each do a quick 30-minute workout session divided into six 5-minute blocks, and we work with one of the machines during each block, taking turns spotting each other. One day my friend asks me, “hey Stephen, have you ever wondered: how many different workout routines are possible for us?"

I was, of course, wondering exactly that. But the correct answer turns out to hinge very delicately on exactly what “a workout routine" is. If we could select any weight machine for any 5-minute block, then the answer is \(18^6\), since we have 18 choices for our first block, 18 choices for our second, and so on. (This comes to 34,012,224 different routines, if you’re interested).

However, on further inspection, we might change our mind about this. Does it make sense to choose the same machine more than once in a 30-minute workout? Would we really complete a workout that consisted of “1.Biceps 2.Abs, 3.Pecs, 4.Biceps, 5.Biceps, 6.Biceps?" If not (and most trainers would probably recommend against such monomaniacal approaches to excercise) then the real answer is only \(18^{\underline{6}}\), since we have 18 choices for our first block, and then only 17 for the second, 16 for the third, etc. (This reduces the total to 13,366,080.)

But perhaps the phrase “a workout routine" means something different even than that. If I tell my physical therapist what “my workout routine" consisted of this morning, does he really care whether I did triceps first, last, or in the middle? He probably only cares about which machines (and therefore which muscle groups) I worked out that morning, not what order I did them in. If this is true, then our definition of a workout routine is somewhat different than the above. It’s no longer a consecutive sequence of machine choices, but rather a set of six machine choices. There would only be \(\binom{18}{6}\) of those, or a mere 18,564. So as you can see, the answer radically depends on the precise interpretation of the concepts, which means that to successfully do combinatorics, you have to slow down and think very carefully.