Mathematics.

counting

Permutations

Combinatorics25 minDifficulty3 out of 10

You should know: counting principles

Overview

A permutation is an arrangement of objects where order matters. The number of ways to arrange n distinct objects in a sequence is n! (n factorial), and the number of ways to arrange r of them out of n is denoted P(n,r) or ₙPᵣ. Permutations are the 'order matters' counterpart to combinations.

Intuition

Think of arranging 3 books (A, B, C) on a shelf. ABC and BAC use the same books but are different arrangements — order matters, so they're counted separately. There are 3! = 6 total arrangements. If you're only choosing 2 of the 3 books to place in a row, order still matters (AB ≠ BA), giving P(3,2) = 6 arrangements as well.

Formal Definition

Definition

The number of ways to arrange r objects chosen from n distinct objects, where order matters:

P(n,r)=n!(n−r)!P(n, r) = \frac{n!}{(n-r)!}
Definition
P(n,n)=n!P(n, n) = n!

Arranging all n objects

Notation

NotationMeaning
P(n,r)=nPrP(n,r) = {}_nP_rNumber of ordered arrangements of r objects from n
n!=n(n−1)(n−2)⋯1n! = n(n-1)(n-2)\cdots 1n factorial, with 0! defined as 1

Properties

Factorial growth

n!=n⋅(n−1)!n! = n \cdot (n-1)!

Example: 5! = 5 \cdot 4! = 120

Permutations with repetition

Arrangements of a multiset with repeats n1,…,nk=n!n1!n2!⋯nk!\text{Arrangements of a multiset with repeats } n_1,\ldots,n_k = \frac{n!}{n_1! n_2! \cdots n_k!}

Applications

Permutations underlie algorithm analysis for sorting, cryptographic key spaces, and password strength estimates.

Worked Examples

  1. All 4 are arranged, so use 4!.

    4!=4⋅3⋅2⋅1=244! = 4\cdot3\cdot2\cdot1 = 24

Answer: 24

Practice Problems

Difficulty 3/10

How many distinct arrangements are there of the letters in 'BOOK'?

Difficulty 4/10

In a race with 8 runners, how many different ways can the gold, silver, and bronze medals be awarded?

Difficulty 5/10

A project manager must order 6 distinct tasks into a sequence (no two at once). How many possible schedules exist?

Common Mistakes

Common Mistake

Confusing permutations with combinations.

Permutations count ORDERED arrangements (AB ≠ BA); combinations count unordered selections (AB = BA). Use P(n,r) when order matters, C(n,r) when it doesn't.

Quiz

Permutations differ from combinations because in permutations:
The number of ways to arrange all n distinct objects in a row is:
For the word 'BOOK', why is the count 4!/2! rather than 4!?

Summary

  • A permutation is an arrangement of objects where order matters.
  • P(n,r) = n!/(n-r)! counts arrangements of r objects chosen from n.
  • P(n,n) = n! arranges all n objects.
  • Repeated elements reduce the count by dividing by the factorial of each repeat count.

References

  1. WebsiteWikipedia — Permutation