Let’s consider another way to count sequences: first count sets, then arrange them.
Clearly combinations and permutations are very closely related. The formulas to count each are very similar; there is just an extra \(k!\) in the denominator of \(\binom{n}{k}\text{.}\) That extra \(k!\) accounts for the fact that \(\binom{n}{k}\) does not distinguish between the different orders that the \(k\) objects can appear in. We are just selecting (or choosing) the \(k\) objects, not arranging them.
Perhaps “combination” is a misleading label. We don’t mean it like a combination lock (where the order would definitely matter). Perhaps a better metaphor is a combination of flavors — you just need to decide which flavors to combine, not the order in which to combine them.
Does order matter?
Almost every source you look at about combinations and permutations will make some variation of the following claim.
Use a permutation when the order matters, and use a combination when the order does not matter.
What does this even mean? And why is it an absolutely awful way to distinguish between the two counting techniques? Let’s explore with an example.
Suppose you are proposing a new lottery game. In the game, five numbered balls will be randomly shot out of the machine which holds balls numbered 1 to 50. If a player correctly picks the five numbers that come out, they win the jackpot.
Of course, we want to know the odds of winning this lottery game, which requires us to know how many different outcomes there are. The balls fly out of the machine randomly, so one result might be to get the balls
\begin{equation*}
26, 5, 42, 17, 33\text{.}
\end{equation*}
If you were holding the ticket that had numbers \(5, 17, 26, 33, 47\text{,}\) do you expect to have won? Most lottery games would say you have, since you have the same numbers, just in a different order.
In this sense, the order of the numbers does not matter. A better way to say this is that any order of the same numbers is considered the same outcome, and is counted only once. So really, we are counting the sets of five numbers, not the sequences of five numbers. Each outcome is a combination, so the number of outcomes should be \(C(52,5) = \binom{52}{5}\text{.}\)
On the other hand, if we must pick the numbers in the same order they come out of the machine, then we are really matching a sequence of numbers to a sequence of numbers. The number of sequences is \(P(52,5)\text{.}\) In this case, we would say that the order matters.
Okay, so far so good. But what about the following example?
Example 3.4.11.
How many three letter “words” are there in which
the letters appear in alphabetical order?
the letters in the word can come in any order?
Solution.
Does “order matter” for the first question? In some sense, absolutely! We only want to count words where the letters are in the correct order. But from the standard combination/permutation sense of order mattering, it does not.
Much better would be to ask ourselves whether we should represent each outcome as a set of letters or a sequence of letters. It is true that words are a sequence of letters, but are we counting all possible sequences? Nope, just one sequence for each set of letters. Ah, yes, set of letters. Each outcome corresponds exactly to one set of three letters. We are counting sets, so we count combinations. The number of outcomes is \(C(26,3) = \binom{26}{3}\text{.}\)
For the second question, it might look like we want the order to not matter. Well, it doesn’t matter to the machine spitting out the letters, but it would matter if we were trying to match the letters. No, let’s think about it like this: are we counting every possible sequence of letters? Yes! So these are permutations, and the number of outcomes is \(P(26,3)\text{.}\)
Another deceptive use of order appears when counting bit strings. Recall that a \(n\)-bit string of weight \(k\) is a string of \(n\) bits (0s and 1s) in which \(k\) of the bits are 1s. For example, the 4-bit strings of weight 2 are
\begin{equation*}
1100, ~~ 1010, ~~ 1001, ~~ 0110, ~~ 0101, ~~ 0011\text{.}
\end{equation*}
Does order matter for bit strings? Of course it does! It is the only thing that matters. All of the strings above contain exactly the same number of 0s and 1s, they are only distinguished by the order of the bits.
And yet, the number of \(n\)-bit strings of weight \(k\) is \(\binom{n}{k}\) and NOT a permutation. What is going on here?
Nothing is broken, we are just not thinking about the right objects about which to consider the order. When we choose \(k\) out of \(n\) things for a bit string, it is the positions we are choosing (to fill with 1s, say). It does not matter what order we choose those positions in, just what set of positions we choose. That is, the bit string 1001 is the result of choosing positions 1 and 4 to put 1s into. If we chose positions 4 and then 1, we would get the same bit string.
To summarize, the question of whether order matters can lead us astray when deciding between a combination and a permutation. Instead, we should whether the outcomes we are counting are sets or sequences. If we are counting sets, think combination. If we are counting sequences, think permutation.