- Advanced
- About 16 min
- 5 practice questions
Rank with repeated letters and the sum of numbers formed
Find the dictionary rank of a word with repeated letters, and find the sum of all numbers formed from given digits, including the case where one digit is 0.
If something looks wrong, please tell us.
The practice course found the rank of a word whose letters are all different. Harder questions use words with repeated letters, where the simple (remaining)! count overcounts. A second advanced favourite asks for the sum of all the numbers that can be formed from given digits, which is impossible to do by listing but quick with a place-value argument. Both rely on counting carefully what happens at one position at a time.
Rank when letters repeat
The method is the same as before, with one change. At each position, consider each different unused letter that is alphabetically smaller than the actual letter. Put it at that position and count the arrangements of the letters that remain, dividing by the factorials of any repeats that remain. Two identical smaller letters are counted once, not twice, because putting either of them there gives the same words.
- Write the multiset of letters in alphabetical order.
- At each position, for each different smaller unused letter, count the arrangements of what would remain: (remaining count)!/(product of factorials of remaining repeats).
- Fix the actual letter, remove one copy of it, and move to the next position.
- Rank = total of all these counts + 1.
Worked example 1: the rank of LETTER
Letters in order: E, E, L, R, T, T. Position 1 is L. The only different smaller letter is E. With an E first, the remaining letters are E, L, R, T, T: 5!/2! = 60 words. Position 2 is E, from E, R, T, T: nothing smaller, 0. Position 3 is T, from E, R, T, T. Smaller letters: E (remaining R, T, T gives 3!/2! = 3) and R (remaining E, T, T gives 3). That is 6. Position 4 is T, from E, R, T: smaller E (remaining R, T: 2) and R (remaining E, T: 2), which is 4. Position 5 is E, from E, R: 0. Words before LETTER: 60 + 0 + 6 + 4 + 0 = 70. Rank = 71.
The sum of all numbers formed
Take n different non-zero digits and form all n! numbers that use each digit once. Look at the units place: each digit sits there in exactly (n − 1)! of the numbers, because the other n − 1 digits can then be arranged freely. So the units digits add up to (n − 1)! × (sum of the digits). The same is true of every place, and the places are worth 1, 10, 100 and so on.
Sum of all n-digit numbers formed from n different non-zero digits, each used once = (n − 1)! × (sum of the digits) × 111…1 (n ones).
Worked example 2: digits 1, 2, 3, 4
There are 4! = 24 numbers. The digit sum is 10. Sum = 3! × 10 × 1111 = 6 × 10 × 1111 = 66,660. A quick check of the average: the numbers run from 1234 to 4321, and 66,660/24 = 2777.5, which lies sensibly in the middle.
Worked example 3: when one digit is 0
Find the sum of all four-digit numbers formed from 0, 1, 2, 3, each used once. First treat 0 as an ordinary digit: all 24 strings sum to 3! × 6 × 1111 = 39,996. But the strings beginning with 0 are really three-digit numbers formed from 1, 2, 3, and they must be removed. Their sum is 2! × 6 × 111 = 1332. Required sum = 39,996 − 1332 = 38,664.
Key takeaways: with repeated letters, count each different smaller letter once and divide by the repeats that remain. For sums of numbers, every digit appears equally often in every place: (n − 1)! times for n different digits. A 0 among the digits is handled by subtracting the strings that begin with 0.
Check your understanding
-
1. All arrangements of the letters of BOOK are listed in dictionary order. What is the rank of BOOK?
- 4
- 2
- 3
- 6
Show answer
Answer: C. Order B, K, O, O. Position 1 B: 0. Position 2 O from K, O, O: K smaller, remaining O, O gives 1. Position 3 O from K, O: K smaller, 1. Rank 0 + 1 + 1 + 1 = 3 (BKOO, BOKO, BOOK).
-
2. All arrangements of the letters of AGAIN are listed in dictionary order. What is the rank of AGAIN?
- 7
- 6
- 8
- 13
Show answer
Answer: A. Order A, A, G, I, N. Position 1 A: 0. Position 2 G from A, G, I, N: A smaller, remaining G, I, N: 3! = 6. Positions 3 and 4 (A, then I from I, N): 0. Rank 6 + 1 = 7.
-
3. What is the sum of all three-digit numbers formed from 1, 3, 5, each digit used once?
- 999
- 1665
- 2664
- 1998
Show answer
Answer: D. (3 − 1)! × (1 + 3 + 5) × 111 = 2 × 9 × 111 = 1998.
-
4. What is the sum of all four-digit numbers formed from 1, 2, 3, 4, each digit used once?
- 6666
- 66,660
- 33,330
- 59,994
Show answer
Answer: B. 3! × 10 × 1111 = 66,660.
-
5. All arrangements of the letters of DADDY are listed in dictionary order. What is the rank of DADDY?
- 4
- 5
- 6
- 11
Show answer
Answer: B. Order A, D, D, D, Y. Position 1 D: A smaller, remaining D, D, D, Y: 4!/3! = 4. Later positions add 0. Rank 4 + 1 = 5.
Sign in to keep track of the lessons you finish.