1
$\begingroup$

$10$ persons are to be arranged in a ring shape. Number of ways to do that is $9!.$

I wonder why we subtarct $1$ in all such cases.

I can imagine that if A,B,C,D are sitting in a row then B,C,D,A would give me a different combination but had they been sitting on a circular table then both the above combinations would imply the same thing. Same for CDAB or DABC.

But how does it all lead to $(n-1)!$ formula? Individual cases, I am able to imagine but overall how are we generalizing it?

$\endgroup$
  • $\begingroup$ Imagine that 4 persons are siting in a round table, you can order them in 4! ways, but each time you rotate the table one person to the right, it's the same ordering. how many rotations are there? as the number of persons, 4. So the total number of ways is $\frac{4!}{4} = 3!$. The same way for 10 persons $\endgroup$ – DanielY Oct 28 '13 at 12:51
  • $\begingroup$ @DanielY- why are we dividing by 4? why not subtract? $\endgroup$ – Ramit Oct 28 '13 at 12:53
  • $\begingroup$ Because for each ordering, we have 4 repitition of it when it's in a circle (of n repitition in the general case). So divided must be made. $\endgroup$ – DanielY Oct 28 '13 at 12:55
  • $\begingroup$ @DanielY- okay,okay, got it. Thanks. Wish you post it as answer so that i could accept it. $\endgroup$ – Ramit Oct 28 '13 at 12:56
  • $\begingroup$ You're most welcome @Ramit. Answer posted $\endgroup$ – DanielY Oct 28 '13 at 12:58
5
$\begingroup$

Imagine that the table is arranged so that one of the seats is due north of the centre of the table. Seat the $n$ people around the table. Let $p_1$ be the person sitting in that north seat, and let the other $n-1$ be $p_2,p_3,\ldots,p_n$ clockwise around the table. Now rotate the table and the seats one place counterclockwise: $p_2$ is now in the north seat, and the others going clockwise around the table are $p_3,p_4\ldots,p_n,p_1$. Repeat: $p_3$ is now sitting to the north, and clockwise around the table we have $p_4,p_5,\ldots,p_n,p_1,p_2$. If we keep doing this, we bring each person in succession to the northern spot, and after $n$ of these rotations everything and everyone is back in its original position. From the standpoint of absolute compass directions we had $n$ different arrangements, but from the standpoint of the order of people around the table these $n$ arrangements were all the same. Thus, each cyclic permutation of the diners corresponds to $n$ different absolute permutations, i.e., permutations in which we care about the absolute seating position of each diner and not just who sits next to whom. Since there are $n!$ absolute permutations, there must be $\frac{n!}n=(n-1)!$ cyclic permutations.

Alternatively, you can think of it this way: given a seating of the diners around the table, you can designate any seat as the head of the table and list the diners clockwise around the table starting at the head. That gives $n$ different lists, but they all correspond to the same cyclic permutation of the diners. Since $n!$ different lists are possible, there must again be $\frac{n!}n=(n-1)!$ different cyclic permutations, each corresponding to $n$ of the lists.

$\endgroup$
  • $\begingroup$ Way to go, Brian! $\endgroup$ – DanielY Oct 28 '13 at 13:05
  • 1
    $\begingroup$ @Daniel: Sorry: I wasn’t following the comments while I was typing, so I didn’t see that you’d given an explanation that satisfied the OP. (I have upvoted your answer, however.) $\endgroup$ – Brian M. Scott Oct 28 '13 at 13:16
  • $\begingroup$ That's fine, I guess, especially when it's you, someone that've helped me alot here...Most important thing is that the OP has received a worthy answer... $\endgroup$ – DanielY Oct 29 '13 at 6:04
3
$\begingroup$

Imagine that $4$ persons are siting in a round table, you can order them in 4! ways, but each time you rotate the table one person to the right, it's the same ordering. How many rotations are there? as the number of persons, $4$. So the total number of ways is $\frac{4!}{4}=3!$.

The same way for 10 persons, and also $n$ persons as the general case.

$\endgroup$
1
$\begingroup$

Here's another way to think about it:

First, let's consider the case of the 'regular' linear permutation and see how we come up with the formula ${P(n) = n! }$.

We have $n$ ordered slots (first, second, third etc.) in which we will insert our $n$ elements. Arbitrarily select an element, $i_1$. We have $n$ available slots in which we can insert $i_1$. Now choose another element, $i_2$. Independent of our choice for $i_1$, we have $n - 1$ options for $i_2$. Proceeding in this manner, we end up with ${n * n-1 * \ldots * 2 * 1 = n!}$.

Now let's consider the circular permutation. The ordering of a circle does not have a notion of a first element, second element etc. Rather we can describe the ordering of a circle in terms of element adjacency. In other words, we've described the configuration of a circle, when we've described for each element which other element lies to its right.

So let's choose one element, $i_1$. We have $n - 1$ potential right neighbors to choose from. Call our choice $i_2$, there are $n - 2$ options for $i_2$. (The element $i_1$ is not an option as a right neighbor for $i_2$ because that would prevent us from adding additional elements to the circle without breaking existing choices.) Proceeding in this way, our choices are ${n -1 * n -2 * \ldots * 2 * 1 * 1}$ (The last elements only have one option.) This gives the formula ($CP$ = number of circular permutations) ${CP(n) = (n-1)!}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.