Formulas Circular Permutation and Combination

Formulas For Circular Permutation and Combinations

Circular Permutaion and Combination is calculated when we selecting or arranging the items in a circular manner .Or we can say that when Permutation is calculated in a circle known as Circular Permutation.

Formulas For Circular Permutation and Combinations

Circular Permutations

  • Before diving into circular permutation let us discuss Permutation of n things not all different taken all together. If we have n things of which x number of things are of same kind, y number of things are of same type and similarly z number of things are of the same type.
  • In this case the required number of permutations is written as, P = \frac{n!}{x! y! z!}

Example :   In how many ways can the letters of the word “GOOGLE” be arranged?

            Solution :    In this case we have 6 letters of which 2 are O and 2 are G.

So total number of permutations in this case = \frac{6!}{2! 2! } = 180

Therefore, we can have 180 different arrangements.

Let’s take another question.

Example :   There are 3 copies of Harry Potter and the Philosopher’s Stone, 4 copies of The Lost Symbol, 5 copies of The Secret of the Unicorn. In how many ways can you arrange these books on a shelf?

Solution :   Total number of books = 3 + 4 + 5 = 12

Of which 3 are Harry Potter, 4 are The Lost Symbols by Dan Brown and 5 are The Secrete of The Unicorn by Herge.

So the required number of permutation = \frac{12!}{3! 4! 5!} = 27720 ways.

Permutation where repetition is allowed

  • This is a very interesting part of permutation. Say for instance, you have the digits 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9 and you are asked to find the total numbers of 6 digits passwords that can be formed using those 10 digits and repetition is allowed.
  • So we have to find the number of permutations of 10 digits taken 6 at a time with repetition allowed.
  • This means we have 6 places and 10 digits to fill those 6 places. Let’s mark these places as A, B, C, D, E and F

[ A | B | C | D | E | F ]

  • We can fill the first place i.e., A with any one of the 10 digits.
  • Note! While forming passwords even if we start with zero it will still count.
  • Similarly, we can fill the second place i.e., B with any one of the 10 digits as repetition is allowed so we can reuse the digit used in A.
  • Proceeding in a similar way C, D, E and F can be filled with any one of the 10 digits respectively.
  • So we have 6 places and each of the places can be filled with any one of the 10 digits.
  • Therefore, the number of permutations in this case = 10x10x10x10x10x10 = 1000000

Circular Permutation

  • Permutation in a circle is called circular permutation.
  • If we consider a round table and 3 persons then the number of different sitting arrangement that we can have around the round table is an example of circular permutation.
  • Circular permutation is a very interesting case. Let’s try to solve the above problem. If we have 3 persons and if we want to arrange them in a linear fashion then the total number of permutation of 3 persons taken all at a time is P = 3! = 6. Now for the sake of our convenience let us represent them as A, B and C. So we will have the following linear sitting arrangements
  • ABC, ACB, BAC, BCA, CAB, CBA
  • Now the circular part, If we arrange these 3 persons around a round table as show in the picture below, we notice that all the different arrangements are not actually different, rather they all are same. How? Well… If you move clockwise, start with A, round the table in the picture shown below you will always get A-B-C. See for yourself.
  • So it turns out that 3 linear permutations is actually 1 circular permutation.
  • Hence in general if we have n elements then total linear permutation of n elements taken all at a time is n! And we observe that n linear permutations correspond to 1 circular permutation.
  • So for n elements, circular permutation = \frac{n !}{n} = (n-1)!
  • Now if we solve the above problem, we get total number of circular permutation of 3 persons taken all at a time = (3-1)! = 2.
  • So, in the above picture 3 linear arrangements makes 1 circular arrangement.
  • Linear arrangements ABC, CAB, BCA = Circular arrangement 1
  • Linear arrangements ACB, BAC, CBA = Circular arrangement 2
  • The point is in circular permutation one element is fixed and the remaining elements are arranged relative to it.
  • Now let me tell you something that is really interesting and if you have paid a closer attention to the above picture then you can guess what I want to tell.
  • Got the clue?
  • Well… If you consider JUST, and I want to emphasis this, if you JUST want to find the total number of circular permutation without taking into consideration the clockwise and counterclockwise issue then for 3 persons you get (3-1)! = 2 possible circular arrangements as show in the above picture. But if you consider the direction, the clockwise and counterclockwise order, then the scenario change. So if the clock clockwise and counterclockwise orders are not distinguishable then the total number of circular permutation of n elements taken all together = \frac{(n – 1) !}{2}.
  • Check it out. If you look at the above picture you will definitely notice that in the circular arrangement 1 if you move clockwise you get the result A-B-C. And in the circular arrangement 2 if you move counter clockwise you get the same result A-B-C.
  • So the important point about circular arrangement is as follows:
  • If the clockwise and counter clockwise orders CAN be distinguished then total number of circular permutation of n elements taken all together = (n-1)!
  • If the clockwise and counter clockwise orders CANNOT be distinguished then total number of circular permutation of n elements taken all together = \frac{(n – 1) !}{2}.
    Example of indistinguishable case is, if you consider 5 diamonds and you want to make a necklace. In this case 5 diamonds can be arranged in a circle in (5-1)! = 24 ways. But in case of forming a necklace the clockwise and counter clockwise arrangements cannot be distinguished. So the total circular permutation in this case = \frac{(5 – 1) !}{2}. = \frac{4 !}{2}. = 12 ways.

