Arrangements: Ordering Without Using Everything

In a race with 10 participants, in how many ways can the podium (1st, 2nd, 3rd place) be filled? Here we use only 3 of the 10 athletes, and order matters (1st ≠ 2nd). This is an arrangement (also called an r-permutation).

Why arrangements?

#

Selecting and ordering a subset of elements, without necessarily using all of them, is a core operation in computing and mathematics:

• Security: passwords of length \(r\) with no repetition, drawn from an alphabet of \(n\) symbols, add up to \(A(n, r)\) possibilities, and the arrangement sizes the space a brute-force attacker has to search.
• License plates and unique identifiers: alphanumeric systems with no repeated characters use the arrangement to compute how many distinct identifiers can be issued, exactly the example solved below.
• Scheduling: ordering \(r\) processes out of \(n\) available in a priority queue corresponds to \(A(n, r)\) possible sequences.
• Routes and graphs: the number of simple paths that go through \(r\) distinct vertices, in order, in a complete graph with \(n\) vertices is \(A(n, r)\), the basis of state-space search algorithms.
• Rankings: podiums, ordered recommendation lists, and tournament results are arrangements, because it matters who was chosen and in which position.

From permutation to arrangement

#

The permutation, covered in the previous article, orders all \(n\) elements. The arrangement relaxes that requirement: we order only \(r < n\) of them. The diagram below places the arrangement in the family of groupings:

