Permutations and Combinations: An Introduction

We have seen a number of questions recently about combinatorics: the study of methods for counting possibilities. These topics are studied at all levels of mathematical education, from elementary (where they might just be called counting) to high school (where they are often learned along with probability) to college (where they are part of “discrete math”). As a result, there is no one category to put it into without turning away suitable readers. I want to explore various aspects of this field over the next week or two.

I want to start with some questions about the basics, developing the concepts of permutation and combination, and seeing where the formulas for them come from. Then we’ll go beyond mere formulas, looking into some challenging problems and helpful ways of thinking.

The multiplication principle

We can begin with what is sometimes called the Fundamental Principle of Counting: When we have a series of choices, with m ways to make the first choice, n ways to make the second choice, and so on, the total number of ways to make all the choices is the product of those numbers. Here is a question about that, from 1999:

Gift Wrap Combinations

This is the problem. I think I should add but my mom said to multiply. 
My answer is 5 and my mom's answer is 6.  Am I right or is my mom?

The problem:

Mary is wrapping a gift. She has 3 different colors of ribbon and 2 different colors of wrapping paper.  

How many many different ways can she wrap the gift?

Doctor Rick answered, first just showing what answer is correct by actually doing the counting, and in passing showing how a wrong interpretation of the question could result in the wrong answer:

Let's try it. Let's say Mary has:

red ribbon
green ribbon
yellow ribbon

striped paper
white paper

If she picks ONE of these 5 things to wrap the gift, she has 5 ways to do it. But that's not how we usually wrap gifts. (Once my brother built a greenhouse for my father, and he wrapped it with a huge ribbon but no wrapping paper.) Normally, though, we wrap it in paper AND a ribbon.

If Mary does it this way, she has these choices:

  striped paper, red ribbon
  striped paper, green ribbon
  striped paper, yellow ribbon
  white paper, red ribbon
  white paper, green ribbon
  white paper, yellow ribbon

Well, it looks like your mom is right. She has probably wrapped a lot of presents, so this was easy for her.

Note that if we take the question as an “or” (paper or ribbon), we would add; but it is intended as an “and” (paper and ribbon), and that makes us multiply. This shows up elsewhere in math, from probability to logic.

But why do you multiply? We can write the choices as a table, like this:

                PAPER:
                striped  white
               +-------+-------+
RIBBON: red    |       |       |
               +-------+-------+
        green  |       |       |
               +-------+-------+
        yellow |       |       |
               +-------+-------+

Mary can put a check in any of the 6 boxes in the table, and that's her choice - the row shows which ribbon she picked, and the column shows which paper she picked. The number of boxes is 3 rows times 2 columns = 6 boxes. That's why you multiply.

In this kind of problem, there is a fixed number of choices at each step, so we multiply those numbers. Another common model is the tree of possibilities, branching at each decision to be made.

For more examples, see:

Examples of the Fundamental Counting Principle
Counting Answer Keys

Permutations of an entire set

Next, we’ll look at a different kind of question:

Explaining Permutation to Young Students

Question:  How many ways can we arrange 4 people A, B, C, D to sit in a different order?

Answer:  For the first seat, we have 4 choices, for the second seat, we have 3 choices, for the third seat, we have 2 choices, and for the last seat, 1 choice.  Therefore, the answer is 4 x 3 x 2 x 1 = 24.

My kid wants to know why it's not 4 + 3 + 2 + 1 = 10.  I'm having a hard time explaining this to him.

It’s easy to see why the given explanation would convey the wrong idea to a child: 4 choices, and 3 more, and another 2, and 1 more, adds up to 10. Where does multiplication come in?

I replied:

I like to add a few extra words in the explanation.  As you stated the answer (which is the way it's commonly done), it does sound as if you would just add the numbers.

Here's how I say it:

You have 4 ways to choose a person for the first seat. Then, FOR EACH of those 4 choices, there are 3 ways to choose a person for the second seat. Then FOR EACH of the 12 choices you've made so far, you have 2 ways to choose the person to sit in the third seat, making a total of 24 ways to choose. The last seat leaves us no choice, since there is only 1 person left to pick.

The “for each” part is essential, in my mind. We don’t just have 4 choices, then another 3, and so on; rather for each of the 4, there are 3 of the next, and so on. And “for each” is what multiplication is all about.

But beyond mere words, the best way to learn anything at the beginning is a concrete model:

If we try actually making a list of the possible orders, we can watch this happening. After filling the first seat, we have these 4 possible orders:

  A _ _ _

  B _ _ _

  C _ _ _

  D _ _ _

Then for each case, we have three ways to fill in the second seat:

  A B _ _    A C _ _    A D _ _

  B A _ _    B C _ _    B D _ _

  C A _ _    C B _ _    C D _ _

  D A _ _    D B _ _    D C _ _

Then, for each of those 24 choices, we still have two ways to fill in the third seat:

  A B C _    A C B _    A D B _
  A B D _    A C D _    A D C _

  B A C _    B C A _    B D A _
  B A D _    B C D _    B D C _

  C A B _    C B A _    C D A _
  C A D _    C B D _    C D B _

  D A B _    D B A _    D C A _
  D A C _    D B C _    D C B _

The last seat fills itself:

  A B C D    A C B D    A D B C
  A B D C    A C D B    A D C B

  B A C D    B C A D    B D A C
  B A D C    B C D A    B D C A

  C A B D    C B A D    C D A B
  C A D B    C B D A    C D B A

  D A B C    D B A C    D C A B
  D A C B    D B C A    D C B A

So there are the 24 ways to seat the four people, which we found by making 4 times 3 times 2 times 1 choices.

For larger problems, of course, we don’t make actual lists; combinatorics is essentially all about finding ways to count without having to count one by one, because answers in this field are often to large to even imagine. But thinking about how we might count something, and thinking about the patterns involved, can often be a good start in solving these problems.

I didn’t use the word, but that problem was about permutations: all the ways to list elements of a set in order, in this case all the elements of the set {A, B, C, D}. What if you have to include only some subset of the elements in each list?

The answer here has a special form (starting from a number and counting down to 1, and using those as factors), which will be needed over and over, so it has been given a special name and notation: \(n!\), which is read as “n factorial”. You can read about the origin of this notation (and a negative opinion of it) here:

Origin of the Factorial Symbol !

Permutations of part of a set

This question came in 1998:

Marathon Prizes

Ten runners are competing in a marathon. In how many ways can the first and second prizes be awarded? 

Also, There are 7 possible commercials to be used in 3 time slots. How many possible arrangements are there?

These problems are both about listing some of the given items (runners or commercials) in a specific order (prizes, time slots). Doctor Anthony answered this:

There are 10 ways that the first prize could be awarded, and now with 9 to choose from, there are 9 ways that the second prize could be awarded. So the total number of ways that the two prizes could be awarded is 

               10 x 9 = 90 ways.

I often think of this sort of problem in terms of filling in blanks. We have two blanks (whose order matters), representing first prize and second prize: __  __. There are 10 ways to fill in the first (any of the runners), and then (since one runner already has a place) there are 9 ways to fill in the second. Again, this is a “for each” situation, so we multiply.

For the second question we must choose 3 from the 7 to go into the time slots.

We could choose the first in 7 ways, then the second in 6 ways and finally the third in 5 ways. This would give 7 x 6 x 5 = 210 ways.  However the order in this question does not matter, and for any group of 3 commercials, we could rearrange them amongst themselves in 3 x 2 x 1 = 6 ways. So the group of 3 commercials could be chosen in 210/6  = 35 ways.

Here I would make 3 blanks, __  __  __, and see that we can fill them in in 7, 6, and 5 ways, respectively. This makes 210 ways to fill in the time slots, so that is the answer to the question as asked, which is about permutations (of 7 items taken 3 at a time, as we say). But if, as Doctor Anthony interprets it, we only care about which commercials are aired, not when, then we can divide by the number of ways in which the blanks could be rearranged. This is called combinations.

Doctor Anthony continues, leading to formulas for both concepts:

In the first question we were dealing with permutations where the order matters, while in the second question we were dealing with combinations where order does not matter.

There are formulae that can be used in each situation.  

nPr is the number of permutations of r things that can be made from n different things. 10 P 2 = 10 x 9 = 90 = answer to first question.

nCr is number of combinations of r things that can be made from n different things

               7 x 6 x 5      210
      7 C 3 =  ---------   = -----  = 35  = answer to second question.
               1 x 2 x 3       6

The notation is a little awkward to type out. The proper forms are \(_nP_r\) for permutations, and \(_nC_r\) for combinations. The latter is also commonly denoted by \({n\choose r}\). Often, in typing, we use function notation to make it easier, \(P(n,r)\) and \(C(n,r)\).

For other explanations of permutations (mostly of the full-set variety), see:

Possible Letter Arrangements
What Is N Factorial Used For?
The Three Little Pigs Arrange Their Houses
Introduction to Permutations by Standing in Line
Counting Arrangements of Objects in a Set

Combinations

How can we make usable formulas for permutations and combinations? This is from 2001:

Calculating Permutations

I don't understand how the formula for calculating the total possible number of ways to choose r objects out of a total n objects works. I know the formula is 

         n!
C  = -----------
      r! (n-r)!

(Andrew used “Permutations” as his subject line, and used P for his formula, but he is really asking about combinations. Doctor Greenie quietly changed terminology in his answer, but the site editor failed to fix this. I’ve made appropriate fixes here, but couldn’t change the page name.)

Hi, Andrew -

It is admirable that you are concerned with understanding why the formula works. I hope you are able to keep up your interest in the "why" as well as the "how" - you will get much more enjoyment out of mathematics if you can do that.

I'm going to use the notation C(m,n) for "m choose n."  Then the formula for C(m,n) is

                  m!
    C(m,n) = -----------
              n! (m-n)!

This is just a convenient way to write the general expression. If you think of a specific numerical example, the numerical value of the expression becomes more clear, and the "why" behind the formula becomes apparent.

The notation \(_nC_r\) is often read as “n choose r“, short for “the number of ways to choose r out of n items”. Often we can best understand a symbolic formula by first thinking about it more concretely, with particular numbers, so suppose we want to choose 3 items from a set of 8:

Let's look at a specific example: C(8,3).

First, let's see what happens to the formula when we put these specific numbers in.

                8!        8*7*6*5*4*3*2*1       8*7*6
    C(8,3) = ------- = --------------------- = -------
              3! 5!     (3*2*1) (5*4*3*2*1)     3*2*1

One nice thing about C(m,n) is that when you actually calculate a value for a particular m and n, whole groups of the factors in the numerator and denominator always cancel, as did the factors (5*4*3*2*1) in this case.

This is an interesting fact: the result of the formula has to be a number of choices, so it has to be a whole number (in this case, 42), even though it looks like a big fraction that ought to have an ugly result. Big chunks will always magically cancel, because they have to!

But don’t miss what’s happened here: the fraction on the right looks just like Doctor Anthony’s form above, consisting of the same number of factors on the top and the bottom, the top starting at 8 (our m), and the bottom ending at 1. The notation of the formula, using factorials, might have been invented by starting with the form on the right and realizing that if we multiply the top and bottom by 5!, the top becomes 8! and makes a nicer looking formula.

Now let's think about the physical meaning of C(8,3). I have a group of eight objects and I'm going to choose three of them. How many ways can I do it? (The answer had better turn out to be the expression above!)

Let's first think about how many different ways I can choose three of the eight objects if order is important. I can choose any of the eight first. Then, for each of those eight choices, there would be seven choices for my second selection. That makes a total of 8*7 choices for the first two out of eight. Then, for each of those 8*7 choices for the first two, there would be six choices for the third. That makes a total of 8*7*6 different ordered ways in which I can pick three of the eight objects.

This gives us our numerator, a product of three descending factors starting at 8.

This is the number of permutations of 8 items, taken 3 at a time. The formula for this is, in general, $$_mP_n = \underset{n factors}{\underbrace{m(m-1)\cdots (m-n+1)}} = \frac{m!}{(m-n)!}.$$

But mathematically "choose" has the meaning that order is not important (we are choosing a committee of 3 - not a president, vice president and secretary). So the list of 8*7*6 different orders contains each combination of 3 of the 8 objects several times, in different orders. How many times does each group of 3 occur in that list?  Well, any one of the three could have been chosen first. For each of those three choices, there are two choices for which one could have been chosen second, giving 3*2 ways to choose the first two of the three. For each of those 3*2 choices for the first two there would be only one choice left, for a total of 3*2*1 ways for choosing each particular group of three.

So, as we’ve seen before, the blanks themselves can be permuted in 6 ways.

So our list of 8*7*6 ordered ways for choosing three objects from a group of eight includes each particular group of three objects 3*2*1 times - so the number of ways of choosing three objects from eight is

    8*7*6
    -----
    3*2*1

So the formula for C(8,3) simplifies to

    8*7*6
    -----
    3*2*1

And in this expression, the "8*7*6" is the number of ordered ways I can pick three out of eight; while the "3*2*1" is the number of different orders in which any of those groups of three out of eight could have been chosen.

This, rather than the formal version with factorials, is the most useful way to think about it, as Doctor Greenie explains:

Whenever I am doing any work where I use C(m,n) frequently, I find that I don't think of the formula as it is formally defined. For example, if I run into the need for C(8,3), I don't think of

                8!        8*7*6*5*4*3*2*1       8*7*6
    C(8,3) = ------- = --------------------- = -------
              3! 5!     (3*2*1) (5*4*3*2*1)     3*2*1

Instead, I think as follows:

             3 decreasing factors, starting with 8    8*7*6
    C(8,3) = ------------------------------------- = -------
             3 decreasing factors, starting with 3    3*2*1

This way of remembering C(8,3) works better for me; it also gives a better picture of the meaning of the formula. You could do the same thing with C(m,n):

           n decreasing factors, starting with m    m(m-1)...(m-n+1)
  C(m,n) = ------------------------------------- = ------------------
           n decreasing factors, starting with n   n(n-1)...(3)(2)(1)

However, the standard form for the definition of C(m,n) is more compact.

Put into factorial form, this formula is what Andrew asked about: $$_mC_n = \frac{\underset{n factors}{\underbrace{m(m-1)\cdots (m-n+1)}}}{\underset{n factors}{\underbrace{n(n-1)\cdots (1)}}} = \frac{m!}{n! (m-n)!}.$$

For more on combinations, see:

Choosing 3 of 6 Colors
Choose Three People from Five

For another explanation of both formulas, see

Permutations and Combinations: Deriving Formulae

Leave a Comment

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.