Distinction Between Clockwise and Anti-Clockwise Arrangements

  • Consider the following circular arrangements:
  • In figure I the order is clockwise whereas in figure II, the other is anti-clock wise. These are two different arrangements. When distinction is made between the clockwise and the anti-clockwise arrangements of n different objects around a circle, then the number of arrangements = (n – 1)!.
  • But if no distinction is made between the clockwise and anti-clockwise arrangements of n different objects around a circle, then the number of arrangements is  (n – 1)!.
  • As an example consider the arrangements of beads (all different) on a necklace as shown in figure A and B.
  • Look at (A) having 3 beads x1, x2, x3 as shown. Flip (A) over on its right. We get (B) at once. However, (A) and (B) are really the outcomes of one arrangement but are counted as 2 different arrangements in our calculation. To nullify this redundancy, the actual number of different arrangements is \frac{(n – 1) !}{2}..
  • Note:  
    • When the positions are numbered, circular arrangements is treated as a linear arrangement.
    • In linear arrangements it does not make difference whether the positions are numbered or not.

Illustration: 20 persons we invited to a party. In how many ways can they be seated in a round table such that two particular persons sit on either side of the host?

Solution: After fixing the places of three persons (1 host + 2 persons) and treating them as 1 unit we can arrange the total (20 – 2 + 1) = 19 units in 18! ways. Again these particular persons can sit on either side of the host in 2 ways.

Hence the total number of ways is 18! × 2.

Illustration: In how many ways 10 boys and 5 girls can sit around a circular table, so that no two girls sit together.

Solution:    10 boys can be seated in a circle in 9! ways. There are 10 spaces between the boys, which can be occupied by 5 girls in ^{10}P_{5} ways. Hence total number of ways = 9! ^{10}P_{5} = \frac{9! 10! }{5}.

IllustrationIn how many ways can 20 persons be seated round a table if there are 9 chairs?

Solution: In case of circular table the clockwise and anticlockwise arrangements are different.

Hence the total number of ways = \frac{^{20}P_{9}}{9}

Illustration: How many necklaces of 10 beads each can be made from 20 beads of different colours?

Solution:  In case of necklace there is no distinction between the clockwise and anticlockwise arrangements. Then the required number of circular permutations \frac{^{20}P_{10}}{2 × 10 } =\frac{19! }{10! × 2} .

  • In circular arrangements, there is no concept of starting point (i.e. starting point is not defined). Hence number of circular permutations of n different things taken all at a time is
  • (n – 1)! if clockwise and anti-clockwise order are taken as different.
  • In the case of four persons A, B, C and D sitting around a circular table, then the two arrangements ABCD (in clock- wise direction) and ADCB (the same order but in anti- clockwise direction) are different.
  • Hence the number of arrangements (or ways) in which four different persons can sit around a circular table = (4 – 1)! = 3! = 6.

Number of Circular Permutations of n Different Things Taken r at a Time

  • Case I: If clockwise and anti-clockwise orders are taken as different, then the required number of circular permutations  
  • Case II: If clockwise and anti-clockwise orders are taken as same, then the required number of circular permutations =  \frac{^nP_r }{2r}

Question: In how many ways can 5 boys and 5 girls be seated at a round table so that no two girls may be together ?

Solution:  Leaving one seat vacant between two boys, 5 boys may be seated in 4! ways. Then at remaining 5 seats, 5 girls can sit in 5! ways. Hence the required number

= 4! × 5! = 2880 ways.

  • Conclusion
    • Number of ways of arranging n people on a circular track (circular arrangement) = (n – 1)!
    • When clockwise and anti-clockwise observation are not different then number of circular arrangements of n different things \frac{(n – 1)!}{2}  e.g. the case of a necklace with different beads, the same arrangement when looked at from the opposite side becomes anti-clockwise.
    • Number of selections of k consecutive things out of n things in a circle
      • = n when k < n
      • = 1 when k = n