flowchart TD
    A["n distinct elements"] --> B{"Use all of them?"}
    B -->|"Yes"| C["Permutation
P_n = n!"]
    B -->|"No: choose r < n"| D{"Does order matter?"}
    D -->|"Yes"| E["Arrangement
A(n,r) = n!/(n-r)!"]
    D -->|"No"| F["Combination
(next article)"]

Arrangement

#

In the international literature, the same number usually appears as \(P(n, r)\) or \({}_{n}P_{r}\), from permutation, and it is the nPr key on scientific calculators.

Notable cases:

• \(A(n, n) = n!\), the same as the permutation \(P_n\)
• \(A(n, 1) = n\)

Back to the opening example: the podium of a race with 10 athletes has \(A(10, 3) = 10 \times 9 \times 8 = 720\) distinct configurations.

The figure below shows where this product comes from. Each podium place is a little box with the number of athletes still available for it, and each filled place leaves one athlete fewer for the following ones; in the general case, the \(r\) boxes carry \(n, n-1, \ldots, n-r+1\):

Worked Examples

#

Building with 8 floors: distinct (entry, exit) pair

#

Problem: A building has 8 floors. A person gets in the elevator on one floor and gets out on a different one. In how many distinct ways can this ordered (entry, exit) pair occur?

Solution: We want to choose 2 distinct floors out of 8, where order matters, since getting in at the 3rd and out at the 7th is different from getting in at the 7th and out at the 3rd. This is an arrangement of 8 elements taken 2 at a time.

We fill the two positions sequentially:

CREATE TABLE floors (floor INT);
INSERT INTO floors VALUES (1),(2),(3),(4),(5),(6),(7),(8);

SELECT a.floor AS entry, b.floor AS exit
FROM   floors a
CROSS JOIN floors b
WHERE  a.floor <> b.floor
ORDER BY entry, exit;
-- 56 rows = A(8, 2)

SELECT COUNT(*)
FROM   floors a
CROSS JOIN floors b
WHERE  a.floor <> b.floor;
-- 56

Schedule of 3 activities out of 4

#

Problem: A student has 4 activities available: reading (R), exercise (E), drawing (D), and cooking (C). They want to put together a daily schedule with 3 of these activities in a fixed sequence: order matters, because it determines what they will do in the morning, afternoon, and evening. In how many distinct ways can they put together this schedule?

Solution: We want to select and order 3 distinct activities out of 4. We fill the three positions sequentially, with no repetition:

Routes among 5 cities: ordered route of 3 cities

#

Problem: A traveler needs to plan a route that goes through exactly 3 cities among São Paulo, Rio de Janeiro, Belo Horizonte, Porto Alegre, and Curitiba. The order of the cities visited determines the route: SP → RJ → BH is different from RJ → SP → BH. How many distinct routes can they plan?

Solution: We want an ordered sequence of 3 distinct cities chosen from 5. We fill the three stages of the route sequentially:

import itertools, math

# A(5, 3) — routes of 3 cities among 5
cities = ["SP", "RJ", "BH", "POA", "CWB"]
routes = list(itertools.permutations(cities, 3))
print(len(routes))                         # 60

# Confirm with the formula
def arrangement(n, r):
    return math.factorial(n) // math.factorial(n - r)

print(arrangement(5, 3))                   # 60

CREATE TABLE cities (city TEXT);
INSERT INTO cities VALUES ('SP'),('RJ'),('BH'),('POA'),('CWB');

SELECT a.city AS origin,
       b.city AS stopover,
       c.city AS destination
FROM   cities a
CROSS JOIN cities b
CROSS JOIN cities c
WHERE  a.city <> b.city
  AND  b.city <> c.city
  AND  a.city <> c.city
ORDER BY origin, stopover, destination;

SELECT COUNT(*)
FROM   cities a
CROSS JOIN cities b
CROSS JOIN cities c
WHERE  a.city <> b.city
  AND  b.city <> c.city
  AND  a.city <> c.city;
-- 60 = A(5, 3)

License plates: 3 letters and 4 distinct digits

#

Problem: A plate system uses the format AAA-NNNN, with 3 letters of the alphabet (26 letters) followed by 4 digits (from 0 to 9). No letter may repeat in the 3 letter positions, and no digit may repeat in the 4 digit positions. How many distinct plates can be issued?

Solution: Choosing the letters and choosing the digits are independent steps, so we apply the Product Rule between the two blocks.

Letter block, \(A(26, 3)\): we select and order 3 distinct letters out of 26.

Digit block, \(A(10, 4)\): we select and order 4 distinct digits out of 10.

Total, by the Product Rule between the two blocks:

3-digit numbers with distinct digits from \(\{0, 1, \ldots, 9\}\)

#

Problem: How many 3-digit numbers (between 100 and 999), with all digits distinct, can be formed with the digits \(\{0, 1, \ldots, 9\}\)?

Solution: The difficulty is the restriction: the 1st digit cannot be 0, otherwise the number would effectively have only 2 digits (e.g., 053 = 53). We present two approaches.

Direct approach (fill the restricted position first):

The strategy is always to start with the position that has a restriction, then fill the others.

Check by complement:

We count all arrangements of 3 distinct digits (including those that start with 0) and subtract the invalid ones:

• Total without restriction: \(A(10, 3) = 10 \times 9 \times 8 = 720\)
• Start with 0: 0 fixed in the 1st position, 2 digits chosen from the remaining 9 → \(A(9, 2) = 9 \times 8 = 72\)

from itertools import permutations

digits = range(10)  # {0, 1, ..., 9}

# All arrangements of 3 distinct digits (including those starting with 0)
all_pins = list(permutations(digits, 3))
print(len(all_pins))  # 720 = A(10, 3)

# Only those valid as a 3-digit number (no 0 in the 1st position)
valid = [p for p in all_pins if p[0] != 0]
print(len(valid))     # 648

# Invalid cases: start with 0 → A(9, 2) arrangements of the 9 remaining digits
invalid = [p for p in all_pins if p[0] == 0]
print(len(invalid))   # 72 = A(9, 2)

# Confirm the complement
assert len(valid) + len(invalid) == len(all_pins)  # 648 + 72 = 720 ✓

Even 4-digit numbers with distinct digits from \(\{0,1,\ldots,9\}\)

#

Problem: How many 4-digit numbers (between 1000 and 9999), with all digits distinct, are even, using the digits \(\{0, 1, \ldots, 9\}\)?

Solution: A number is even when its last digit (units) belongs to \(\{0, 2, 4, 6, 8\}\). We split into two cases according to the final digit, because the restriction on the 1st digit (≠ 0) changes depending on which even digit occupies the last position.

Case I (last digit = 0):

With 0 fixed in the last position, it cannot appear in the 1st, so the restriction on the 1st digit is already satisfied.

Case II (last digit \(\in \{2, 4, 6, 8\}\)):

Now 0 was not used in the last position, so it remains forbidden in the 1st position.

Total, by the Sum Rule between the two cases:

Summary Table: Permutation vs. Arrangement

#

Exercises

#

Next steps

#

The arrangement solves the case where order matters and we use only \(r < n\) elements. Its limitation is exactly that requirement of order: in many practical situations (forming a committee, choosing the ingredients of a recipe, selecting movies to watch) all that matters is which elements were chosen, not in what sequence.

When order does not matter, we arrive at combinations, the next topic in the series. With permutations, arrangements, and combinations we will have the fundamental triad of combinatorics, enough to solve the vast majority of counting problems.