Number of distinct $n$ cycles of $n$ objects.

73 Views Asked by At

Find number of $n$ element cycles of $n$ elements.

The first position can be filled in $n$ ways.
Then, the second position can be filled in $n-1$ ways.
Then, the third position can be filled in $n-2$ ways.
$\vdots$
This gives a total of $n!$ ways.

Let, the four elements, for $n=4$ be: $a,b,c,d.$
Taking a particular cycle to be $abcd,$ have the equivalent cycles:

  1. $bcda,$
  2. $cdab,$
  3. $dabc.$

I.e, for each cycle of length $n,$ there are $n-1$ equivalent cycles.

But, this means there are $n!/(n-1)$ distinct cycles.

However, for $n=4$ have $6$ non-equivalent (distinct) cycles of length $4,$ as for say the cycle $(abcd)$:

  1. $abcd,$
  2. $abdc,$
  3. $acbd,$
  4. $acdb,$
  5. $adbc,$
  6. $adcb.$

But, this contradicts with earlier analysis of having $4!/(3)= 8$ cycles.

1

There are 1 best solutions below

2
On BEST ANSWER

For each cycle $a_1a_2\dots a_n$, there are actually $n$ equivalent cycles, not $n-1$ --- each corresponds to a unique choice of starting element $a_i$. In the case of $n=4$ where the original cycle is $abcd$, the equivalent cycles are $$\{abcd,bcda,cdab,dabc\};$$ I believe you only counted the last three.