• Practice
  • About 20 min
  • 5 practice questions

Permutations with restrictions and repeated objects

Arrange objects that must stay together or apart, find the rank of a word in dictionary order, arrange objects that are not all different, and add up all numbers formed from given digits.

If something looks wrong, please tell us.

By the end of this lesson you can

  • Use the string method when some objects must be together.
  • Use the gap method when no two of some objects may be together.
  • Find the rank of a word among all arrangements of its letters in dictionary order.
  • Count arrangements of n objects with p₁ alike of one kind, p₂ of another, ...: n!/(p₁! p₂! ...).
  • Find the sum of all numbers formed from given digits.

Real arrangements come with conditions: friends who want to sit together, people who must not sit side by side, letters that repeat. This lesson gives a method for each condition. Each method is the product rule applied in a clever order.

Objects always together: the string method

To arrange n different objects so that m particular objects are always together, tie the m objects into one bundle. Now there are n − m + 1 units, which can be arranged in (n − m + 1)! ways. Inside the bundle the m objects can be arranged in m! ways. The answer is m! × (n − m + 1)!.

Worked example 1: vowels together

In how many arrangements of the letters of MOTHER are the vowels O and E together? Working: bundle O and E. The units are M, T, H, R and [OE]: 5 units, arranged in 5! = 120 ways. Inside the bundle, OE or EO: 2! = 2 ways. Answer: 120 × 2 = 240. All arrangements number 6! = 720, so the vowels are not together in 720 − 240 = 480 of them.

No two together: the gap method

To arrange objects so that no two of k given objects are next to each other, first arrange the other m objects in m! ways. They create m + 1 gaps, counting both ends: _ X _ X _ X _. Place the k restricted objects in different gaps, in ⁽ᵐ⁺¹⁾Pₖ ways. The answer is m! × ⁽ᵐ⁺¹⁾Pₖ.

Together or apart?

  • Always together: string method
    • Tie the m objects into one unit
    • Arrange n − m + 1 units
    • Arrange inside the unit: m!
    • m! × (n − m + 1)!
  • Never two together: gap method
    • Arrange the m free objects: m!
    • They make m + 1 gaps
    • Put the k objects in different gaps
    • m! × ⁽ᵐ⁺¹⁾Pₖ
Note: 'not all together' is total minus 'all together'; 'no two together' needs the gap method.

Worked example 2: seating with gaps

In how many ways can 6 boys and 3 girls sit in a row so that no two girls are together? Working: seat the boys first: 6! = 720 ways. The 6 boys make 7 gaps. Choose ordered gaps for the 3 girls: ⁷P₃ = 7 × 6 × 5 = 210. Answer: 720 × 210 = 151200.

Worked example 3: alternating

3 boys and 3 girls stand in a line, boys and girls alternating. If a boy stands first, the pattern is B G B G B G: the boys fill their 3 places in 3! = 6 ways and the girls theirs in 3! = 6 ways, giving 36. If a girl stands first, again 36. By the sum rule there are 36 + 36 = 72 lines.

Rank of a word in dictionary order

List all arrangements of the letters of a word in dictionary (lexicographic) order. The rank of the word is its position in this list. To find it, do not list everything: count the blocks of words that come before it, letter by letter.

Worked example 4: the rank of MANGO

The letters in alphabetical order are A, G, M, N, O. Words starting with A: the other 4 letters in 4! = 24 ways. Starting with G: 24 more. Now words starting with M. Second letter A (the smallest): MA, then G, N, O remain. Words MAG _ _: 2! = 2. Next come MAN _ _, and the first of them is MANGO itself (G before O). Rank = 24 + 24 + 2 + 1 = 51.

Permutations when some objects are alike

Arrange the letters of TOO. If the two O's were different, O₁ and O₂, there would be 3! = 6 arrangements, but swapping O₁ and O₂ gives the same visible word, so each word was counted 2! times: there are 6/2 = 3 words (TOO, OTO, OOT). In general, the number of arrangements of n objects in which p₁ are alike of one kind, p₂ alike of another kind, ..., pₖ alike of a k-th kind and the rest different is n!/(p₁! × p₂! × ... × pₖ!).

Worked example 5: repeated letters

