Permutations

How many ways can eight sprinters finish a race with no ties? How many ways can a judge award gold, silver, and bronze medals among them? Both questions ask for the number of ordered arrangements of distinct objects. Both are answered by the same idea: a permutation. Permutations sit at the foundation of enumerative combinatorics. They turn the informal act of "arranging things in order" into a precise counting formula. This formula is built directly from the Product Rule. The idea matters because ordering is everywhere. Passwords, race results, seating charts, DNA-reading frames, and shuffles of a deck of cards are all governed by the same combinatorial skeleton. Once we know how to count arrangements of all nn objects, and arrangements of just rr of them at a time, an enormous range of counting problems collapses into applications of a single formula. Permutations also serve as the natural counterpart to combinations, where order is deliberately ignored. Understanding permutations precisely is what makes the distinction meaningful rather than hand-wavy. The big picture is this: counting ordered selections is fundamentally a repeated application of the Product Rule. At each stage, the number of remaining choices shrinks by exactly one. This "shrinking choices" pattern is what factorial notation was invented to capture compactly. Once formalized, the resulting theorem is not just a formula to memorize. It is a small proof by induction (or direct product-rule argument) that every student can reconstruct from scratch. This article gives the formal definition of an rr-permutation. It proves the counting formula for P(n,r)P(n,r) rigorously from the Product Rule. It works through two asymmetric numerical examples, and shows precisely what goes wrong if the objects are not distinct. It closes by connecting permutations to their natural sequel: Combinations, the Binomial Theorem, and more refined variants such as circular and restricted permutations.

Key takeaways
  • A permutation of a set is an ordered arrangement of all its elements; an rr-permutation arranges only rr of them.
  • The count of rr-permutations of nn distinct objects is P(n,r)=n(n−1)(n−2)⋯(n−r+1)P(n,r) = n(n-1)(n-2)\cdots(n-r+1).
  • In factorial notation, P(n,r)=n!(n−r)!P(n,r) = \dfrac{n!}{(n-r)!}, valid for integers 0≤r≤n0 \le r \le n.
  • When r=nr = n, this reduces to P(n,n)=n!P(n,n) = n!, the count of full arrangements.
  • The formula is proved by the Product Rule applied to a sequence of rr dependent choices, not by any circular appeal to combinations.
  • Key idea: counting ordered arrangements is repeated application of the Product Rule with the pool of choices shrinking by one at each step.

Where this lives today

Permutations are the combinatorial backbone of many applied fields. In cryptography, the security of block ciphers and substitution-permutation networks rests on permutations of bit-strings, and key-space sizes are literally P(n,r)P(n,r)- or n!n!-type counts. In computer science, algorithms for generating, ranking, and unranking permutations (e.g. Lehmer codes) are used in testing, randomized algorithms, and combinatorial optimization such as the traveling salesman problem, where the search space has size (n−1)!/2(n-1)!/2 for undirected tours. In statistics, permutation tests use the set of all reorderings of data labels to build nonparametric significance tests, relying directly on counting all n!n! or restricted arrangements. In physics and chemistry, permutations of identical particles underlie quantum statistics (Bose–Einstein vs. Fermi–Dirac counting) and the combinatorics of molecular symmetry. In pure mathematics, permutations form the symmetric group SnS_n, a central object in group theory-adjacent combinatorics, representation theory, and Galois theory, while rr-permutations directly generalize to the Binomial Theorem and multinomial expansions once repetition or order-indifference is introduced.

Ask the tutor: How does the rr-permutation formula generalize when repetition of objects is allowed, and how does that connect to the multinomial theorem?

DefinitionPermutations and rr-permutations

Let SS be a set with ∣S∣=n|S| = n distinct elements, and let rr be an integer with 0≤r≤n0 \le r \le n. An rr-permutation of SS is an ordered sequence (a1,a2,…,ar)(a_1, a_2, \dots, a_r) of rr distinct elements of SS; equivalently, it is an injective function f:{1,2,…,r}→Sf : \{1, 2, \dots, r\} \to S, where f(i)=aif(i) = a_i. The number of rr-permutations of a set with nn elements is denoted P(n,r)P(n,r) (also written nPr{}_nP_r or nr‾n^{\underline{r}}). A permutation of SS (with no qualifier) is the special case r=nr = n: an ordered arrangement of all nn elements of SS, i.e. a bijection f:S→Sf : S \to S realized as a sequence listing every element exactly once. By convention 0!=10! = 1 and an empty sequence (the case r=0r=0) is the unique 00-permutation of any set.

