Skip to content
Tutorials Center
My learning

Topics

Lesson 9 of 36 ยท Permutations and Combinations

Permutations and Factorials

Count the ways to arrange n distinct objects in order: n factorial. Learn why factorials grow so fast, how to generate permutations, and how to handle restrictions.

A permutation is an arrangement of objects in a definite order. The three letters A, B, C can be arranged as ABC, ACB, BAC, BCA, CAB and CBA: six permutations. Whenever the question has the flavour "in how many orders can these things line up", you are counting permutations.

The factorial formula

To arrange n distinct objects in a row, fill the positions one by one. The first position has n choices, the second n - 1 (one object is used), the third n - 2, and so on until the last position, which has 1 choice. By the product rule:

n! = n ยท (n-1) ยท (n-2) ยท ... ยท 2 ยท 1

We read n! as "n factorial". By convention 0! = 1: there is exactly one way to arrange nothing (the empty arrangement). This convention keeps later formulas consistent.

Python Factorials and generated permutations

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

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Why factorials explode

Factorial growth is faster than any exponential. The table shows how quickly arrangement counts become unmanageable.

n n!
5 120
10 3,628,800
15 1,307,674,368,000
20 2,432,902,008,176,640,000
52 about 8 x 10^67 (a shuffled deck)

This is why trying all orders (for example, all routes of a travelling salesperson visiting 20 cities) is infeasible. A deck of 52 cards has so many orders that every well-shuffled deck is almost surely in an arrangement that has never occurred before in history.

Python How big are factorials?

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

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Restrictions

Many problems say that some objects must stay together, or apart, or occupy fixed positions.

Two people must sit together. Glue them into one block. With 5 people, you now arrange 4 units (the block plus 3 others): 4! ways. Inside the block the two can swap: times 2. Answer: 4! x 2 = 48.

Two people must not sit together. Use the complement: all arrangements minus those where they are together. 5! - 48 = 120 - 48 = 72.

One person must be first. Fix that person; arrange the other 4: 4! = 24.

Python Together and apart

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

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Generating permutations yourself

itertools.permutations is convenient, but writing a recursive generator makes the factorial structure visible: pick any element to go first, then permute the rest.

Python Recursive permutation generator

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

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

flowchart TD
    R["Arrange A, B, C"] --> A["A first"]
    R --> B["B first"]
    R --> C["C first"]
    A --> A1["ABC, ACB"]
    B --> B1["BAC, BCA"]
    C --> C1["CAB, CBA"]

3 choices for the first slot, each leaving 2! arrangements of the rest.

Ordering by rank also exists: the lexicographic order lists permutations as a dictionary would. Algorithms such as next_permutation step from one to the next, and you will meet them in the applications chapter.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In how many ways can 6 different books be placed on a shelf?

    6! = 720.
  2. 2. What is 0! by convention?

    There is exactly one arrangement of nothing, so 0! = 1.
  3. 3. Four people sit in a row; two of them insist on sitting together. How many arrangements?

    Glue the pair: 3! = 6 arrangements of 3 units, times 2 orders inside the block = 12.
  4. 4. How many ways can 5 people line up if two specific people must NOT be adjacent?

    Total 120 minus adjacent 48 equals 72.

Summary

  • n distinct objects can be arranged in n! ways; 0! = 1.
  • Factorials grow faster than exponentials, so brute force is hopeless beyond roughly n = 10.
  • Handle "together" by gluing, and "apart" by complement.
  • A recursive generator mirrors the product rule: choose the first item, permute the rest.

Next: Partial Permutations and Circular Arrangements