Skip to content
Tutorials Center
My learning

Topics

Lesson 41 of 86 ยท Permutations, Combinations and Probability

Counting Principles and Permutations

Learn the addition and multiplication rules, factorials, arrangements and words with repeated letters, with worked examples and a runnable counter.

How many different four-digit PIN codes exist? How many ways can five runners finish a race? How many different words, meaningful or not, can you make from the letters of BANANA? These are counting problems, and they are far easier than they look once you know two simple rules and one idea: build the answer one decision at a time.

This lesson introduces the addition rule and the multiplication rule, the factorial, permutations (ordered arrangements), and words with repeated letters. The next lesson, Combinations, handles selections where order does not matter, and the one after it adds circular arrangements and restrictions. Counting also underlies Probability.

The multiplication rule

If a task has two steps, and the first can be done in m ways and the second in n ways (whichever way the first was done), then the whole task can be done in m ร— n ways. The rule extends to any number of steps.

Example. A meal has 3 starters, 4 mains and 2 desserts. One of each can be chosen in 3 ร— 4 ร— 2 = 24 ways.

Example. A licence plate has 2 letters followed by 3 digits. With letters and digits free to repeat, there are 26 ร— 26 ร— 10 ร— 10 ร— 10 = 676,000 plates.

Think of an invisible tree: each step multiplies the number of branches.

flowchart LR
    A["Start"] --> B["Step 1: 3 starters"]
    B --> C["Step 2: 4 mains"]
    C --> D["Step 3: 2 desserts"]
    D --> E["Total = 3 x 4 x 2 = 24"]

Independent steps multiply.

The addition rule

If a task can be done in one way or the other (never both at once), the numbers of ways add. If you can travel from town A to town B by 3 buses or 2 trains, there are 3 + 2 = 5 ways. The word AND (steps in sequence) signals multiplication; the word OR (alternatives) signals addition.

Example. How many three-digit numbers are divisible by 5? The last digit must be 0 or 5. For each choice the first digit has 9 options (1 to 9) and the middle digit has 10, so there are 9 ร— 10 ร— 2 = 180.

Factorials

The factorial of a positive integer n is the product of all whole numbers from 1 to n:

n! = n ร— (n โˆ’ 1) ร— ... ร— 2 ร— 1, and by convention 0! = 1.

The values to know: 1! = 1, 2! = 2, 3! = 6, 4! = 24, 5! = 120, 6! = 720, 7! = 5040, 8! = 40,320.

Factorials count arrangements of distinct objects in a line. For n different objects, there are n choices for the first place, n โˆ’ 1 for the second, and so on, giving n! arrangements. Five different books on a shelf can be ordered in 5! = 120 ways.

Permutations: arranging r of n objects

A permutation is an arrangement where order matters. The number of ways to arrange r objects chosen from n distinct objects is

nPr = n! / (n โˆ’ r)! = n ร— (n โˆ’ 1) ร— ... ร— (n โˆ’ r + 1) (r factors).

Examples:

  • 8 runners compete for gold, silver and bronze: 8P3 = 8 ร— 7 ร— 6 = 336.
  • Three-digit numbers from the digits 1 to 5 with no repeats: 5P3 = 5 ร— 4 ร— 3 = 60.
  • With repeats allowed: 5 ร— 5 ร— 5 = 125 (multiplication rule, no shrinking).

Note nPn = n! and nP1 = n. Order matters: ABC and CBA are different permutations.

Digit problems

Digit questions mix the rules above with a restriction: the first digit cannot be 0. Fill the restricted place first.

  • Four-digit numbers, no digit repeated, digits 0 to 9: first place 9 choices (not 0), then 9 (zero is allowed again but the first digit is used), then 8, then 7: 9 ร— 9 ร— 8 ร— 7 = 4536.
  • Even three-digit numbers from 1, 2, 3, 4, 5 without repeats: fill the units place first with 2 or 4 (2 ways), then 4 and 3 for the others: 2 ร— 4 ร— 3 = 24.

Whenever a place has a restriction, fill that place first. Filling the unrestricted places first can leave you unsure how many options remain.

Words with repeated letters

If some objects are identical, swapping them does not give a new arrangement, so we divide out the repeats. For n objects where one kind repeats p times, another q times, another r times:

Arrangements = n! / (p! ร— q! ร— r! ...)

  • LEVEL has 5 letters with L twice and E twice: 5! / (2! ร— 2!) = 120 / 4 = 30.
  • BANANA has 6 letters: A three times, N twice, B once: 6! / (3! ร— 2!) = 720 / 12 = 60.
  • MISSISSIPPI has 11 letters: I four times, S four times, P twice, M once: 11! / (4! ร— 4! ร— 2!) = 39,916,800 / 1152 = 34,650.
flowchart TB
    A["Word with n letters"] --> B["Count how often each letter repeats"]
    B --> C["Total arrangements = n!"]
    C --> D["Divide by p! for every repeated letter"]
    D --> E["Distinct arrangements"]

Divide the full factorial by the factorial of every repeat count.

Many questions add a condition. For example, how many arrangements of BANANA start with B? Fix B in front, then arrange ANANA: 5! / (3! ร— 2!) = 10.

When is it a permutation?

Use these clues:

  • Order matters (ranks, passwords, seats in a row, forming numbers or words): permutation.
  • Order does not matter (committees, hands of cards, choosing a team): combination, in the next lesson.

If you are unsure, test with a tiny case. Two people from three (A, B, C): as a ranking, AB differs from BA, so there are 6 outcomes; as a team, AB and BA are the same, so there are 3.

A counting toolkit

The script below computes factorials with exact big integers, nPr, and the arrangements of any word with repeats. It then verifies the formula for small words by generating every arrangement and counting the distinct ones.

JS Permutation and word counter

Press Run (or Ctrl + Enter) to see the console output here.

No output.

For a second check, count the even numbers formed from the digits 1 to 5, with and without repeats, by trying every possible number.

JS Count numbers from given digits

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A licence plate has 2 letters followed by 3 digits, and repetition is allowed. How many plates are possible?

    26 x 26 x 10 x 10 x 10 = 676 x 1000 = 676,000.
  2. 2. In how many ways can 8 runners fill the gold, silver and bronze positions?

    8P3 = 8 x 7 x 6 = 336. Order matters, because gold and bronze are different.
  3. 3. How many distinct arrangements are there of the letters of the word LEVEL?

    5 letters with L twice and E twice: 5! / (2! x 2!) = 120 / 4 = 30.
  4. 4. How many four-digit numbers have all four digits different?

    The first digit cannot be 0: 9 choices. Then 9, 8, 7 choices remain: 9 x 9 x 8 x 7 = 4536.
  5. 5. How many even numbers can be formed from the digits 1, 2, 3, 4, 5 using each digit at most once in a 3-digit number?

    The units digit is 2 or 4 (2 ways), then 4 choices and 3 choices for the others: 2 x 4 x 3 = 24.

Summary

  • Steps in sequence (AND) multiply; alternatives (OR) add.
  • n! counts arrangements of n distinct objects, with 0! = 1.
  • nPr = n! / (n - r)! counts ordered selections of r from n.
  • For restricted places (such as a non-zero first digit), fill the restricted place first.
  • For repeated letters, divide n! by the factorial of each repeat count.
  • If order matters, use permutations; if it does not, use combinations.

Next: Combinations, where order stops mattering.