Discrete Mathematics: Permutations

What is a Permutation?

A permutation is an arrangement of objects in a specific order. Unlike combinations, the order of selection matters in permutations.

For example, arranging the letters A, B, C gives different permutations depending on their order: ABC, ACB, BAC, BCA, CAB, CBA — a total of 6 arrangements.

Permutations are used when the sequence or arrangement of items is important.

The Permutation Formula

The number of ways to arrange \(r\) objects chosen from \(n\) distinct objects is given by:

\[P(n, r) = \frac{n!}{(n - r)!}\]

Where:

\(n\) = total number of distinct objects
\(r\) = number of objects selected and arranged
\(n!\) = \(n\) factorial \(= n \times (n-1) \times (n-2) \times \cdots \times 1\)

Special case: When all \(n\) objects are arranged \((r = n)\):

\[P(n, n) = n!\]

Factorial Notation

The factorial of a non-negative integer \(n\), written \(n!\), is the product of all positive integers from 1 to \(n\).

Expression	Expansion	Value
\(0!\)	Defined as 1	1
\(1!\)	\(1\)	1
\(2!\)	\(2 \times 1\)	2
\(3!\)	\(3 \times 2 \times 1\)	6
\(4!\)	\(4 \times 3 \times 2 \times 1\)	24
\(5!\)	\(5 \times 4 \times 3 \times 2 \times 1\)	120

Worked Examples

Example 1: Arranging All Items

How many ways can 4 books be arranged on a shelf?

Here \(n = 4\) and \(r = 4\):

\[P(4,4) = 4! = 4 \times 3 \times 2 \times 1 = \mathbf{24}\]

Example 2: Selecting and Arranging a Subset

How many ways can 3 students be chosen from a group of 7 and seated in a row?

Here \(n = 7\) and \(r = 3\):

\[P(7,3) = \frac{7!}{(7-3)!} = \frac{7!}{4!} = 7 \times 6 \times 5 = \mathbf{210}\]

Example 3: Arranging Letters

How many different 2-letter arrangements can be made from the letters in the word MATH?

Here \(n = 4\) and \(r = 2\):

\[P(4,2) = \frac{4!}{(4-2)!} = \frac{4!}{2!} = 4 \times 3 = \mathbf{12}\]

Common Permutation Notation

Notation	Meaning
\(P(n, r)\)	Permutations of \(n\) objects taken \(r\) at a time
\({}^nP_r\)	Alternate notation for \(P(n,r)\)
\(n!\)	\(n\) factorial: product of all integers from 1 to \(n\)
\(0!\)	Equals 1 by definition
\(P(n,n)\)	Number of ways to arrange all \(n\) objects \(= n!\)

Permutations vs. Combinations

A key distinction in counting problems is whether order matters:

Feature	Permutation	Combination
Order matters?	Yes	No
Formula	\(\dfrac{n!}{(n-r)!}\)	\(\dfrac{n!}{r!(n-r)!}\)
Example	Arranging runners in 1st, 2nd, 3rd place	Choosing 3 toppings for a pizza
\(P(4,2)\) vs \(C(4,2)\)	12	6

Practice Problems

Problem 1:
How many ways can 5 people be arranged in a line?

\(P(5,5) = 5! = 120\) ways.

Problem 2:
Find \(P(6, 2)\).

\(P(6,2) = \dfrac{6!}{(6-2)!} = \dfrac{6!}{4!} = 6 \times 5 = 30\)

Problem 3:
How many 3-letter arrangements can be formed from the letters A, B, C, D, E (no repetition)?

\(P(5,3) = \dfrac{5!}{2!} = 5 \times 4 \times 3 = 60\) arrangements.

Problem 4:
In how many ways can a president, vice president, and treasurer be elected from a club of 10 members?

\(P(10,3) = \dfrac{10!}{7!} = 10 \times 9 \times 8 = 720\) ways.

Problem 5:
How many distinct arrangements are there of the words in the phrase Lights Camera Action?

\(P(3,3) = 3! = 6\) arrangements: Lights Camera Action , Lights Action Camera , Action Lights Camera, Action Camera Lights, Camera Action Lights, Camera Lights Action.

Challenge Problems

A race has 8 runners. How many ways can gold, silver, and bronze medals be awarded?
How many 4-digit PINs can be formed from the digits 1–9 if no digit is repeated?
Evaluate: \(\dfrac{P(8,3)}{P(4,2)}\)
Is \(P(n,0) = 1\) for all \(n \geq 0\)? Explain using the formula.
A bookshelf holds 6 different books. How many ways can all 6 be arranged if a specific book must always be placed first?