Intuition

Think of filling rr labeled slots, one at a time, from a pool of nn distinct objects, where once an object is placed it is removed from the pool. The first slot can be filled in nn ways. Having used up one object, the second slot can be filled in n−1n-1 ways — no matter which object filled the first slot, exactly n−1n-1 remain. This "no matter which" independence of the count of remaining choices (even though the identity of remaining choices depends on earlier picks) is exactly the hypothesis the Product Rule needs. Continuing, the kk-th slot has n−(k−1)n-(k-1) available objects, and the process stops after rr slots, having used the factors n,n−1,…,n−r+1n, n-1, \dots, n-r+1. The picture below shows this shrinking-pool process for n=5n = 5 objects and r=3r = 3 slots: the number of available choices at each stage decreases by exactly one, and the total count is the product of the numbers along the top.

Figure
Filling r=3r=3 ordered slots from a pool of n=5n=5 distinct objects: choices shrink 5→4→35 \to 4 \to 3
Choices remaining at each slot (n=5, r=3) slot 1 5 choices × slot 2 4 choices × slot 3 3 choices P(5,3) = 5 × 4 × 3 = 60 one object is removed from the pool after each slot is filled

The key subtlety the diagram encodes: at slot 2, the particular four objects available depend on what was chosen at slot 1, but the number four does not. That invariance of count regardless of prior choice is precisely what licenses multiplying the three numbers together rather than needing a more delicate case analysis.

TheoremThe rr-permutation counting formula

Let nn and rr be integers with 0≤r≤n0 \le r \le n, and let SS be a set with ∣S∣=n|S| = n. Then the number of rr-permutations of SS is

P(n,r)=n(n−1)(n−2)⋯(n−r+1)=n!(n−r)!.P(n,r) = n(n-1)(n-2)\cdots(n-r+1) = \frac{n!}{(n-r)!}.

In particular, taking r=nr = n, the number of permutations of an nn-element set is P(n,n)=n!P(n,n) = n!.

Proof

We give a direct proof by the Product Rule, using induction on rr to make the repeated application rigorous. Fix n≥0n \ge 0 and let SS be a set with ∣S∣=n|S| = n.

Setup as an ordered choice process. An rr-permutation of SS is precisely a sequence of choices (a1,…,ar)(a_1, \dots, a_r) where:

  • a1a_1 is chosen freely from SS;
  • for each kk with 2≤k≤r2 \le k \le r, aka_k is chosen from S∖{a1,…,ak−1}S \setminus \{a_1, \dots, a_{k-1}\}, i.e. from whatever remains after removing the previously chosen elements.

This is exactly the definition of an rr-permutation: the sequence must consist of distinct elements, and this constraint is enforced slot-by-slot by choosing each aka_k outside the set of earlier choices.

Claim (constant fiber size). For every choice of a1,…,ak−1a_1, \dots, a_{k-1} (distinct elements of SS), the number of valid choices for aka_k is exactly n−(k−1)n - (k-1). Proof of claim. Since a1,…,ak−1a_1, \dots, a_{k-1} are k−1k-1 distinct elements of SS, the set S∖{a1,…,ak−1}S \setminus \{a_1, \dots, a_{k-1}\} has exactly ∣S∣−(k−1)=n−k+1|S| - (k-1) = n - k + 1 elements, by the finite subtraction rule for cardinalities of finite sets (removing jj distinct elements from a finite set of size nn leaves a set of size n−jn - j, provable by a trivial induction on jj using ∣A∖{x}∣=∣A∣−1|A \setminus \{x\}| = |A| - 1 for x∈Ax \in A). Thus there are exactly n−k+1n-k+1 valid choices for aka_k, regardless of which particular (k−1)(k-1)-tuple of distinct elements preceded it. ■\blacksquare (claim)

Induction on rr to assemble the product. Let P(n,r)P(n,r) denote the number of rr-permutations of SS. We show

P(n,r)=∏i=0r−1(n−i)P(n,r) = \prod_{i=0}^{r-1} (n-i)

