How many anagrams does the word VIRUS have? In how many ways can 5 friends sit around a round table? These questions have a different structure from the ones we saw in the article on the Sum and Product Rules: here we want to order all the elements of a set, not just choose some of them.
Why permutations? #
Ordering elements is a fundamental operation in computing and mathematics:
- Algorithm analysis: to sort \(n\) elements, there are \(n!\) possible arrangements. The contrast between an O(n!) algorithm, which would test every order, and an O(n log n) one such as mergesort shows why choosing the right algorithm can mean the difference between milliseconds and astronomical time.
- Cryptography: transposition ciphers rearrange the characters of a text as an encoding operation. Security depends, in part, on how many permutations exist: at most \(n!\) for a text of \(n\) distinct characters, although practical ciphers use only a fraction of them.
- Task scheduling: \(n\) independent processes can be run in \(n!\) orders. Finding the lowest-cost sequence is a permutation problem: for large \(n\), brute force is impractical.
- Integration testing: covering every execution order of \(n\) concurrent operations requires testing \(n!\) sequences. Formal verification tools (model checking) explore the possible execution orders to verify properties of concurrent systems, such as the absence of race conditions.
- Routing: the number of routes that leave a city, visit the others exactly once, and return to the origin is \((n-1)!\), the basis of the classic Traveling Salesman Problem (TSP).
This article formalizes the simple permutation (ordering in a line) and the circular permutation (ordering in a circle), with examples of anagrams, round tables, and adjacency restrictions.
Factorial #
Before permutations themselves, we need the factorial:
| \(n\) | \(n!\) |
|---|---|
| 0 | 1 |
| 1 | 1 |
| 2 | 2 |
| 3 | 6 |
| 4 | 24 |
| 5 | 120 |
| 6 | 720 |
It is not an arbitrary convention. First, the relation \(n! = n \cdot (n-1)!\) only holds for \(n = 1\) if \(1! = 1 \cdot 0!\), which forces \(0! = 1\). Second, \(n!\) counts the ways of ordering \(n\) objects, and there is exactly one way of ordering zero objects: doing nothing.
Intuition: if we have 4 pens of different colors to hand out among 4 friends, the first receives any of the 4, the second any of the 3 remaining, and so on: \(4 \times 3 \times 2 \times 1 = 4! = 24\) distributions.
Simple Permutation #
A simple permutation of \(n\) distinct elements is an ordering of all those elements in a line.
$$P_n = n!$$Justification: \(n\) choices for the 1st element, \(n-1\) for the 2nd, …, 1 for the last: \(n \cdot (n-1) \cdots 1 = n!\)
Examples #
Example 1: Anagrams of VIRUS
Statement: In how many distinct ways can the 5 letters of the word VIRUS be arranged?
Solution: The 5 letters are all distinct and we want to order all of them in a line, which characterizes a simple permutation. We count the choices position by position:
| Position | Available options | Reason |
|---|---|---|
| 1st | 5 | any of the 5 letters |
| 2nd | 4 | one letter already used |
| 3rd | 3 | two letters already used |
| 4th | 2 | three letters already used |
| 5th | 1 | only one letter left |
Example 2: Anagrams of VIRUS that start and end with a consonant
Statement: How many anagrams of VIRUS start and end with a consonant?
Solution: VIRUS has 3 consonants (V, R, S) and 2 vowels (I, U).
The strategy is to fill the restricted positions first (1st and 5th), then the others:
| Position | Options | Reason |
|---|---|---|
| 1st (must be a consonant) | 3 | any of the 3 consonants |
| 5th (must be a consonant) | 2 | from the 2 remaining consonants |
| 2nd, 3rd, 4th (free) | 3! = 6 | the 3 letters left over (2 vowels + 1 consonant) in any order |
Filling the restricted positions first avoids the mistake of computing the total and then trying to “remove” invalid cases: here the Product Rule already guarantees that every arrangement counted is valid.
Python: itertools.permutations and math.factorial
itertools.permutations and math.factorial
Python’s standard library offers two complementary paths: enumerating the permutations or just counting how many there are.
import itertools
import math
letters = "VIRUS"
# Count: P_5 = 5! = 120
print(math.factorial(len(letters))) # 120
# Enumerate and filter: starting and ending with a consonant
consonants = set("VRS")
anagrams = itertools.permutations(letters)
filtered = [a for a in anagrams
if a[0] in consonants and a[-1] in consonants]
print(len(filtered)) # 36itertools.permutations(iterable, r) generates all permutations of length
\(r\) as tuples (omitting \(r\) uses all the elements). For
large problems, never convert the iterator to a list: \(20! > 2 \times 10^{18}\).
Example 3: 5-digit numbers with \(\{0, 5, 7, 8, 9\}\)
Statement: Using each digit of the set \(\{0, 5, 7, 8, 9\}\) exactly once, how many 5-digit numbers can be formed?
Solution: The set has 5 distinct digits, and without restrictions there would be \(P_5 = 120\) arrangements. The restriction is that the digit 0 cannot occupy the 1st position: a number with 0 in front would effectively have only 4 digits.
Direct reasoning: fill the restricted position first:
| Position | Options | Reason |
|---|---|---|
| 1st | 4 | \(\{5, 7, 8, 9\}\), with 0 excluded |
| 2nd | 4 | the 4 remaining digits, including 0 |
| 3rd | 3 | |
| 4th | 2 | |
| 5th | 1 |
Check by complement: subtract the invalid cases from the total:
$$5! - 4! = 120 - 24 = 96 \checkmark$$The \(4!\) cases removed correspond to all the arrangements in which 0 occupies the 1st position and the 4 remaining digits fill the other positions freely.
Example 4: Concert: 4 women and 5 men in consecutive seats, groups kept apart
Statement: Nine friends attend a concert with assigned, consecutive seats. The 4 women must all sit together, and so must the 5 men. In how many ways can they sit?
Solution: Since the seats are assigned and consecutive (a linear row), there are two possibilities for the order of the blocks: [W W W W | M M M M M] or [M M M M M | W W W W]. Within each block, the members order themselves freely.
| Step | Calculation | Reason |
|---|---|---|
| Relative position of the blocks | 2 | women’s block to the left or to the right of the men’s |
| Internal permutations of the women | \(4! = 24\) | the 4 women order themselves within the block |
| Internal permutations of the men | \(5! = 120\) | the 5 men order themselves within the block |
Circular Permutation #
When arranging people around a round table, what matters is the relative position: there is no “first chair”. Rotations of the same arrangement count as the same permutation.
The number of circular permutations of \(n\) distinct elements is:
$$PC_n = \frac{P_n}{n} = (n-1)!$$Intuition: each circular permutation corresponds to \(n\) linear permutations (each rotation produces a new ordering in a line, but the same arrangement in a circle). Therefore, we divide by \(n\).
The figure below shows this for 5 people. Each table is the previous one rotated by one chair; read from the same chair, the five give different lines, but in all of them each person has the same neighbors:
Examples #
Example 1: 5 friends around a round table
Statement: In how many ways can 5 friends sit around a round table?
Solution: In a line, each person’s position is absolute. At a round table, what matters is the relative position among those present: shifting everyone one chair to the right does not create a new arrangement, just a rotation of the same one.
To eliminate equivalent rotations, we fix one person in any chair and permute the other 4:
$$PC_5 = (5-1)! = 4! = 24$$
Application: the Traveling Salesman Problem (TSP)
The problem: a salesman needs to visit \(n\) cities exactly once and return to the city of origin. Between each pair of cities there is a known distance. What is the route with the smallest total distance?
Formally: given a complete graph with \(n\) vertices (cities) and weighted edges (distances), find the lowest-cost Hamiltonian cycle, the one that passes through every vertex exactly once.
Why it belongs here: the route forms a cycle and the starting city does not change the structure of the tour, which is exactly the definition of a circular permutation. The number of distinct routes to evaluate is \((n-1)!\), or \((n-1)!/2\) when the distance from one city to another equals the distance back, because each route and the same route traveled in the opposite direction have the same length.
The scale of the problem: for \(n = 20\) cities, there are \(19! \approx 1.2 \times 10^{17}\) possible routes. If a computer evaluated \(10^9\) routes per second, it would take almost 4 years to test them all. For \(n = 30\), the time would exceed the age of the universe.
What NP-hard means: the class NP gathers the problems whose solutions can be verified in polynomial time. A problem is NP-hard when every problem in NP can be reduced to it in polynomial time, that is, it is at least as hard as any of them. Therefore, a polynomial algorithm for the TSP would solve all the problems in NP at once. Nobody knows such an algorithm, and nobody has proved that it does not exist: this is the question P versus NP, one of the great open problems of mathematics. The best known exact algorithm for the TSP has exponential complexity. In practice, this means that for large instances the problem is intractable by brute force, and one resorts to approximation algorithms (which guarantee a solution within a factor of the optimum) or heuristics such as genetic algorithms and simulated annealing (which find good solutions with no guarantee of optimality). The TSP is one of the most studied problems in combinatorial optimization.
Examples 2 and 3: Two non-adjacent elements: complement vs. sequential insertion
The next two examples solve the same type of problem (two specific elements cannot be adjacent in a circular arrangement) with different strategies. The goal is to show when each approach is more natural.
The diagram below summarizes the choice: the key question is whether the forbidden cases are easy to count directly.
flowchart TD
A["Two elements cannot be adjacent
in a circular arrangement"] --> B{"Are the forbidden cases
easy to count
as a block?"}
B -->|Yes| C["Complement
Total − Forbidden"]
B -->|No| D["Sequential insertion
Build avoiding
the restriction from the start"]
C --> E["Ex. 2: 5 children
24 − 12 = 12"]
D --> F["Ex. 3: 6 children
6 × 4 × 3 = 72"]
Example 2: Ring dance of 5 children: the complement strategy
Statement: Five children (\(c_1, c_2, c_3, c_4, c_5\)) form a ring dance circle. In how many ways can they be arranged so that \(c_1\) and \(c_2\) are not side by side?
Strategy (complement): instead of directly counting the valid cases (hard), we count the total and subtract the forbidden cases (easier).
$$\text{valid} = \text{total} - \text{cases with } c_1 \text{ and } c_2 \text{ together}$$Total without restriction:
$$PC_5 = (5-1)! = 4! = 24$$Forbidden cases (\(c_1\) and \(c_2\) together): we treat \(\{c_1, c_2\}\) as a single block. The problem becomes arranging 4 entities in a circle and ordering the block internally:
| Step | Calculation | Reason |
|---|---|---|
| 4 entities in a circle | \((4-1)! = 3! = 6\) | block + \(c_3, c_4, c_5\) |
| Ordering \(c_1\) and \(c_2\) within the block | \(2! = 2\) | \(c_1 c_2\) or \(c_2 c_1\) |
Forbidden cases: \(6 \times 2 = 12\)
$$PC_5 - \text{forbidden} = 24 - 12 = \mathbf{12}$$When to use the complement: when the forbidden cases form a compact set that is easy to describe. Here, it is enough to treat the pair as a block.
Example 3: Circle of 6 children: the sequential insertion strategy
Statement: Six children (\(c_1\) to \(c_6\)) form a ring dance circle. In how many ways can they be arranged so that \(c_1\) and \(c_2\) are not side by side?
Strategy (sequential insertion): we first place the unrestricted elements, creating a structure of gaps, and insert the problematic elements last, choosing only valid positions from the start.
| Step | Calculation | Reason |
|---|---|---|
| Arrange \(c_3, c_4, c_5, c_6\) in a circle | \((4-1)! = 3! = 6\) | 4 unrestricted children form the base structure |
| Insert \(c_1\) into one of the 4 gaps between them | \(6 \times 4 = 24\) | 4 gaps available: any position is valid for \(c_1\) |
| Insert \(c_2\) in a position not adjacent to \(c_1\) | \(24 \times 3 = 72\) | of the 5 remaining gaps, 2 are adjacent to \(c_1\); 3 valid ones remain |
The diagram below illustrates the three stages of the construction. Each arrow represents a multiplication by the number of choices available at that step:
flowchart LR
A["Stage 1
c₃ c₄ c₅ c₆
in a circle
(PC)₄ = 6"] -->|"× 4 positions
for c₁"| B["Stage 2
Insert c₁
24 arrangements"] -->|"× 3 non-adjacent
positions
for c₂"| C["Stage 3
Insert c₂
72 arrangements"]
When to use sequential insertion: when the complement would be hard to compute. For example, if there were multiple forbidden pairs, counting by complement would require inclusion-exclusion. Sequential insertion builds the restriction directly into the construction, with nothing to subtract.
Example 4: Concert revisited: what if the stage were circular?
Statement: The same 9 friends from Example 4 of the previous section, 4 women and 5 men, now position themselves around a circular stage, keeping the restriction that all the women stay together and all the men together. In how many ways can they be arranged?
Solution: The block structure is the same, but the context changed from linear to circular. What changes?
In the linear case, the 2 blocks could occupy two distinct orders in the line: [W|M] or [M|W]. In the circle, rotating everyone one position turns [W|M] into [M|W]: the two orders are rotations of each other and count as the same arrangement. With only 2 blocks in a circle, there is \((2-1)! = 1\) circular arrangement.
| Step | Linear (previous Ex. 4) | Circular (this example) |
|---|---|---|
| Arrangement of the blocks | 2 (order matters in a line) | \((2-1)! = 1\) (equivalent rotations) |
| Internal permutations of the women | \(4! = 24\) | \(4! = 24\) |
| Internal permutations of the men | \(5! = 120\) | \(5! = 120\) |
| Total | \(2 \times 24 \times 120 = \mathbf{5{,}760}\) | \(1 \times 24 \times 120 = \mathbf{2{,}880}\) |
The factor 2 that existed in the linear case disappears in the circular one: in a circle, “women to the left of the men” and “men to the left of the women” describe the same relative arrangement, just rotated.
Python: simulating circular permutations
To generate circular permutations without counting rotations as distinct, just fix one element and permute the others:
import itertools
import math
people = ["Ana", "Luís", "Fernando", "Clara", "Bruno"]
# Fix "Ana" and permute the other 4: (5-1)! = 4! = 24
fixed = people[0]
others = people[1:]
circular = list(itertools.permutations(others))
print(len(circular)) # 24
print(math.factorial(len(people) - 1)) # 24Fixing one element is exactly what the formula \((n-1)!\) formalizes: it removes the \(n\) rotationally equivalent arrangements, leaving only the structurally distinct ones.
Comparing Linear and Circular Permutations #
For 3 people (Ana, Luís, Fernando):
| Arrangement | Counts as | Total |
|---|---|---|
| Line (numbered positions) | Simple permutation | \(3! = 6\) |
| Triangle with numbered seats | Simple permutation | \(3! = 6\) |
| Round table (only relative position matters) | Circular permutation | \((3-1)! = 2\) |
Derangements: Nobody in Their Own Place #
One last family of restricted permutations has a name of its own. In a gift exchange, \(n\) people put their gifts in a box and each draws one. In how many ways can the draw come out with nobody getting their own gift? The problem was posed by Pierre Rémond de Montmort in 1708, in the Essay d’analyse sur les jeux de hazard, and solved by him and by Nicolaus Bernoulli around 1713 (see the entry Derangement).
A derangement of \(n\) elements is a permutation in which no element occupies its original position. The number of derangements is denoted \(D_n\).
Small cases. With the letters A, B, C in positions 1, 2, 3, there are only two derangements: BCA and CAB, so \(D_3 = 2\). With A, B, C, D there are nine, \(D_4 = 9\):
BADC · BCDA · BDAC · CADB · CDAB · CDBA · DABC · DCAB · DCBA
And, in the trivial cases, \(D_1 = 0\) (a single element has nowhere to go) and \(D_2 = 1\) (BA).
A recurrence by counting. In a derangement, element 1 goes to some position \(k \neq 1\): there are \(n-1\) choices, and each one yields the same number of derangements. With position \(k\) fixed, we look at where element \(k\) goes:
- Element \(k\) goes to position 1 (the two swap places): the other \(n-2\) elements must form a derangement among themselves, which gives \(D_{n-2}\) ways.
- Element \(k\) does not go to position 1: there remain \(n-1\) elements (all but
- for \(n-1\) positions (all but \(k\)), each element with one forbidden position (its own and, for element \(k\), position 1). This is exactly a derangement of \(n-1\) elements: \(D_{n-1}\) ways.
Adding the two cases and multiplying by the \(n-1\) choices of \(k\):
$$D_n = (n-1)\left(D_{n-1} + D_{n-2}\right), \qquad D_1 = 0,\ D_2 = 1$$Checking: \(D_3 = 2(1 + 0) = 2\) and \(D_4 = 3(2 + 1) = 9\), as in the list above; and \(D_5 = 44\) and \(D_6 = 265\) follow.
The closed-form formula and the number \(e\). The Inclusion-Exclusion Principle leads to the formula \(D_n = n! \sum_{k=0}^{n} (-1)^k/k!\), derived in the article on cardinality. From it comes the most surprising result of the topic: the fraction of draws in which nobody gets their own gift, \(D_n/n!\), approaches \(1/e\), about 36.8%, practically the same for 10 people or for 10 thousand.
Python: checking the recurrence by brute force
For small \(n\), we can enumerate all the permutations and count the ones that leave nobody in their place:
from itertools import permutations
def brute_force_derangements(n):
return sum(1 for p in permutations(range(n))
if all(p[i] != i for i in range(n)))
D = {1: 0, 2: 1}
for n in range(3, 9):
D[n] = (n - 1) * (D[n - 1] + D[n - 2])
print([D[n] for n in range(1, 9)])
# [0, 1, 2, 9, 44, 265, 1854, 14833]
print(all(D[n] == brute_force_derangements(n) for n in range(1, 9))) # TrueSummary Table #
| Type | Formula | When to use |
|---|---|---|
| Simple permutation | \(P_n = n!\) | Line: absolute position matters |
| Circular permutation | \(PC_n = (n-1)!\) | Circle: relative position matters |
| With a required block | \(k! \times P_{\text{remaining}}\) | Elements that must stay together |
| With a restriction (e.g., 0 at the start) | Complement | Remove invalid cases |
| Derangement | \(D_n = (n-1)(D_{n-1} + D_{n-2})\) | Nobody in the original position |
Exercises #
Exercise 1: Simplifying factorials
Simplify: (a) \(\dfrac{(n+1)!}{n!}\) (b) \(\dfrac{n!}{(n+2)!}\) (c) \(\dfrac{(n+1)!}{(n-1)!}\)
Answers
(a) \(n+1\)
(b) \(\dfrac{1}{(n+2)(n+1)}\)
(c) \((n+1) \cdot n\)
Exercise 2: Anagrams of ÂNGULO
How many anagrams of the word ÂNGULO (Portuguese for “angle”) (a) start with a vowel? (b) start and end with a vowel? (c) do not have the letters A and N together?
Solution
ÂNGULO has 6 distinct letters: vowels Â, U, O; consonants N, G, L. Total: \(6! = 720\).
(a) 3 choices for the 1st position × \(5! = 120\): \(3 \times 120 = \mathbf{360}\)
(b) 3 × 2 for the 1st and last positions × \(4! = 24\): \(3 \times 2 \times 24 = \mathbf{144}\)
(c) By complement: treat \(\{A, N\}\) as a block → 5 units, \(5!\) arrangements × 2 internal orders = \(240\). Not together: \(720 - 240 = \mathbf{480}\)
Exercise 3: Numbered faces of a cube
A cube has its faces painted in different colors. In how many ways can the numbers 1 to 6 be engraved, one on each face?
Answer
Since each face is painted a distinct color, the 6 faces are distinguishable positions, with no ambiguity about which is which. Engraving the numbers 1 to 6, one on each face, is a permutation of 6 elements in 6 distinct positions:
$$P_6 = 6! = \mathbf{720} \text{ ways}$$
Exercise 4: Ring dance with alternating sexes
In how many ways can 5 girls and 5 boys form a ring dance circle so that people of the same sex are not next to each other?
Answer
The sexes must alternate (B-G-B-G…).
- Arrange the 5 boys in a circle: \((5-1)! = 4! = 24\)
- Arrange the 5 girls in the 5 alternating places: \(5! = 120\) $$4! \times 5! = 24 \times 120 = \mathbf{2{,}880}$$
Exercise 5: Couples in a circle with alternating sexes
In how many ways can 4 couples form a ring dance circle with men and women alternating, with each couple adjacent?
Answer
- Arrange the 4 couples as units in a circle: \((4-1)! = 3! = 6\) arrangements.
- To keep the sexes alternating, all the couples must have the same internal orientation: if couple 1 is arranged as M-W (clockwise), all the others must follow the same order, since any couple with reversed orientation would put two elements of the same sex in adjacent positions. The couples’ orientations are not independent: there are only 2 global choices (all M-W or all W-M). $$3! \times 2 = 6 \times 2 = \mathbf{12} \text{ ways}$$
Next steps #
Permutation orders all \(n\) elements. When we want to select and order only \(r \leq n\) of them, without necessarily using all of them, we enter the domain of arrangements (or r-permutations, also called partial permutations), the topic of the next article in the series.
Later on, we will see how to count groupings in which order does not matter, the combinations, completing the fundamental triad of combinatorics: permutations, arrangements, and combinations.
