7.1 Permutations

Definition of permutations

A permutation is an arrangement of objects in a specific order. This concept sits at the heart of combinatorics and shows up constantly in probability, statistics, and algebra. Whenever you need to count how many ways things can be ordered, you're working with permutations.

Real-world examples are everywhere: how many ways can 5 people line up for a photo? How many distinct 4-digit PINs exist? How many ways can a playlist of 10 songs be shuffled?

Fundamental counting principle

The fundamental counting principle says: if one event can occur in $m$ ways and a second independent event can occur in $n$ ways, then the two events together can occur in $m \times n$ ways.

This extends to any number of independent events. Just multiply the number of options at each stage.

Example: You're choosing an outfit from 4 shirts, 3 pairs of pants, and 2 pairs of shoes. The total number of outfits is $4 \times 3 \times 2 = 24$.

This principle is the foundation for every permutation formula you'll encounter.

Factorial notation

Factorial notation gives you a shorthand for multiplying a sequence of descending positive integers. The factorial of $n$, written $n!$, is:

$n! = n \times (n-1) \times (n-2) \times \cdots \times 3 \times 2 \times 1$

So $5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$.

One special case you need to memorize: $0! = 1$. This isn't intuitive, but it's defined this way so that permutation and combination formulas work correctly when edge cases arise (like choosing 0 items from a set).

Types of permutations

Different situations call for different permutation models. The three main types are linear, circular, and permutations with repetition. Recognizing which type applies to a problem is half the battle.

Linear permutations

These are arrangements of objects in a line or sequence, where order matters. Arranging $n$ distinct objects in a row gives $n!$ total permutations.

Example: How many ways can 6 books be arranged on a shelf? That's $6! = 720$.

The key feature: position matters. The arrangement ABC is different from CBA. You can also have partial permutations, where you only arrange $r$ objects out of $n$ total (more on the formula below).

Circular permutations

When objects are arranged in a circle, rotations of the same arrangement count as identical. Think of people sitting around a round table: rotating everyone one seat clockwise doesn't create a new arrangement.

The formula for circular permutations of $n$ objects is $(n-1)!$.

Example: How many ways can 5 people sit around a circular table? That's $(5-1)! = 4! = 24$.

Why $(n-1)!$ instead of $n!$? You "fix" one person's position to eliminate the duplicate rotations, then arrange the remaining $n-1$ people.

Permutations with repetition

When objects can be reused, the count grows quickly. If you have $n$ types of objects and you're building an arrangement of length $r$, the total number of permutations is $n^r$.

Example: A 4-digit PIN where each digit can be 0–9 (digits can repeat) has $10^4 = 10{,}000$ possibilities.

There's a related but distinct scenario: permutations of indistinguishable objects. If you're arranging $n$ objects where some are identical, you divide out the duplicates. For instance, the number of distinct arrangements of the letters in "MISSISSIPPI" is:

$\frac{11!}{1! \times 4! \times 4! \times 2!} = 34{,}650$