by induction on rr, for 0≤r≤n0 \le r \le n. Base case r=0r = 0. The only 00-permutation is the empty sequence, so P(n,0)=1P(n,0) = 1, and the empty product ∏i=0−1(n−i)\prod_{i=0}^{-1}(n-i) is 11 by convention. The formula holds. Inductive step. Suppose 0≤r<n0 \le r < n and the number of rr-permutations of SS is ∏i=0r−1(n−i)\prod_{i=0}^{r-1}(n-i) (inductive hypothesis). An (r+1)(r+1)-permutation is obtained by first choosing an rr-permutation (a1,…,ar)(a_1,\dots,a_r) and then appending one more element ar+1∈S∖{a1,…,ar}a_{r+1} \in S \setminus \{a_1,\dots,a_r\}. By the claim above (with k=r+1k = r+1), for every fixed rr-permutation (a1,…,ar)(a_1,\dots,a_r) there are exactly n−rn - r valid choices of ar+1a_{r+1} — this count does not depend on which rr-permutation was fixed. This is precisely the hypothesis required by the Product Rule: a two-stage process where stage one has P(n,r)P(n,r) outcomes and, independent of which stage-one outcome occurs, stage two always has n−rn-r outcomes. The Product Rule then gives

P(n,r+1)=P(n,r)⋅(n−r)=(∏i=0r−1(n−i))(n−r)=∏i=0r(n−i),P(n,r+1) = P(n,r) \cdot (n-r) = \left(\prod_{i=0}^{r-1}(n-i)\right)(n-r) = \prod_{i=0}^{r}(n-i),

using the inductive hypothesis in the middle equality. This completes the induction.

Conclusion of the product form. By induction, for all 0≤r≤n0 \le r \le n,

P(n,r)=∏i=0r−1(n−i)=n(n−1)(n−2)⋯(n−r+1),P(n,r) = \prod_{i=0}^{r-1}(n-i) = n(n-1)(n-2)\cdots(n-r+1),

a product of exactly rr consecutive descending integer factors starting at nn.

Factorial form. If r=nr = n, the product runs over all integers from nn down to 11, so P(n,n)=n!P(n,n) = n! by definition of factorial. For general 0≤r≤n0 \le r \le n, multiply and divide by the missing descending factors:

P(n,r)=n(n−1)⋯(n−r+1)=n(n−1)⋯(n−r+1)⋅(n−r)(n−r−1)⋯1(n−r)(n−r−1)⋯1=n!(n−r)!,P(n,r) = n(n-1)\cdots(n-r+1) = \frac{n(n-1)\cdots(n-r+1)\cdot (n-r)(n-r-1)\cdots 1}{(n-r)(n-r-1)\cdots 1} = \frac{n!}{(n-r)!},

valid since (n−r)!≥1!(n-r)! \ge 1! or 0!=10!=1 is a well-defined nonzero integer for 0≤r≤n0 \le r \le n (so no division by zero occurs). This establishes both stated formulas. ■\blacksquare

∎

Worked examples

Example 1: Course scheduling with three distinguishable slots. A student must choose an ordered schedule of 33 distinct courses, in order (1st period, 2nd period, 3rd period), from a catalog of 1111 available distinct courses, no repeats allowed. How many ordered schedules are possible? Here n=11n = 11, r=3r = 3. By the theorem,

P(11,3)=11⋅10⋅9=11!8!.P(11,3) = 11 \cdot 10 \cdot 9 = \frac{11!}{8!}.

Compute directly: 11⋅10=11011 \cdot 10 = 110, and 110⋅9=990110 \cdot 9 = 990. So there are 990990 possible ordered schedules. Note the asymmetry: n=11n=11 is not a small round number and r=3≠nr=3 \ne n, so this genuinely tests the general rr-permutation formula rather than the special case n!n!.

