Math Vale

🎲 Probability Marsh · Probability

Counting Principles

Count arrangements and selections without listing them, using the multiplication principle, factorials, permutations and combinations.

In short

  • Choices made in stages multiply; you add only when you are picking one thing in total, not one from each stage.
  • n! counts the arrangements of n distinct objects, because the number of choices drops by one at every position.
  • Order matters means a permutation (nPr); order does not means a combination (nCr = nPr / r!), which is always the smaller.
  • Repetition allowed gives nr; repetition forbidden makes the count fall away, which is what nPr and n! do.

The fundamental counting principle

If a choice comes in stages, and every stage has the same options whatever you picked before, then the number of ways to get through all of them is the product of the stage counts.

3 cloaks and 4 lanterns give 3 x 4 = 12 outfits. Add 5 routes and it is 3 x 4 x 5 = 60.

The reason is a tree. Each of the 3 cloaks grows 4 branches, one per lantern, so there are 3 lots of 4 branches. Multiplication is what "so many lots of" means.

The instinct to add is strong and almost always wrong here. Adding answers a different question — "how many items are there to choose from" — while multiplying answers "how many complete outfits can be made". Ask yourself whether you are picking one thing in total or one thing from each stage.

Factorials: arranging everything

To put n different objects in a row, fill the positions one at a time. The first position has n candidates. Once it is filled only n - 1 remain for the second, then n - 2, and so on down to 1.

n! = n x (n - 1) x (n - 2) x ... x 2 x 1

So 5 banners can be arranged in 5! = 120 orders, and 8 in 8! = 40320. Factorials grow ferociously; that growth is the whole reason we count arrangements with a formula rather than a list.

The number drops at every step because each object can only be used once. Writing 5 x 5 x 5 x 5 x 5 instead would be counting as if you could reuse a banner you had already hung.

When some of the objects are identical, arrangements that only swap them are the same arrangement, so each has been counted more than once. Divide by the factorial of each repeat: REEDS has 5 letters with two Es, so it has 5!/2! = 60 distinguishable arrangements, not 120.

Permutations and combinations

Often you take only some of the objects. Then everything hangs on one question: does order matter?

If it does — gold, silver and bronze ribbons are not interchangeable — you want a permutation:

nPr = n x (n - 1) x ... x (n - r + 1), that is r factors counting down from n.

8 rowers taking 3 ribbons: 8P3 = 8 x 7 x 6 = 336.

If it does not — a team where everyone does the same job — you want a combination. Count the ordered picks first, then divide out the orders you did not want to distinguish:

nCr = nPr / r!

8 rowers forming a team of 3: 336 / 3! = 336 / 6 = 56.

A combination is always the smaller number, and the ratio between them is exactly r!.

With repetition, or without

The second question to ask is whether an object can be used twice.

A lock with 4 dials, each carrying 8 symbols, allows repeats: every press still has all 8 symbols available, so there are 84 = 4096 codes.

A lock that requires 4 *different* symbols out of 8 does not: the choices fall away, 8 x 7 x 6 x 5 = 1680 codes.

Put the two questions together and every counting problem in this skill falls into one of four boxes:

  • order matters, repeats allowed: nr
  • order matters, no repeats: nPr
  • order does not matter, no repeats: nCr
  • all objects used, some identical: n! divided by the factorial of each repeat

Answer the two questions in words before you reach for a formula, and the formula chooses itself.

Worked examples

Example 1

A guild of 9 must send 4 delegates. All four do the same job. How many different delegations are possible?

  1. Ask whether order matters. All four do the same job, so choosing Ines then Kofi is the same delegation as Kofi then Ines — order does not matter.
  2. Ask whether repeats are possible. Nobody can be sent twice, so they are not. That is a combination.
  3. Count the ordered picks first: 9P4 = 9 x 8 x 7 x 6 = 3024.
  4. Each delegation of 4 was counted once for every order its members could be listed in, and that is 4! = 24 orders.
  5. 9C4 = 3024 / 24 = 126 delegations.

Example 2

A signal is made by hanging 3 of the 6 available pennants on a mast, top to bottom, with no pennant used twice. How many signals are there?

  1. Order matters here: the same three pennants in a different order is a different signal.
  2. Repeats are not allowed, so the number of choices falls at each position.
  3. Top position: 6 pennants. Middle: 5 remain. Bottom: 4 remain.
  4. 6 x 5 x 4 = 120 signals.
  5. Compare: if repeats were allowed it would be 6 x 6 x 6 = 216, and if order did not matter it would be 120 / 3! = 20. Same three numbers, three different answers.

Practice problems, with solutions

Three problems of increasing difficulty, each with the full working. In the game these are generated fresh every time; these three are fixed so this page always shows the same ones.

Problem 1

Difficulty 1 of 5

The Coin Ferry outfitter offers 2 cloaks and 4 hot drinks. Jonas picks exactly one of each. How many different combinations are possible?

Answer: 8

  1. Stages: 2 cloaks; 4 hot drinks.
  2. Every choice at one stage can be paired with every choice at the next, so the counts multiply.
  3. 2 x 4 = 8
  4. So there are 8 different combinations.

Problem 2

Difficulty 3 of 5

Freya lines up 6 different runes in a row on the ferry rail. How many different orders are possible?

Answer: 720

  1. Position by position the choices are 6, 5, 4, 3, 2, 1.
  2. Total orders = 6 x 5 x 4 x 3 x 2 x 1 = 6!
  3. 6! = 720

Problem 3

Difficulty 4 of 5

8 ferry rowers race, and the first 4 finishers take the gold, silver, bronze, copper ribbons. How many different ways can those ribbons be handed out? (No ties.)

Answer: 1680

  1. Order matters, so this is 8P4.
  2. 8P4 = 8 x 7 x 6 x 5
  3. = 1,680

Common mistakes

  • Adding the stage counts instead of multiplying them, so 3 cloaks and 4 lanterns give 7 rather than 12.
  • Using nr where each object may only be used once, which counts codes that reuse a symbol.
  • Answering with a permutation when order does not matter, counting the same team once for every order of its members.
  • Forgetting to divide by the factorial of a repeated letter, so REEDS gets 120 arrangements instead of 60.
  • Multiplying n by r and hoping, which happens to agree with nCr in one or two small cases and nowhere else.

What you should be able to do

  • Apply the fundamental counting principle to a multi-stage choice.
  • Use factorials to count the arrangements of a set of distinct objects.
  • Choose between a permutation and a combination by asking whether order matters.
  • Count arrangements with and without repetition and tell the two apart.

Where this fits in the curriculum

Common Core

  • HSS-CP.B.9

    High school — Use permutations and combinations to compute probabilities of compound events and solve problems.

    The Common Core files permutations and combinations under probability rather than giving counting a home of its own; the counting techniques themselves are the content of this skill.

Learn these first

This leads on to