I know this is a physics group, but then I think you guys can answer me .. anyone can explain how circular permutation work? From the explanation from the book, it is understood that if CW $\ne$ ACW , it is $(n-1)!$. if CW $=$ ACW, $(n-1)!/2$ . . . but then from the example that it give, it confuses me..help? test tomorrow >.<
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
There are as you know $n!$ ways to arrange $n$ people in a row.
Now imagine arranging $n$ people around a circular table, where we count two seatings $A$ and $B$ as the same if everyone in seating $B$ has the same right-neghbour as in $A$, and the same left neighbour as in $A$. To count the number of such seatings, note that it doesn't matter where Alicia sits, all that matters is where the others are seated in in relation to Alicia. So seat Alicia in the best chair. The person to the right of Alicia can be chosen in $n-1$ ways. For each such way, the next person on the right can be chosen in $n-2$ ways. And for every $(n-1)(n-2)$ ways of selecting these two people, the next person to the right can be chosen in $(n-3)$ ways. And so on. The total number of ways is therefore $(n-109n-2)(n-3)\cdots(2)(1)$, or $(n-1)!$. Note that this even works for $n=1$, since $0!$ is defined to be $1$.
Now imagine making a necklace with $n$ different circular beads. Consider two such necklaces $A$ and $B$ the same if $A$ can be rotated to look exactly like $B$, or $A$ can be rotated and turned over to look exactly like $B$. Turning over essentially reverses left and right. So (usually) if we allow turning over, the number of distinct necklaces gets divided by $2$. With rotation allowed, there were $(n-1)!$ of them, so with turning over allowed, the number is $(n-1)!/2$.
That is not quite fully correct. If $n=1$, turning the necklace over makes no difference, so the number of distinct permutations with turning over allowed is $1$. Also, if $n=2$, every left neighbour is simultaneously a right neighbour. the number of circular permutations is $1$, and the number of permutations with turning over also allowed is again $1$. But for $n \ge 3$, the number of really different necklaces is $(n-1)!/2$.