A 4-digit password allows repetition: the code 1111 is valid. How many 4-digit passwords exist? \(10^4 = 10{,}000\). This is the concept of an arrangement with repetition.
In the article on permutations with repetition, we saw how to count orderings of a fixed multiset, where the repeated elements are already given. Now the problem changes: we have \(n\) types of elements available and \(r\) positions to fill, and we may use any type in each position, as many times as we like.
Why arrangements with repetition? #
Counting ordered sequences with repetition is one of the most recurrent operations in computing and mathematics:
- Digital storage systems: the number of values that \(r\) bits can represent is \(AR(2, r) = 2^r\), the basis for computing memory capacity, addressing, and state spaces in hardware.
- Cryptography and passwords: passwords of length \(r\) over an alphabet of \(n\) symbols (with repetition) total \(n^r\) possibilities, the formula that sizes resistance to brute-force attacks.
- Bioinformatics: DNA sequences of length \(r\) over the 4 bases (A, T, C, G) form \(AR(4, r) = 4^r\) sequences, the starting point for estimating sequence diversity in a genome.
- Network protocols: IPv4 addresses are 32-bit sequences, which gives \(AR(2, 32) = 2^{32} \approx 4.3\) billion possible addresses.
- Number systems: the number of patterns representable with \(r\) digits in base \(b\) is \(AR(b, r) = b^r\), unifying binary, decimal, and hexadecimal in a single formula.
From permutation with repetition to arrangement with repetition #
The diagram below expands the decision tree from the previous articles, adding the branch that covers elements with repetition and partial selection:
flowchart TD
A["n types of elements"] --> B{"Repetition
allowed?"}
B -->|"No: all distinct"| C{"Use all?"}
C -->|"Yes"| D["Permutation
P_n = n!"]
C -->|"No: choose r"| E{"Does order matter?"}
E -->|"Yes"| F["Arrangement
A(n,r) = n!/(n-r)!"]
E -->|"No"| G["Combination
C(n,r) = n!/(r!(n-r)!)"]
B -->|"Yes: with repetition"| H{"Use all?"}
H -->|"Yes: fixed multiset"| I["Permutation with Repetition
n!/(n₁!·n₂!·…·nₖ!)"]
H -->|"No: choose r positions"| J["Arrangement with Repetition
AR(n,r) = nʳ"]
Arrangement with Repetition #
An arrangement with repetition of \(n\) elements taken \(r\) at a time is an ordered sequence of \(r\) elements in which each element may be chosen more than once:
$$AR(n, r) = n^r$$Justification: each of the \(r\) positions has \(n\) independent choices. By the product rule: \(\underbrace{n \times n \times \cdots \times n}_{r} = n^r\).
Key difference: in the arrangement without repetition, \(r \leq n\). In the arrangement with repetition, \(r\) can be greater than \(n\), and we can fill more positions than there are available types, thanks to repetition.
Reading It as a Cartesian Product #
If \(A = \{a_1, \ldots, a_n\}\), the arrangements with repetition of \(n\) elements taken \(r\) at a time correspond to the elements of:
$$\underbrace{A \times A \times \cdots \times A}_{r \text{ factors}}$$and therefore there are \(|A|^r = n^r\) arrangements. In Python,
itertools.product(A, repeat=r) generates exactly this set.
Worked Examples #
Passwords of 2 symbols out of 8 available #
Problem: A lock uses symbols from an alphabet of 8 characters. How many passwords of 2 symbols exist if repetition is allowed? And without repetition?
Solution: With repetition, each position has 8 independent choices:
$$AR(8, 2) = 8^2 = \mathbf{64}$$This includes repeated pairs such as (A, A). Without repetition (simple arrangement), the 2nd position excludes the symbol already used: \(A(8,2) = 8 \times 7 = 56\). The difference of 8 corresponds exactly to the 8 pairs of the form (Xᵢ, Xᵢ).
Python: itertools.product for arrangements with repetition
itertools.product for arrangements with repetition
itertools.product(iterable, repeat=r) generates all arrangements with
repetition of \(r\) elements of an iterable, exactly \(n^r\) tuples:
from itertools import product, permutations
symbols = "ABCDEFGH" # 8 symbols
# AR(8, 2) = 8^2 = 64: all pairs with repetition allowed
arrangements = list(product(symbols, repeat=2))
print(len(arrangements)) # 64
print(arrangements[:4]) # [('A', 'A'), ('A', 'B'), ('A', 'C'), ('A', 'D')]
# A(8, 2) = 56: without repetition
without_rep = list(permutations(symbols, 2))
print(len(without_rep)) # 56The difference between product(S, repeat=r) and permutations(S, r) is
exactly the difference between arrangement with and without repetition: the
first allows the same symbol to appear in more than one position; the
second does not.
3-digit sequences from \(\{1,2,3,4,5\}\) #
Problem: How many 3-digit sequences can be formed with the elements of \(\{1,2,3,4,5\}\), allowing repetition?
Solution: Since repetition is allowed, each position is filled independently of the others, and the choice for the 1st position does not restrict the options for the 2nd or the 3rd. By the product rule:
$$AR(5, 3) = \underbrace{5 \times 5 \times 5}_{3\text{ positions}} = 5^3 = \mathbf{125}$$Sequences such as (3, 3, 3) or (1, 5, 1) are valid and are all counted.
Vehicle license plates (3 letters + 4 digits, with repetition) #
Problem: How many distinct vehicle license plates can be formed in the format of 3 letters followed by 4 digits, with repetition allowed?
Solution: The choices of letters and digits are independent of each other. By the product rule:
$$AR(26, 3) \times AR(10, 4) = 26^3 \times 10^4 = 17{,}576 \times 10{,}000 = \mathbf{175{,}760{,}000}$$RGB color palette #
Problem: Monitors and digital images represent colors as combinations of three channels: red (R), green (G), and blue (B). In the 8-bit-per-channel standard (called true color), each channel accepts intensities from 0 to 255, that is, 256 possible values. How many distinct colors can be represented? And on a display with 4 bits per channel, where each channel goes from 0 to 15?
Solution: The three channels are chosen independently; there is repetition (two channels can have the same intensity, as in R = G = 128 for gray). By the product rule:
| Format | Intensities per channel | Total colors |
|---|---|---|
| 8 bits per channel (true color) | 256 (from 0 to 255) | \(AR(256, 3) = 256^3 = 16{,}777{,}216\) |
| 4 bits per channel | 16 (from 0 to 15) | \(AR(16, 3) = 16^3 = 4{,}096\) |
The difference between the two formats is enormous: doubling the number of bits per channel multiplies the number of intensities by 16 (from 16 to 256) and the total number of colors by \(16^3 = 4{,}096\). The total goes from \(4{,}096\) to \(4{,}096^2 = 16{,}777{,}216\), that is, from a little over 4 thousand to almost 17 million colors.
Python: enumerating colors and counting with itertools.product
itertools.product
itertools.product(range(n), repeat=3) generates all (R, G, B) triples with
intensities from 0 to n−1, exactly the \(n^3\) arrangements with repetition
of 3 positions over an alphabet of \(n\) symbols:
from itertools import product
# Counting by formula
for bits_per_channel in [4, 8]:
n = 2 ** bits_per_channel # intensities per channel
total = n ** 3 # AR(n, 3)
total_fmt = f"{total:_}".replace("_", ",") # comma as thousands separator
print(f"{bits_per_channel} bits/channel: {n} intensities → {total_fmt} colors")
# 4 bits/channel: 16 intensities → 4,096 colors
# 8 bits/channel: 256 intensities → 16,777,216 colors
# Generating the first colors of a 4-bit palette (n=16)
palette_4bits = list(product(range(16), repeat=3))
print(len(palette_4bits)) # 4096
print(palette_4bits[:4]) # [(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 0, 3)]
# In CSS, colors are written as #RRGGBB in hexadecimal
def to_hex(r, g, b):
return f"#{r:02X}{g:02X}{b:02X}"
print(to_hex(255, 128, 0)) # #FF8000 (orange)
print(to_hex(0, 0, 0)) # #000000 (black)For the 8-bit-per-channel format, materializing the full list would take considerable memory (16 million triples). The formula \(256^3\) gives the total in constant time: this is when combinatorics replaces enumeration.
Comparison: Arrangement without vs. with Repetition #
The table below summarizes the essential differences between the two kinds of arrangement:
| Type | Repetition? | \(r > n\) allowed? | Formula |
|---|---|---|---|
| Arrangement without repetition | No | No | \(\dfrac{n!}{(n-r)!}\) |
| Arrangement with repetition | Yes | Yes | \(n^r\) |
Application: Computational Representation of Numbers #
Every floating-point system stores a number as a sequence of positions, each filled with a symbol from a fixed alphabet. How many distinct numbers the system can represent is, therefore, a count of arrangements with repetition: the base of the alphabet raised to the number of positions.
What varies between systems is the base used: modern computers use base 2 (binary), following the IEEE 754 standard; many scientific calculators of the 1970s and 1980s used base 10 (decimal), storing each digit directly in BCD (Binary Coded Decimal). The advantage of BCD is that the number shown on the display is identical to the number stored, avoiding the decimal ↔ binary conversion errors that affect IEEE 754 (such as the famous \(0.1 + 0.2 \neq 0.3\)). The cost is space: BCD takes more memory than plain binary for the same range of values.
The two examples below illustrate this difference.
For a complete treatment of the IEEE 754 standard and of rounding errors in binary, see the article Inside IEEE 754 and the article on base conversion for real numbers.
Intel 8087 (binary floating point, 32-bit format):
The Intel 8087 coprocessor (1980) works internally with 80-bit numbers, but it also reads and writes the 32-bit and 64-bit formats that would later be standardized by IEEE 754. In the 32-bit single-precision format, each position is a bit, with an alphabet of 2 symbols (0 or 1). The total number of distinct patterns is:
$$AR(2, 32) = 2^{32} = 4{,}294{,}967{,}296 \text{ bit patterns}$$(Not all of them correspond to “useful” numbers: some bits encode the sign, the exponent, and the significand, and certain patterns represent special values such as infinity and NaN (Not a Number). The arrangement counts the patterns; interpreting them is the job of the IEEE 754 standard.)
HP-11C calculator (decimal floating point):
The HP-11C (1981) uses BCD: each position stores a decimal digit (from 0 to 9), not a bit. Numbers have a 10-digit significand and a 2-digit exponent, each with its own sign, and the storage format has three independent parts:
| Component | Positions | Alphabet | Count |
|---|---|---|---|
| Sign of the significand and of the exponent | 2 (one each) | \(\{+, -\}\) → 2 symbols | \(AR(2,2) = 2^2 = 4\) |
| Exponent (characteristic) | 2 decimal digits | \(\{0,\ldots,9\}\) → 10 symbols | \(AR(10,2) = 10^2 = 100\) |
| Normalized significand | 10 digits | 1st digit from 1 to 9; others from 0 to 9 | \(9 \times 10^9\) |
The significand is normalized: the 1st digit is always nonzero (from 1 to 9), since a leading zero would be redundant, as the number could be rewritten with a smaller exponent. This reduces the options for the 1st digit from 10 to 9, exactly as in counting 3-digit numbers that exclude those with a leading zero.
The total number of distinct configurations is:
$$4 \times 10^2 \times 9 \times 10^9 = 36 \times 10^{11} = 3{,}600{,}000{,}000{,}000$$That is 3.6 trillion configurations. Each digit and each sign takes 4 bits, and each HP-11C register has 14 such groups: the sign and the 10 digits of the significand, plus 3 groups for the exponent and its sign, which gives 56 bits in total. The same 56 bits, used as plain binary, would give \(2^{56} \approx 7.2 \times 10^{16}\) patterns, about 20 thousand times more. That is the cost of BCD: each decimal digit spends 4 bits, which could distinguish 16 values, to store only 10.
The figure below puts the two formats one over the other, on the same bit scale:
Summary Table #
| Concept | Result |
|---|---|
| Arrangements with repetition of \(n\) types taken \(r\) at a time | \(AR(n, r) = n^r\) |
| Arrangement without repetition | \(A(n,r) = \dfrac{n!}{(n-r)!}\) |
| Can \(r\) exceed \(n\)? | Yes, in the arrangement with repetition; no, in the one without |
| Cartesian product \(A \times \cdots \times A\) (\(r\) factors) | \(|A|^r = n^r\) arrangements |
Exercises #
The exercises below apply the formula \(AR(n,r) = n^r\) in different contexts: direct counting, counting with position restrictions, and the complement method. They are ordered from simplest to most complex.
Exercise 1: 3-digit numbers from \(\{2,3,5,8,9\}\) with repetition
(a) Total. (b) Less than 800. (c) Multiples of 5. (d) Even. (e) Odd.
Solution
(a) With no restriction, each position can be any of the 5 elements:
$$AR(5,3) = 5^3 = \mathbf{125}$$(b) For the number to be less than 800, the hundreds digit must be less than 8. In the set \(\{2,3,5,8,9\}\), the elements less than 8 are \(\{2,3,5\}\), that is, 3 options. The other two positions remain free (5 options each):
$$3 \times 5 \times 5 = 3 \times 25 = \mathbf{75}$$(c) A multiple of 5 ends in 0 or 5. From the set \(\{2,3,5,8,9\}\), only 5 satisfies this condition: the units digit is fixed. The other two positions have 5 options each:
$$5 \times 5 \times 1 = \mathbf{25}$$(d) An even number ends in an even digit. The even ones in the set are \(\{2,8\}\), that is, 2 options for the units digit. The other two positions have 5 options each:
$$5 \times 5 \times 2 = \mathbf{50}$$(e) By complement with respect to the total: even + odd = 125. Alternatively, the odd ones in the set are \(\{3,5,9\}\), that is, 3 options for the units digit:
$$5 \times 5 \times 3 = \mathbf{75}$$Check: \(50 + 75 = 125\) ✓
Exercise 2: 5-letter words with A but not as the first letter
With an alphabet of 26 letters and repetition allowed, how many 5-letter words contain A, but not as the first letter?
Solution
Directly counting “has A in at least one of positions 2 to 5” would require handling many overlapping cases. The nested complement strategy is cleaner:
Define two sets:
- \(U\) = words without A in the 1st position: the 1st position has 25 options (any letter except A); the other 4 positions accept any of the 26 letters. So \(|U| = 25 \times 26^4\).
- \(B\) = words without A in any position: all 5 positions have 25 options. So \(|B| = 25^5\).
Note that \(B \subset U\): every word with no A anywhere also has no A in the 1st position. The difference \(|U| - |B|\) gives exactly the words without A in the 1st position but with A in some of positions 2 to 5, which is what the problem asks:
$$|U| - |B| = 25 \times 26^4 - 25^5 = 25(26^4 - 25^4) = \mathbf{1{,}658{,}775}$$
Exercise 3: 5-digit numbers that contain the digit 2
(a) That contain the digit 2. (b) That do not contain the digit 2.
Solution
Total 5-digit numbers: the 1st digit cannot be zero (otherwise the number would have fewer than 5 digits), so it has 9 options (from 1 to 9); each of the other 4 digits has 10 options (from 0 to 9):
$$9 \times 10^4 = \mathbf{90{,}000}$$(b) Without the digit 2: we remove 2 from the available alphabet. The 1st digit cannot be 0 or 2, leaving \(\{1,3,4,5,6,7,8,9\}\), that is, 8 options. Each of the other 4 digits can be any digit except 2, that is, \(\{0,1,3,4,5,6,7,8,9\}\), with 9 options each:
$$8 \times 9^4 = 8 \times 6{,}561 = \mathbf{52{,}488}$$(a) Directly counting the numbers with at least one digit 2 would require adding up many overlapping cases. By complement:
$$90{,}000 - 52{,}488 = \mathbf{37{,}512}$$
Exercise 4: Anagrams with and without repetition
With \(\{a,b,c,d,e\}\), how many 3-letter “anagrams” exist: (a) With distinct letters. (b) With at least 2 equal letters.
Solution
(a) With distinct letters, no position can repeat the letter already used, which characterizes an arrangement without repetition:
$$A(5,3) = 5 \times 4 \times 3 = \mathbf{60}$$(b) Counting directly would require handling “exactly 2 equal” and “all 3 equal” separately. The complement is more direct: \(AR(5,3)\) counts all 3-letter sequences with repetition allowed; \(A(5,3)\) counts exactly those whose letters are all distinct. The difference is the sequences with at least 2 equal letters:
$$AR(5,3) - A(5,3) = 125 - 60 = \mathbf{65}$$Next steps #
Arrangements with repetition count ordered sequences where elements repeat. The limitation that remains is order: what about when it does not matter but repetition is allowed? This case, in which we select a subset of \(r\) elements with replacement among \(n\) available types, without regard to the sequence, leads to combinations with repetition, the topic of the next article in the series.
