1
$\begingroup$

My book writes like this:

Number of permutations of $n$ different things taken $r$ at a time: Case I : If clockwise & anti-clockwise orders are taken as different, then the number of circular permutations = $$ \frac{{_n}P_r}{r}$$

Case II : When clockwise & anticlockwise orders are not taken as different, then number of permutations = $$\frac{{_n}P_r}{2r}$$

So, can anyone help me explaining how the book came to the conclusion? What is the proof? Please help.

$\endgroup$
1
  • 2
    $\begingroup$ The number of linear permutations is $_nP_r$. If you number the positions on the circle $1$ to $r$ and count these $_nP_r$ permutations, you counted each rotated version of the circular permutation $r$ times. If you can also flip the circle over (which changes a clockwise permutation into an anticlockwise one, you’ve counted each one $2r$ times. $\endgroup$
    – Steve Kass
    Commented Nov 3, 2014 at 6:07

2 Answers 2

4
$\begingroup$

nPr is the count of the number of arrangements of n unique beads taken r together. Once you arrange them, tie them into a necklace of r beads.

Now think of cutting the necklace. You can choose to cut at r points. Each cut will result in a permutation of the beads. All these r permutations would result in the same necklace.

Out of the nPr permutations, there are r permutations for each necklace. Hence, the number of unique necklaces is nPr/r

Once we prove case I, it is easy to prove case II. Each unique necklace of case I, will also have its mirror reflection, which was also counted. Case II considers these 2 as same: hence the total count is halved.

$\endgroup$
1
  • $\begingroup$ This analysis is great Can I get a mathematical proof? $\endgroup$
    – Shashaank
    Commented Mar 24, 2022 at 17:44
0
$\begingroup$

Consider a circular permutation of 8 things taken 3 at a time, say:

...174174174174...

Obviously this corresponds to the ordinary permutation 174 of 8 things taken 3 at a time. But of course depending on where you start it also corresponds to the permutations 741 and 417. That is, each of the circular permutations of 8 things taken 3 at a time corresponds to exactly 3 ordinary permutations of 8 things taken 3 at a time.

Since there are $_{8}P_3$ of the latter, there are $_{8}P_3/3$ of the former.

$\endgroup$

You must log in to answer this question.