How many anagrams does the word MAMBEMBE have? A plain \(8!\) overestimates: swapping the two letters B produces the same anagram, not a new one. When there are repeated elements, we need to divide to compensate.
In the article on combinations, we closed the classic triad of groupings with distinct elements. Now we take the next step: what happens when the elements repeat?
Why permutations with repetition? #
Counting orderings with repeated elements shows up often in computing and data science:
- Anagrams: counting the distinct anagrams of a word with repeated letters (such as MISSISSIPPI) is the textbook problem for this formula.
- Bioinformatics: DNA sequences are made of four bases (A, T, C, G) that repeat. The number of distinct sequences of length \(n\) with a fixed composition is a permutation with repetition.
- Grid paths: the number of shortest paths between two points of an obstacle-free grid is a permutation with repetition of horizontal and vertical moves.
- Statistics: the multinomial coefficient \(\dfrac{n!}{n_1! n_2! \cdots n_r!}\) (which is exactly this formula) appears in the multinomial distribution, which generalizes the binomial distribution to more than two possible outcomes.
From combination to permutation with repetition #
The diagram below expands the decision tree from the previous article, adding the branch that covers repeated elements:
flowchart TD
A["n elements"] --> B{"All distinct?"}
B -->|"Yes"| 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 -->|"No: there are repeats"| H["Permutation with Repetition
n! / (n₁! · n₂! · … · nᵣ!)"]
The Central Idea: Removing the Overcount #
Imagine 5 pens: 2 white (W¹ and W²), 1 blue, 1 black, 1 green. If we treat the two white ones as distinct, we get \(5!\) distributions. But W¹=white and W²=white are the same thing to whoever receives them: each real distribution was counted \(2!\) times.
Correct number: \(\dfrac{5!}{2!} = 60\).
Permutation with Repetition #
Given a set of \(n\) elements, of which \(n_1\) are equal to type 1, \(n_2\) to type 2, …, \(n_r\) to type \(r\), with \(n_1 + n_2 + \cdots + n_r = n\), the number of distinct arrangements (permutations) is:
$$P_n^{(n_1, n_2, \ldots, n_r)} = \frac{n!}{n_1! n_2! \cdots n_r!}$$Intuition: we start with the \(n!\) orderings of all the elements as if they were distinct. We divide by \(n_i!\) for each group of equal elements, which permute among themselves without creating anything new.
Worked Examples #
Numbers formed with 1,1,1,3,3,9 #
Problem: How many distinct 6-digit numbers can be formed with the digits 1, 1, 1, 3, 3, 9?
Solution:
Via the formula:
$$\frac{6!}{3! 2! 1!} = \frac{720}{12} = 60$$Via choosing positions: choose 3 positions (out of 6) for the 1s: \(C(6,3) = 20\). Then 2 positions (out of the 3 remaining) for the 3s: \(C(3,2) = 3\). The 9 takes the last one: \(C(1,1) = 1\). Total: \(20 \times 3 \times 1 = 60\) ✓
Anagrams of MAMBEMBE #
Letters: M (3×), B (2×), E (2×), A (1×), 8 letters in total.
$$P_8^{(3,2,2,1)} = \frac{8!}{3! 2! 2! 1!} = \frac{40{,}320}{24} = \mathbf{1{,}680}$$
Python: math.factorial and collections.Counter
math.factorial and collections.Counter
Python lets you compute the formula directly with math.factorial, or use
sympy.factorial to work symbolically. The most idiomatic pattern combines
collections.Counter to count the frequencies with math.prod to compute the
denominator:
from math import factorial
from collections import Counter
from math import prod
def permutations_with_repetition(word: str) -> int:
n = len(word)
frequencies = Counter(word).values()
return factorial(n) // prod(factorial(k) for k in frequencies)
print(permutations_with_repetition("MAMBEMBE")) # 1680
print(permutations_with_repetition("MISSISSIPPI")) # 34650Counter returns a dictionary {letter: count}, exactly the \(n_i\) of the
formula. prod(factorial(k) for k in ...) computes the denominator without
having to name each frequency individually.
Tournament with 15 matches: 7 wins, 5 losses, 3 draws #
How many possible sequences of results are there?
$$\frac{15!}{7! 5! 3!} = \mathbf{360{,}360}$$Binary sequences with three 1s and five 0s #
How many 8-bit sequences have exactly three 1s and five 0s?
$$P_8^{(3,5)} = \frac{8!}{3! 5!} = \binom{8}{3} = \mathbf{56}$$This result reveals an important equivalence:
Any sequence with \(k\) symbols of one type and \(m\) symbols of another type, regardless of what those symbols are, has exactly
$$P_{k+m}^{(k, m)} = \frac{(k+m)!}{k! m!} = \binom{k+m}{k}$$distinct arrangements. In the example above, \(k = 3\) (ones) and \(m = 5\) (zeros), giving \(\binom{8}{3} = 56\). This is the binomial coefficient, which gets its own article later in this series. This formula reappears whenever a problem boils down to placing two types of symbols in sequence, like the stars and bars method, which will be covered in the article on combinations with repetition.
Python: itertools.combinations for binary sequences
itertools.combinations for binary sequences
Generating all binary sequences of length 8 with exactly three 1s is
equivalent to choosing which 3 positions (out of 8) receive the value 1, that
is, a combination. itertools.combinations does exactly that:
from itertools import combinations
from math import comb
n, k = 8, 3
# Count directly through the equivalence with C(n, k)
print(comb(n, k)) # 56
# Generate all sequences: each tuple gives the positions of the 1s
positions = list(combinations(range(n), k))
print(len(positions)) # 56
# Convert to binary strings
def to_binary(pos, n):
seq = ['0'] * n
for i in pos: seq[i] = '1'
return ''.join(seq)
sequences = [to_binary(p, n) for p in positions]
print(sequences[:4]) # ['11100000', '11010000', '11001000', '11000100']Shortest grid paths: from (0,0) to (4,3) #
Move only up (U) or to the right (R), in 7 steps (4R and 3U). The figure below shows two of the 35 possible paths: the blue path goes up first and then to the right; the yellow one does the opposite.
Why is the count the same as for anagrams? Because each shortest path is a 7-letter word with four R and three U, read from left to right as a list of steps, and each such word describes a path. The figure below shows this correspondence letter by letter for RURRURU, one of the 35 anagrams of RRRRUUU (the same four R and three U letters, in another order):
Anagrams of MAMBEMBE starting with a vowel #
Problem: How many anagrams of MAMBEMBE have a vowel in the first position?
Solution: The available vowels are A, E, E. The cases are disjoint according to the initial vowel.
Case 1 (starts with A): the remaining ones are M,M,M,B,B,E,E (7 letters):
$$N_1 = \frac{7!}{3! 2! 2!} = \mathbf{210}$$Case 2 (starts with E): the remaining ones are M,M,M,A,B,B,E (7 letters):
$$N_2 = \frac{7!}{3! 1! 2! 1!} = \mathbf{420}$$Total (sum rule, disjoint cases): \(210 + 420 = \mathbf{630}\)
Anagrams of MAMBEMBE with all the Ms apart #
Problem: How many anagrams of MAMBEMBE have the three Ms in positions that are not adjacent to each other?
Solution:
Step 1: order the 5 non-M letters: A, B, B, E, E.
$$\frac{5!}{2! 2! 1!} = 30 \text{ orderings}$$Step 2: each ordering has 6 gaps (before, between, and after the letters). Insert 3 Ms into 3 distinct gaps (so they are not adjacent):
$$C(6, 3) = 20$$Total: \(30 \times 20 = \mathbf{600}\)
Summary Table #
| Type | Equal elements? | Formula |
|---|---|---|
| Permutation | No | \(P_n = n!\) |
| Permutation with repetition | Yes | \(\dfrac{n!}{n_1! n_2! \cdots n_r!}\) |
| Special case: two types | Yes (two groups) | \(\dfrac{n!}{k! (n-k)!} = \dbinom{n}{k}\) |
Exercises #
The following exercises cover the main techniques of the article: direct application of the formula, cases with position restrictions, and grid paths. They are ordered from simplest to most complex.
Exercise 1: Numbers with repeated digits
How many 7-digit numbers can be formed with \(1, 3, 6, 6, 6, 8, 8\)? (a) With no restrictions. (b) Greater than 6,000,000.
Solution
(a) \(\dfrac{7!}{3! 2! 1! 1!} = \dfrac{5{,}040}{12} = \mathbf{420}\)
(b) 1st digit ∈ {6, 8}.
- Starts with 6: the remaining ones are \(6,6,8,8,1,3\) → \(\dfrac{6!}{2! 2! 1! 1!} = 180\)
- Starts with 8: the remaining ones are \(6,6,6,8,1,3\) → \(\dfrac{6!}{3! 1! 1! 1!} = 120\)
Total: \(180 + 120 = \mathbf{300}\)
Exercise 2: 5-digit subsets of \(\{1,1,1,1,2,3\}\)
How many 5-digit numbers can be formed by choosing 5 of the 6 digits \(1,1,1,1,2,3\)?
Solution
Disjoint groups (which 5 of the 6 we use):
- \(\{1,1,1,1,2\}\): \(\dfrac{5!}{4!} = 5\)
- \(\{1,1,1,1,3\}\): \(\dfrac{5!}{4!} = 5\)
- \(\{1,1,1,2,3\}\): \(\dfrac{5!}{3!} = 20\)
Total: \(5 + 5 + 20 = \mathbf{30}\)
The next two exercises use the same map. The figure below shows the grid with points A, B, and C marked and, anticipating Exercise 4, highlights one possible path from A to C (in blue) and one from C to B (in yellow):
Exercise 3: Shortest grid paths
On a map with 7 N-S (North-South, that is, vertical) avenues and 6 E-W (East-West, that is, horizontal) avenues, how many shortest routes are there from the bottom-left corner (A) to the top-right corner (B)?
Solution
With 7 N-S avenues there are 6 horizontal blocks to cross (6 moves to the right); with 6 E-W avenues there are 5 vertical blocks to cross (5 moves up). Any path that only moves forward (never backtracks) uses exactly these 11 steps, so 11 is the minimum length:
$$\frac{11!}{6! 5!} = C(11,6) = \mathbf{462}$$
Exercise 4: Shortest paths through C
On the same map, how many routes A→B pass through the point C located 4 blocks to the right and 4 up from A?
Solution
- A→C: 4R + 4U = \(\dfrac{8!}{4! 4!} = 70\)
- C→B: 2R + 1U = \(\dfrac{3!}{2! 1!} = 3\)
Total: \(70 \times 3 = \mathbf{210}\)
Next steps #
Permutation with repetition solves the case where we use all \(n\) elements, repeated ones included. The limitation that remains is this requirement of using all of them: what if we want to choose only \(r < n\) elements from a set with repetitions allowed, and order still matters?
This case, in which we select \(r\) elements with replacement among \(n\) available types, leads to arrangements with repetition, the topic of the next article in the series.
