Permutations

The idea: same items, different order ⇒ different outcome

A permutation is an ordered arrangement of items. The central question permutations answer is:

How many outcomes are there when the positions matter?

You already know the multiplication rule: if you make a sequence of choices and each step has a certain number of options, you multiply those counts.

Permutations are what you get when those choices are:

• •Without replacement (you don’t reuse items), and
• •Order-sensitive (different orders count as different outcomes).

Why “order matters” is a big deal

Consider the two-letter sequence made from {A, B, C} without repeats.

• •AB and BA use the same letters.
• •But they are different sequences.
• •So they must be counted separately.

That is the signature of permutations.

Three common “permutation contexts”

1. 1)Ranking / podiums: 1st, 2nd, 3rd are different positions.
2. 2)Seating in labeled seats: seat #1 vs seat #2 are different.
3. 3)Codes / strings (without repetition): first character vs second character are different.

Vocabulary you’ll see

• •Full permutation: arrange all n distinct items.
• •k-permutation: choose and arrange k distinct items from n (no repeats).

We’ll build both from the same counting principle: multiply the number of choices available at each position.

Notation

• •Factorial: n! = 1 · 2 · 3 · … · n (with 0! = 1 by convention).
• •Permutation operator: n P k (also written P(n, k)) counts ordered selections of length k from n without replacement.

We’ll derive the formulas rather than memorizing them.

Why factorials appear

Suppose you have n distinct items and you want to arrange all of them in a line.

Think in positions:

• •Position 1: n choices
• •Position 2: n − 1 choices (one item is used)
• •Position 3: n − 2 choices
• •…
• •Position n: 1 choice

By the multiplication rule, the total number of arrangements is:

n · (n − 1) · (n − 2) · … · 2 · 1

That product is called n factorial, written n!.

Definition

For integer n ≥ 1:

n! = ∏ᵢ₌₁ⁿ i = 1 · 2 · 3 · … · n

And by convention:

0! = 1

Why 0! = 1 (intuition, not just a rule)

A “full permutation of 0 items” means: how many ways to arrange nothing? There is exactly one empty arrangement.

Also, the recursion for factorials works cleanly:

n! = n · (n − 1)!

If we set n = 1:

1! = 1 · 0!

But 1! = 1, so 0! must be 1.

Small examples (build intuition)

• •3! = 3 · 2 · 1 = 6

The 6 arrangements of (A, B, C) are:

ABC, ACB, BAC, BCA, CAB, CBA.

• •4! = 24

This already grows fast; factorial growth is one reason permutation counts get large quickly.

A useful pattern: factorial cancellation

Factorials often simplify when you divide them:

\( \frac{n!}{(n−1)!} \)

Work it out by expansion:

n! = n · (n − 1) · (n − 2) · … · 1

(n − 1)! = (n − 1) · (n − 2) · … · 1

So:

n! / (n − 1)! = n

This “cancellation idea” is the backbone of the n P k formula you’ll meet next.

When to use n!

Use n! when:

• •You arrange all n distinct items.
• •Every position is part of the outcome.
• •Items are not repeated.

If you’re not using all items (only k of them), you need k-permutations instead.

The question k-permutations answer

How many ordered sequences of length k can you form from n distinct items, without replacement?

Example contexts:

• •Gold/silver/bronze chosen from n runners (k = 3)
• •A 4-character code from n symbols without repeats (k = 4)
• •Choosing a president, vice president, and treasurer from n people (k = 3)

Build it from the multiplication rule (the “why”)

Imagine filling k positions one by one.

• •Position 1: n choices
• •Position 2: n − 1 choices
• •Position 3: n − 2 choices
• •…
• •Position k: n − (k − 1) choices

Multiply them:

n P k = n · (n − 1) · (n − 2) · … · (n − k + 1)

This is already a perfectly good formula.

Convert to factorial form (the “how”)

Factorials let us write that product compactly.

Start with n!:

n! = n · (n − 1) · (n − 2) · … · (n − k + 1) · (n − k) · (n − k − 1) · … · 2 · 1

Notice the part we want (the first k factors) is:

n · (n − 1) · … · (n − k + 1)

The “extra tail” we don’t want is:

(n − k) · (n − k − 1) · … · 1 = (n − k)!

So divide to cancel the tail:

n P k = \( \frac{n!}{(n − k)!} \)

Check with a concrete example

Suppose n = 5 and k = 3.

Direct product:

5 P 3 = 5 · 4 · 3 = 60

Factorial form:

5!/(5 − 3)! = 5!/2! = (120)/2 = 60

Matches.

Boundary cases and sanity checks

• •If k = n, then:

n P n = n!/(n − n)! = n!/0! = n!/1 = n!

So k-permutation generalizes full permutation.

• •If k = 0, then:

n P 0 = n!/(n − 0)! = n!/n! = 1

There is exactly one sequence of length 0: the empty sequence.

• •If k > n, then there are 0 ways (you can’t pick more distinct items than exist). In formula form, (n − k)! isn’t defined for negative integers in this counting context, so treat it as “not allowed.”

A decision table: permutations vs other counts

Use this to avoid the most common confusion.

Interpreting n P k as “pick then arrange”

Another way to see the structure:

• •First you select which k items you’ll use.
• •Then you arrange them.

That viewpoint leads naturally to combinations later:

n P k = (number of k-element sets) · (number of ways to order k items)

And “number of ways to order k items” is k!.

So you’ll soon see the relationship:

n P k = (n C k) · k!

Don’t worry about n C k yet—just remember: permutations count ordered outcomes; combinations will count unordered ones.

Turning words into n, k, and “order?”

Most permutation mistakes come from translating the story incorrectly. A reliable workflow:

1. 1)Identify positions: Are there labeled roles (1st/2nd/3rd, seat 1/2/3, President/Vice/etc.)?
2. 2)Check uniqueness: Can an item/person be used more than once?
3. 3)Extract n and k:

• •n = size of available pool
• •k = number of positions filled

4. 4)If no repeats and order matters → use n P k.

Example application types

1) Rankings and awards

If 10 runners compete and you award gold/silver/bronze, you’re filling 3 distinct ranks:

10 P 3 = 10 · 9 · 8

2) Assigning distinct roles

If you pick a chair, secretary, and treasurer from 12 people:

12 P 3

3) Seating in a row

If 7 people sit in a row of 7 seats:

7!

If only 4 of them sit (4 seats to fill) from 7 people:

7 P 4

A key conceptual bridge to combinations

Often the only difference between a permutation problem and a combination problem is whether we care about the order.

Take the same three winners from 10 runners:

• •If we only care which 3 runners win medals (no order): that’s a combinations question.
• •If we care who is gold vs silver vs bronze: that’s permutations.

The relationship:

n P k = (n C k) · k!

Interpretation:

• •n C k chooses the group.
• •k! orders the chosen group into k distinct positions.

Why permutations are foundational in discrete math and CS

Permutations aren’t just a counting trick.

• •In algorithms, a brute-force search over all arrangements is often “try all permutations,” which can mean n! possibilities—explaining why some problems become infeasible quickly.
• •In probability, many probabilities are “favorable permutations / total permutations.”
• •In data structures, sorting can be seen as transforming one permutation of items into another.

Quick growth intuition (why pacing matters)

Factorials explode:

So, whenever you see n! or n P k, it’s worth pausing to ask: is the model correct? Are repeats allowed? Are we accidentally counting the same outcome multiple times?

That careful translation skill is the main thing this node is training.