Here you divide $11!$ by the factorials of the counts of each repeated letter (1 M, 4 I's, 4 S's, 2 P's).

Calculating permutations

Formula for permutations

The general formula for arranging $r$ objects chosen from $n$ distinct objects is:

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

How to apply it, step by step:

1. Identify $n$, the total number of distinct objects available.
2. Identify $r$, the number of objects you're selecting and arranging.
3. Plug into the formula and simplify.

Example: How many ways can you award gold, silver, and bronze medals to 3 out of 10 runners?

$P(10,3) = \frac{10!}{(10-3)!} = \frac{10!}{7!} = 10 \times 9 \times 8 = 720$

Notice that when $r = n$, the formula simplifies to $\frac{n!}{0!} = \frac{n!}{1} = n!$, which matches the linear permutation count.

Permutations vs. combinations

This distinction trips up a lot of students. The question to ask is: does the order of selection matter?

• Permutations count ordered arrangements. Choosing A then B is different from B then A.
• Combinations count unordered selections. Choosing A and B is the same as choosing B and A.

The combination formula is:

$C(n,r) = \frac{n!}{r! \times (n-r)!}$

Since combinations ignore order, $C(n,r)$ is always less than or equal to $P(n,r)$. In fact, $P(n,r) = C(n,r) \times r!$, because for each combination, there are $r!$ ways to order it.

Quick test: "How many ways can you choose a committee of 3 from 10 people?" is a combination (order doesn't matter). "How many ways can you assign president, VP, and treasurer from 10 people?" is a permutation (order matters).

Permutations with restrictions

Many problems add constraints: certain objects must be adjacent, certain positions are fixed, or certain arrangements are forbidden.

General strategy:

1. Identify the restriction clearly.
2. Break the problem into sub-problems using the multiplication principle.
3. If it's easier, count the total unrestricted permutations and subtract the forbidden ones (complementary counting).

Example types:

• Fixed positions: "Person A must sit in the first seat." Fix A, then arrange the rest: $(n-1)!$ for the remaining people.
• Adjacency requirements: "Two people must sit next to each other." Treat them as a single block, arrange the blocks, then arrange within the block.
• Derangements: No element is in its original position (covered in the advanced section below).

Applications of permutations

Probability problems

Permutations let you calculate the probability of specific ordered outcomes. You set up a fraction: favorable permutations divided by total permutations.

Example: What's the probability that 4 specific runners finish a race in a predicted exact order, out of 10 runners? The total ordered outcomes for the top 4 is $P(10,4) = 5{,}040$. Only 1 outcome matches your prediction. So the probability is $\frac{1}{5{,}040}$.

This kind of reasoning is central to analyzing card games, lottery odds, and risk assessment.

Cryptography and codes

Permutations are foundational to encryption. A substitution cipher, for example, permutes the alphabet so each letter maps to a different one. The number of possible keys for a simple substitution cipher on 26 letters is $26!$, which is over $4 \times 10^{26}$.

Modern cryptographic systems still rely on permutation operations within their algorithms, and concepts like permutation groups and cycle notation (below) help analyze their structure.

Genetic sequencing

DNA is built from 4 nucleotides (A, T, C, G). The number of possible sequences of length $n$ is $4^n$, a permutation-with-repetition calculation. For a gene of just 1,000 nucleotides, that's $4^{1000}$, an astronomically large number.

Permutation-based analysis helps researchers study gene mutations, compare evolutionary relationships, and model protein structures.

Permutations in algebra

Permutations connect combinatorics to abstract algebra. The algebraic study of permutations reveals deep structure behind symmetry and equation-solving.

Permutation groups

The set of all permutations of $n$ elements, together with the operation of composition (applying one permutation after another), forms a group called the symmetric group $S_n$.

This group satisfies the four group axioms:

• Closure: Composing two permutations gives another permutation.
• Associativity: The order of grouping compositions doesn't matter.
• Identity: The "do nothing" permutation exists.
• Inverse: Every permutation can be undone.

$S_n$ has $n!$ elements. Subgroups of symmetric groups play a major role in Galois theory, which connects group structure to the solvability of polynomial equations.

Cycle notation

Cycle notation is a compact way to write permutations. Instead of listing where every element goes, you write the "cycles" of elements that rotate among themselves.

Example: The permutation that sends $1 \to 3$, $2 \to 2$, $3 \to 1$ is written as $(1\ 3)$. Element 2 is a fixed point and is often omitted.

A more complex example: $(1\ 2\ 4)(3\ 5)$ means $1 \to 2 \to 4 \to 1$ and $3 \to 5 \to 3$.

Cycle notation makes it much easier to compose permutations and determine properties like the order of a permutation (the least common multiple of the cycle lengths).

Parity of permutations

Every permutation can be written as a product of transpositions (swaps of two elements). The number of transpositions needed may vary, but whether that number is even or odd is always the same for a given permutation. This gives every permutation a parity: even or odd.

• Even permutations form a subgroup called the alternating group $A_n$.
• Parity is preserved under composition: even ∘ even = even, odd ∘ odd = even, etc.
• Parity plays a key role in proving that there's no general formula (using radicals) for solving polynomial equations of degree 5 or higher.

Advanced permutation concepts

Derangements

A derangement is a permutation where no element remains in its original position. The number of derangements of $n$ elements is written $!n$ (subfactorial $n$) and is calculated using inclusion-exclusion:

$!n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!} = n! \left(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots + \frac{(-1)^n}{n!}\right)$

Example (the hat-check problem): 5 people check their hats. If hats are returned randomly, how many ways can no one get their own hat back?

$!5 = 5!\left(1 - 1 + \frac{1}{2} - \frac{1}{6} + \frac{1}{24} - \frac{1}{120}\right) = 120 \times \frac{11}{30} = 44$

As $n$ grows, the probability of a random permutation being a derangement approaches $\frac{1}{e} \approx 0.3679$.

Inversions in permutations

An inversion is a pair of elements where the larger one appears before the smaller one in the permutation. The number of inversions measures how "out of order" a permutation is.

• A sorted sequence has 0 inversions.
• The reverse-sorted sequence of $n$ elements has $\frac{n(n-1)}{2}$ inversions (the maximum).
• The number of inversions determines the parity of the permutation (even number of inversions = even permutation).
• Counting inversions is directly related to the efficiency of sorting algorithms. Merge sort, for example, can count inversions in $O(n \log n)$ time.

Lehmer code

The Lehmer code encodes a permutation as a sequence of non-negative integers, where each entry counts how many smaller elements appear to the right of the current element.

Example: For the permutation (3, 1, 2), the Lehmer code is (2, 0, 0) because 3 has two smaller elements to its right, 1 has zero, and 2 has zero.

This encoding creates a bijection between permutations of $n$ elements and sequences of integers where the $i$-th entry ranges from 0 to $n - i$. It's useful for generating permutations in lexicographic order and connects to the factorial number system.

Permutations in computer science

Generating permutations algorithmically

Several algorithms systematically generate all $n!$ permutations of a set:

• Lexicographic order algorithm: Generates permutations in dictionary order. Finds the rightmost element that can be increased, swaps it, and reverses the tail.
• Heap's algorithm: Generates all permutations by swapping a single pair of elements at each step, making it very efficient in practice.

These algorithms are used in brute-force search, combinatorial optimization, generating test cases, and cryptographic applications. Efficiency matters: even for modest $n$, the $n!$ permutations grow extremely fast.

Permutation-based sorting algorithms

Sorting can be viewed as finding the right permutation to apply to an unsorted list. Several basic sorting algorithms work by repeatedly swapping elements:

• Bubble sort: Repeatedly swaps adjacent out-of-order pairs. Worst case: $O(n^2)$ comparisons.
• Insertion sort: Builds the sorted sequence one element at a time. Efficient on nearly sorted data.
• Selection sort: Finds the minimum and places it in the correct position each pass.

The number of swaps these algorithms need relates directly to the number of inversions in the input permutation.

Permutation matrices

A permutation matrix is a square matrix with exactly one 1 in each row and each column, and 0s everywhere else. Multiplying a vector by a permutation matrix rearranges its entries according to the corresponding permutation.

Key properties:

• Every permutation matrix is orthogonal: its transpose equals its inverse.
• The determinant is always $+1$ or $-1$, corresponding to the parity of the permutation.
• Permutation matrices are used in LU decomposition (pivoting), computer graphics transformations, and network routing.

Historical significance

Origins of permutation theory

The study of arrangements dates back to ancient civilizations. The Chinese I Ching (circa 1000 BCE) explored combinatorial patterns, and Indian mathematicians studied permutations in the context of poetry and music.

Formal mathematical treatment began during the Renaissance, when mathematicians like Cardano and Tartaglia investigated permutations while trying to solve polynomial equations. Over centuries, permutations evolved from a practical counting tool into a central object of abstract mathematics.

Contributions of key mathematicians

• Levi ben Gerson (13th–14th century): Early systematic work on permutations and combinations.
• Blaise Pascal (17th century): Developed foundational ideas in combinatorial probability.
• Joseph-Louis Lagrange (18th century): Applied permutations to the study of polynomial roots.
• Augustin-Louis Cauchy (19th century): Formalized permutation notation and laid groundwork for group theory.
• Évariste Galois (19th century): Connected permutation groups to the solvability of equations, founding Galois theory.
• Arthur Cayley (19th century): Developed abstract group theory, showing every group can be represented as a permutation group (Cayley's theorem).

Problem-solving strategies

Identifying permutation problems

Look for these signals in a problem:

• Words like "arrange," "order," "sequence," or "rank"
• The problem asks how many ways something can be ordered
• Order matters (choosing a president, VP, and secretary is different from choosing a 3-person committee)

Then determine:

• Are all elements distinct, or are some repeated?
• Is the arrangement linear or circular?
• Is repetition allowed?
• Are there any restrictions on placement?

Common pitfalls and misconceptions

• Confusing permutations with combinations. If order matters, use permutations. If it doesn't, use combinations.
• Ignoring restrictions. Read the problem carefully for constraints like "must be adjacent" or "cannot be in position X."
• Applying the counting principle to dependent events. The multiplication principle requires independence. If choosing one item affects the next choice, adjust your counts at each step.
• Forgetting repeated elements. If letters or objects repeat, divide by the factorials of the repetition counts.
• Miscounting circular arrangements. Remember to use $(n-1)!$, not $n!$.

Step-by-step approach

1. Read the problem carefully and identify what's being arranged.

2. Determine $n$ (total elements) and $r$ (how many you're arranging).

3. Check for restrictions, repetitions, or circular arrangements.

4. Select the right formula or technique:

   • Linear, all distinct: $P(n,r) = \frac{n!}{(n-r)!}$
   • Circular: $(n-1)!$
   • With repetition allowed: $n^r$
   • With identical elements: $\frac{n!}{n_1! \times n_2! \times \cdots}$

5. For restricted problems, break into sub-cases or use complementary counting.

6. Calculate and simplify.

7. Verify with a small case if possible (e.g., list all permutations for $n = 3$ to check your formula).

8. Interpret the answer in context.