Example 2: A 4-digit access code from a restricted alphanumeric set, with a twist. Suppose a security system generates access codes as ordered sequences of 44 distinct symbols drawn from the 77-symbol set {A,B,C,D,1,2,3}\{A, B, C, D, 1, 2, 3\} — but the first symbol of the code is required to be a letter (one of A,B,C,DA,B,C,D), while the remaining three symbols may be any of the remaining 66 distinct symbols (in any order, still without repetition). How many such codes exist? This is not a bare P(n,r)P(n,r) computation — it requires combining a restricted first choice with a full permutation count via the Product Rule, foreshadowing Circular and Restricted Permutations. Stage 1: Choose the first symbol: it must be a letter, and there are 44 letters, so 44 choices. Stage 2: Choose an ordered arrangement of the remaining 33 symbol-slots from the 66 symbols not yet used (the 7−1=67-1=6 remaining distinct symbols, since one letter has been placed). Regardless of which letter was placed in stage 1, exactly 66 symbols remain, and we need an ordered selection of 33 of them without repetition — this is P(6,3)P(6,3). By the theorem, P(6,3)=6⋅5⋅4=120P(6,3) = 6 \cdot 5 \cdot 4 = 120. By the Product Rule (the count 120120 at stage 2 is the same regardless of the stage-1 outcome, satisfying the rule's hypothesis), the total number of codes is

4×P(6,3)=4×120=480.4 \times P(6,3) = 4 \times 120 = 480.

So there are 480480 valid access codes. This example shows how the rr-permutation formula is a building block, combined with the Product Rule, rather than a rigid template that only applies to unrestricted problems.

CounterexampleWhy the objects must be distinct

The theorem requires that SS consist of nn distinct elements. Drop this hypothesis and the formula collapses. Consider the multiset S={a,a,b}S = \{a, a, b\} with n=3n = 3 "objects" but only 22 distinct values, and ask for the number of r=3r=3-arrangements (i.e., all full "permutations" of the multiset, meaning distinct-looking output strings). The theorem's formula would claim

P(3,3)=3!=6.P(3,3) = 3! = 6.

But if we physically list all orderings of the three symbols a,a,ba, a, b treating the two copies of aa as identical (which is the natural reading once objects are not distinct), the distinct output strings are:

aab,  aba,  baa,aab, \; aba, \; baa,

only 33 strings, not 66. The naive count of 66 arises only if we artificially distinguish the two copies of aa (say a1,a2a_1, a_2), giving 3!=63! = 6 labeled arrangements, but each distinct output string is then produced by exactly 2!=22! = 2 of these labeled arrangements (since the two aa's can be swapped without changing the visible string), so the true count of distinct arrangements is 3!/2!=33!/2! = 3, matching the direct list. This is exactly why the multinomial correction factor is needed once repeated objects are allowed, and it shows precisely which hypothesis of the theorem — distinctness of the nn objects — is doing the work: without it, P(n,r)=n!/(n−r)!P(n,r) = n!/(n-r)! overcounts by exactly the factor of internal symmetries among identical objects.

Scope, edge cases & common traps

SituationCorrect handling
r=0r = 0P(n,0)=1P(n,0) = 1 (the empty arrangement), matches n!/n!=1n!/n! = 1
r=nr = nP(n,n)=n!P(n,n) = n!, full arrangements
r>nr > nP(n,r)P(n,r) is undefined / declared 00: cannot choose more distinct objects than exist
Objects not distinguishableFormula overcounts; must divide by symmetry factor (multinomial coefficient)
Order does not matterUse Combinations (nr)=P(n,r)/r!\binom{n}{r} = P(n,r)/r! instead
Arrangement is circular, not linearUse circular permutation count (n−1)!(n-1)!, see Circular and Restricted Permutations

The mathematician behind it

The systematic study of permutations as ordered arrangements, and the factorial notation used to count them, developed gradually across many contributors rather than from a single inventor — but Leonhard Euler stands out for making permutations and their generating functions rigorous, general-purpose combinatorial tools deployed across number theory, analysis, and what we would now call graph theory.

Origins · 1 minLeonhard Euler and how this was discovered
LE
Leonhard Euler
1707–1783 · Enlightenment-era mathematics, Basel/St. Petersburg/Berlin

Euler produced foundational results connecting permutations to partitions, generating functions, and derangement counts (the classic "hat-check problem"), embedding the study of ordered arrangements into the wider machinery of combinatorial analysis that underlies modern enumerative combinatorics.

History
- 1500s–1600s: Early tabulations of arrangement counts appear in combinatorial and gaming contexts across Indian, Arabic, and European mathematics.
- 1666: Gottfried Leibniz's Dissertatio de Arte Combinatoria systematizes combinatorial reasoning, including ordered arrangements.
- 1730s: Euler studies permutation-related problems including the derangement ("problème des rencontres") count.
- 1808: Christian Kramp popularizes the factorial notation n!n! that makes permutation formulas compact and standard.
- 20th century: Permutations become central to algorithmic combinatorics, coding theory, and computational complexity via ranking/unranking and generation algorithms.
What is the difference between a permutation and an rr-permutation?

A permutation (with no qualifier) arranges all nn elements of a set in order, so there are n!n! of them. An rr-permutation arranges only rr of the nn elements, chosen and ordered simultaneously, with 0≤r≤n0 \le r \le n; there are P(n,r)=n!/(n−r)!P(n,r) = n!/(n-r)! of these. A permutation is simply the special case r=nr = n of an rr-permutation, since then (n−r)!=0!=1(n-r)! = 0! = 1 and P(n,n)=n!P(n,n) = n!. Both concepts require the same underlying rule: no repeats, and order matters.

Why is P(n,r)=n!/(n−r)!P(n,r) = n!/(n-r)! rather than something involving addition?

The formula emerges from a chain of multiplicative dependent choices, not additive ones, because filling each of the rr ordered slots is a separate stage in a multi-stage process governed by the Product Rule, not the Sum Rule. The Sum Rule applies when counting a union of disjoint alternative outcomes; here, however, every rr-permutation requires all rr slots to be filled simultaneously, which is a conjunction of stages, not a choice among alternatives. The factorial quotient is just a bookkeeping trick to express the finite product n(n−1)⋯(n−r+1)n(n-1)\cdots(n-r+1) compactly using the identity n!=n(n−1)⋯(n−r+1)⋅(n−r)!n! = n(n-1)\cdots(n-r+1)\cdot (n-r)!.

Does P(n,r)P(n,r) make sense when r>nr > n?

No. An rr-permutation requires selecting rr distinct elements from a set of only nn elements, and by the pigeonhole principle this is impossible when r>nr > n, since you cannot list more distinct items than exist in the set. By convention P(n,r):=0P(n,r) := 0 for r>nr > n, which is also consistent with treating 1/(n−r)!1/(n-r)! as undefined (or the product n(n−1)⋯(n−r+1)n(n-1)\cdots(n-r+1) as containing a nonpositive factor once r>nr>n, signaling the count is vacuously zero). All the theorem's hypotheses explicitly restrict to 0≤r≤n0 \le r \le n to avoid this degenerate case.

How do permutations relate to combinations?

A combination counts unordered selections; a permutation counts ordered ones. Every rr-element subset (combination) can be arranged in r!r! different orders, each order being a distinct rr-permutation. Hence P(n,r)=(nr)⋅r!P(n,r) = \binom{n}{r} \cdot r!, or equivalently (nr)=P(n,r)/r!\binom{n}{r} = P(n,r)/r!. This identity is the precise bridge to Combinations, and it explains why combination counts are always smaller than or equal to the corresponding permutation counts — dividing by r!r! removes the redundancy from having counted every ordering of the same subset separately.

What happens if the objects being arranged are not all distinguishable?

The clean formula P(n,r)=n!/(n−r)!P(n,r) = n!/(n-r)! assumes all nn objects are distinct; if some are identical, naively applying the formula overcounts arrangements that look the same once identical objects are treated as indistinguishable. The fix, illustrated in the counterexample with the multiset {a,a,b}\{a,a,b\}, is to divide by the factorial of the number of copies of each repeated value — this generalizes to the multinomial coefficient n!/(n1!n2!⋯nk!)n!/(n_1! n_2! \cdots n_k!) when there are kk distinct values with multiplicities n1,…,nkn_1,\dots,n_k summing to nn. This generalization is the direct precursor to the multinomial theorem, a close relative of the Binomial Theorem.

How does the Product Rule guarantee that P(n,r)P(n,r) is exactly n(n−1)⋯(n−r+1)n(n-1)\cdots(n-r+1), rather than just an upper bound?

The key technical point, proved in the theorem's inductive step, is that the number of valid choices for the kk-th slot is exactly n−k+1n-k+1 for every possible sequence of prior distinct choices — not merely at most n−k+1n-k+1. This uniformity (a constant "fiber size" independent of the path taken so far) is precisely the hypothesis the Product Rule needs to multiply stage counts together and get an exact equality rather than a bound. Because finite-set cardinality subtraction is exact (removing k−1k-1 distinct elements from an nn-element set leaves exactly n−(k−1)n-(k-1) elements, always), the equality is exact at every stage, and hence the final product is exact too.

Why do textbooks emphasize permutations before combinations, rather than the reverse?

Permutations are conceptually more primitive: they count arrangements directly via the Product Rule with no additional correction needed, whereas combinations are defined and computed from permutations by removing the overcounting due to order via the identity (nr)=P(n,r)/r!\binom{n}{r} = P(n,r)/r!. Teaching permutations first gives students the raw building block, and then combinations is naturally introduced as "permutations divided by the redundancy factor r!r!," which is a much smaller conceptual leap than trying to derive (nr)\binom{n}{r} directly from first principles without reference to P(n,r)P(n,r).

Before this

Where this leads