Skip to content
Tutorials Center
My learning

Topics

Lesson 43 of 86 ยท Permutations, Combinations and Probability

Circular Arrangements and Restrictions

Count seatings around a round table, necklaces, together and apart cases, the rank of a word in a dictionary, and derangements, with runnable checks.

Put five friends in a row and there are 5! ways to do it. Put them around a round table and the count changes, because a seating that is just a rotation of another seating looks the same to everyone at the table. Circular permutations fix that double counting, and they appear in almost every aptitude test that has a counting section.

This lesson covers the circular formula and its necklace variant, the standard restrictions (people who must sit together, apart, or alternate), the rank of a word in the dictionary, and derangements, where nothing lands in its own place. It builds on Counting Principles and Permutations and Combinations.

Why circles divide by n

Take n distinct people. In a row there are n! arrangements. Around a circle, rotating everyone by one seat gives the same seating, and there are n rotations of each arrangement. So the number of different circular arrangements is n! รท n:

Circular permutations of n distinct objects = (n โˆ’ 1)!

Another way to see it: fix one person in a seat as the reference point. The other n โˆ’ 1 people can then be arranged in the remaining seats in (n โˆ’ 1)! ways. Fixing a person is the trick behind almost every circular question.

flowchart LR
    A["Fix one person<br/>as the reference"] --> B["Arrange the other<br/>n - 1 people in a line"]
    B --> C["(n - 1)! seatings"]

Fixing one person removes the rotations, and the rest is an ordinary arrangement.

Example 1. Six people at a round table: (6 โˆ’ 1)! = 120 seatings.

Necklaces and garlands

Beads on a necklace can be flipped over, so a clockwise order and its mirror image are the same necklace. That halves the count:

Necklace of n distinct beads = (n โˆ’ 1)! รท 2 (for n โ‰ฅ 3)

Example 2. Six different beads can form (5!) รท 2 = 60 necklaces. Use the halved formula when the objects can be turned over (necklace, garland, bracelet), and the plain formula when clockwise and anticlockwise order are different (people at a table, with a fixed direction of looking).

Restrictions: together

To keep some people together, glue them into a block, count the block as one object, and then multiply by the ways to arrange inside the block.

If k particular people out of n must sit together, the count is

(n โˆ’ k)! ร— k!

because the block plus the other n โˆ’ k people make n โˆ’ k + 1 objects, which arrange in (n โˆ’ k + 1 โˆ’ 1)! = (n โˆ’ k)! ways around the circle.

Example 3. Six people, A and B must sit together. Block AB plus four others make 5 objects: 4! = 24 circular arrangements, times 2! = 2 for the order inside the block, so 48.

Restrictions: apart

For "not together", subtract the together count from the total. This is called the complement method.

Example 4. Six people, A and B must not sit together: 120 โˆ’ 48 = 72.

For "no two of this group are neighbors", the standard approach is gaps. Seat the others first in a circle, which creates one gap between each pair of neighbors, then place the restricted people in different gaps.

Example 5. Five men and three women sit at a round table with no two women adjacent. Seat the men first: (5 โˆ’ 1)! = 24 ways, creating 5 gaps. Choose and arrange three women in the gaps: 5 ร— 4 ร— 3 = 60 ways. Total 24 ร— 60 = 1,440.

Restrictions: alternate

Equal numbers of men and women sitting alternately are the cleanest case. Seat the men around the table first: (m โˆ’ 1)! ways. The women then take the m gaps, in m! ways.

Example 6. Four men and four women alternating: 3! ร— 4! = 6 ร— 24 = 144.

In a circle, alternating needs exactly equal numbers of men and women. Four men and three women (or 5 and 3) cannot alternate all the way round.

Try it: circular counts

JS Circular counting helper

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Rank of a word

If you list all arrangements of the letters of a word in dictionary order, the rank of the word is its position in that list. The method works one letter at a time from the left.

  1. For the first letter, count how many letters in the word are alphabetically smaller. Each smaller letter can start (n โˆ’ 1)! words, and all of those come before your word.
  2. Remove the first letter, and repeat for the second letter with the remaining letters, using (n โˆ’ 2)!, and so on.
  3. Add all the counts, then add 1 for the word itself.

Example 7. The rank of CODE. Sorted letters are C, D, E, O.

  • C is first: no smaller letters, so 0 words before.
  • O next, from D, E, O: two smaller letters (D, E), each with 2! = 2 words, so 4 words.
  • D next, from D, E: none smaller, 0.
  • E last: 0.