(i) ARRANGE has 7 letters with A twice and R twice: 7!/(2! × 2!) = 5040/4 = 1260 arrangements. (ii) COMMITTEE has 9 letters with M, T and E each twice: 9!/(2! × 2! × 2!) = 362880/8 = 45360. (iii) The rank of INDIA. Letters in order: A, D, I, I, N. Starting with A: 4!/2! = 12 (two I's left). Starting with D: 12. Starting with I: second letter A, D or I gives 3! = 6 each, so 18 words. Then IN: third letter A gives 2 words; then IND: INDAI, then INDIA. Rank = 12 + 12 + 18 + 2 + 2 = 46.

Worked example 6: vowels keep their places, and grid paths

(i) Arrange the letters of CHENNAI so that vowels stay in vowel places and consonants in consonant places. The vowels E, A, I fill their 3 places in 3! = 6 ways; the consonants C, H, N, N fill theirs in 4!/2! = 12 ways. Answer: 6 × 12 = 72. (ii) On a grid, how many shortest paths go from one corner to the opposite corner 5 units right and 3 units up? Each path is a string of 5 R's and 3 U's, so there are 8!/(5! × 3!) = 40320/(120 × 6) = 56 paths.

Sum of all the numbers formed

Find the sum of all 3-digit numbers formed from 1, 3, 5, 7 without repetition. There are ⁴P₃ = 24 numbers. Fix a digit in the units place: the other two places can be filled in ³P₂ = 6 ways, so each digit appears 6 times in the units place, and likewise in the tens and hundreds places. The units digits add up to 6 × (1 + 3 + 5 + 7) = 6 × 16 = 96, and the same total sits in the tens and hundreds places. Sum = 96 × (1 + 10 + 100) = 96 × 111 = 10656.

In general, the sum of all r-digit numbers formed from n non-zero digits without repetition is ⁽ⁿ⁻¹⁾Pᵣ₋₁ × (sum of the digits) × 111...1 (r ones). If 0 is one of the digits, subtract the numbers that start with 0: the sum becomes ⁽ⁿ⁻¹⁾Pᵣ₋₁ × S × 111...1 (r ones) − ⁽ⁿ⁻²⁾Pᵣ₋₂ × S × 11...1 (r − 1 ones). For 3-digit numbers from 0, 1, 2, 3 (S = 6): ³P₂ × 6 × 111 − ²P₁ × 6 × 11 = 3996 − 132 = 3864.

Together: m! × (n − m + 1)!. No two together: m! × ⁽ᵐ⁺¹⁾Pₖ. Alike objects: n!/(p₁! p₂! ... pₖ!).

— Restricted arrangements

Key takeaways: bundle objects that must be together and remember the arrangements inside the bundle; seat the free objects first and use the gaps for objects that must be apart; divide by p! for every group of p identical objects; and for a rank, count whole blocks of words that come before, one letter at a time.

Check your understanding

  1. 1. How many different arrangements are there of the letters of the word LEVEL?

    1. 120
    2. 60
    3. 30
    4. 20
    Show answer

    Answer: C. LEVEL has 5 letters: L twice, E twice and V once. The count is 5!/(2! × 2!) = 120/4 = 30.

  2. 2. In how many ways can 4 boys and 3 girls sit in a row so that no two girls sit together?

    1. 1440
    2. 5040
    3. 720
    4. 144
    Show answer

    Answer: A. Seat the 4 boys: 4! = 24 ways. They make 5 gaps. Put the 3 girls in different gaps: ⁵P₃ = 5 × 4 × 3 = 60 ways. Total 24 × 60 = 1440. 5040 = 7! has no restriction.

  3. 3. In how many arrangements of the letters of SCHOOL are the two O's together?

    1. 240
    2. 120
    3. 60
    4. 720
    Show answer

    Answer: B. Treat OO as one unit. The units S, C, H, L and OO are all different: 5! = 120 arrangements. Inside the unit, the two identical O's give only 2!/2! = 1 order, so the answer is 120, not 240.

  4. 4. The letters of DEAF are arranged in all possible ways and listed in dictionary order. What is the rank of DEAF?

    1. 12
    2. 10
    3. 8
    4. 9
    Show answer

    Answer: D. Letters in order: A, D, E, F. Words starting with A: 3! = 6. Starting with D: DA _ _ gives 2! = 2 words; then DE _ _, whose first word is DEAF (A before F). Rank = 6 + 2 + 1 = 9.

  5. 5. How many shortest paths are there on a grid from one corner to the point 4 units right and 2 units up?

    1. 30
    2. 8
    3. 15
    4. 24
    Show answer

    Answer: C. Every shortest path is a string of 4 R's and 2 U's, so the count is 6!/(4! × 2!) = 720/(24 × 2) = 15.

Privacy · Terms · Refunds · Delivery