Rank = 0 + 4 + 0 + 0 + 1 = 5.

Example 8. The rank of SMART. Sorted: A, M, R, S, T.

  • S: smaller letters A, M, R, so 3 ร— 4! = 72.
  • M, from A, M, R, T: one smaller (A), so 1 ร— 3! = 6.
  • A, from A, R, T: 0. R, from R, T: 0. T: 0.

Rank = 72 + 6 + 1 = 79.

When letters repeat, divide each count by the factorials of the repeated letters left in the rest of the word, and count each smaller distinct letter only once. For BANANA (letters A three times, N twice, B once), the words starting with A number 5! รท (2! ร— 2!) = 30, then those starting with BAA... and so on lead to rank 35. The program below does this bookkeeping for you.

Derangements

A derangement is an arrangement in which no object is in its original position. Typical picture: four letters go into four addressed envelopes at random, and none lands in the right one.

The count D(n) follows a recurrence:

D(n) = (n โˆ’ 1) ร— [D(n โˆ’ 1) + D(n โˆ’ 2)], with D(1) = 0 and D(2) = 1.

So D(3) = 2 ร— (1 + 0) = 2, D(4) = 3 ร— (2 + 1) = 9, D(5) = 4 ร— (9 + 2) = 44. The closed form is n! ร— (1 โˆ’ 1/1! + 1/2! โˆ’ 1/3! + ... ยฑ 1/n!), which also explains why D(n) รท n! settles near 0.368 as n grows.

flowchart TD
    A["D(n)<br/>object 1 goes to<br/>one of n - 1 places"] --> B["(n - 1) x D(n - 1)<br/>the partner does not<br/>go back to place 1"]
    A --> C["(n - 1) x D(n - 2)<br/>object 1 and its partner<br/>swap places"]

The recurrence splits derangements by where object 1 goes and whether its partner swaps back.

Example 9. Three people each leave a coat, and the coats are returned at random. The number of ways nobody gets their own coat is D(3) = 2, out of 3! = 6 possible returns, so the probability is 1/3.

JS Word rank and derangements

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Common mistakes

  • Using n! for a round table. Use (n โˆ’ 1)!, and (n โˆ’ 1)! รท 2 only when the arrangement can be flipped.
  • Forgetting the inside order of a block (the 2! when two people sit together).
  • Mixing up n โˆ’ k and n โˆ’ k + 1 for a block: the block counts as one object, but the circular formula then subtracts one.
  • In rank problems, adding 1 at the end is easy to forget, and repeated letters must be handled with division.

When a restriction seems hard, count the opposite (together) and subtract from the total. It is almost always shorter.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In how many ways can 7 people sit around a round table?

    Circular arrangements of 7 distinct people number (7 - 1)! = 6! = 720.
  2. 2. How many different necklaces can be made from 8 distinct beads?

    A necklace can be flipped, so the count is (8 - 1)! / 2 = 5040 / 2 = 2520.
  3. 3. Five people sit at a round table. In how many ways can two particular people sit together?

    Use (n - k)! x k! = 3! x 2! = 12. The block and the other three people form 4 objects, which arrange in 3! ways, and the two inside the block can swap.
  4. 4. What is the rank of the word MAIL among all arrangements of its letters in dictionary order?

    Sorted letters: A, I, L, M. M has three smaller letters, giving 3 x 3! = 18 words before it. A, I and L then follow in sorted order, so rank = 18 + 1 = 19.
  5. 5. Five letters are put at random into five addressed envelopes. In how many ways can no letter go into its own envelope?

    This is the derangement number D(5) = 4 x (D(4) + D(3)) = 4 x (9 + 2) = 44.

Summary

  • Circular permutations of n distinct objects: (n โˆ’ 1)!, found by fixing one object. For necklaces that can be flipped: (n โˆ’ 1)! รท 2.
  • Together: treat the group as a block, giving (n โˆ’ k)! ร— k! for k people. Apart: total minus together.
  • Alternating men and women: (m โˆ’ 1)! ร— m!. For "no two adjacent" seat the others first and use the gaps.
  • Rank of a word: for each letter, count smaller letters times the arrangements of the rest, then add 1.
  • Derangements: D(n) = (n โˆ’ 1)(D(n โˆ’ 1) + D(n โˆ’ 2)), giving 0, 1, 2, 9, 44, 265, ...

Next: Probability, where counting turns into chances.