4

I am not familiar with this kind of counting problem, so I googled the key words. From what I found it looks like Stirling Numbers of First Kind do the job(?). These numbers are denoted [$\frac nk$ ] where $n$ is the length of permutations and $k$ is the number of cycles with $0 \le k \le n$.

In the problem, the length of permutations is $8$ and the number of cycles is $4$. So, there are [$\frac 84$ ] permutations. Does that work?

Kyle
  • 95

3 Answers3

2

There are $ \frac{{8!}} {{\left( 3 \right)\left( {2^2 \times 2!} \right)\left( {8 - 7} \right)!}} = 1,680 $ 1 3-cycle, 2 2-cycles in 8 objects. See this page for more details. (Also note that he uses the term "cycle class", but the common term is "cycle type".)

EDIT:

Okay, I will explain this a little more. Let me abbreviate "1 3-cycle and two 2-cycles" as {3,2,2}.

I will be complete concrete and show you all 24 redundancies for the cycle type {3,2,2} in 8 objects which you have asked about.

Firstly, I will rewrite my calculation as the following, and I will refer to each factor in the denominator from left to right in the explanation that follows.

$\frac{{8!}} {{\left( 3 \right)\left( 2 \right)\left( 2 \right)\left( {2!} \right)\left( {8 - (3+2+2)} \right)!}}$

Now, let (1$\to$2$\to$3)(4$\leftrightarrow$5)(6$\leftrightarrow$7)(8) represent the cycle type {3,2,2}.

Then the 24 redundancies we divide by are the following:

For the 3-cycle (rotate the 3-cycle clockwise each time): $=(3)$

Set A

{$(1\to2\to3)$, $(3\to1\to2)$, $(2\to3\to1)$}

For the 2 2-cycle (Rotate one of the 2-cycles each time): $=(2)(2)$

Set $B_1$

{$(5\leftrightarrow4)(7\leftrightarrow6)$, $(4\leftrightarrow5)(7\leftrightarrow6)$, $(5\leftrightarrow4)(6\leftrightarrow7)$, $(4\leftrightarrow5)(6\leftrightarrow7)$}

and... switch the two 2-cycles in the above work: $=(2)(2)$

Set $B_2$

{$(7\leftrightarrow6)(5\leftrightarrow4)$, $(7\leftrightarrow6)(4\leftrightarrow5)$, $(6\leftrightarrow7)(5\leftrightarrow4)$, $(6\leftrightarrow7)(4\leftrightarrow5)$}

$B_1$ and $B_2$ are a result of $(2!)$. That is, when we switch/permute these two 2-cycles, we are saying that there are only two ways we can order these two same length cycles.

For the 1-cycle $=(8 - (3+2+2))$

Set $C$

{$(8)$}

We now take the Kronecker product $\{$A$\}\times\{B_1\cup B_2\}\times\{C\}$ to get $(3)(4+4)(1) = 24$ equivalent permutations. Therefore, we divide by 24 to only use one of them.

Key Point: Because the product of disjoint cycles is commutative, and since we can represent an $n$-cycle in $n$ different ways (by rotating all the numbers inside of it---and keep their cyclic order the same as we do), 23/24 of these permutation representations are redundant. Therefore, we divide by 24 to only use one of them.

Christopher Mowla
  • 969
  • Suppose one of the permutations among $8!$ is $(123)(45)(67)(8)$. Other possibilities are $(213)(54)(76)(8)$ and $(312)(45)(76)(8)$. Then the cycles $(123), (312), (213)$ are all the same cycle, so we need to divide them out. If initially we filled out the $3$-cycle as $123$, then there are only 2 redundant cycles, namely $(312), (213)$, but shouldn't there be $3! = 6$? $123$ and $132$ are not the same permutation, are they? Can you comment on this, please. Thanks. – Kyle Jun 13 '15 at 01:23
  • (123) and (132) are not the same permutation: they are inverses of each other (the 2-cycle is an exception). However, they are the same cycle type/in the same conjugacy class. Remember, these calculations calculate the order of the conjugacy class (which counts the inverse and all other "versions" (for the 4-cycle and larger) of a cycle, and thus cycle type, since a cycle type is a collection of individual cycles). – Christopher Mowla Jun 13 '15 at 05:15
  • We only divide by factors which describe the exact same cycle (and thus the exact same permutation, since, again, a cycle type is a collection of individual cycles). That is, rotating an n-cycle, while keeping the cyclic order of its numbers the same and/or changing the slots in which that n-cycle takes place relative to the position of all other individual cycles (when doing this, of course, we assume that every number in each cycle occupies adjacent slots in a permutation representation list: we switch the order of the slots in "blocks" to keep all numbers in each cycle together). – Christopher Mowla Jun 13 '15 at 05:20
  • I apologize for a third comment, but note that $ n! = \sum\limits_{i = 1}^{C_n } {\left( {c_i } \right)} $, where $C_n$ is the number of cycle types in $n$ objects and $c_i$ is the number of "versions" of each cycle type.

    In other words, the sum of all versions/conjugates (which we are calculating in this topic) of all cycle types (which we determine by using integer partitions) is what makes up $n!$. Therefore, $n!$ is calculated after eliminating these same permutation representation redundancies.

     – Christopher Mowla Jun 13 '15 at 05:50
  • Think I see where my thinking went wrong. Suppose I want to plant 5 identical flowers in a row. There's only one way to do that since the flowers are identical: $\frac {5!}{5!}$. Somehow I thought there's always $n!$ redundancies for $n$ identical permutations. Apparently not. Now I am trying to see where that extra $2$ in the denominator of the expression in your original post comes from. There are $2$ identical permutations in $(45)$. Same goes for $(67)$. In total, $4$. If $(123)(45)(67)(8) = (123)(67)(45)(8)$,then there are $4$ more. Make sense? – Kyle Jun 14 '15 at 22:16
  • I am going to edit my post to explain this topic in full detail. I will put the new information under "EDIT". – Christopher Mowla Jun 15 '15 at 00:14
1

No, $\left[ 8 \over 4 \right]$ is the number of ways to partition $8$ objects into $4$ cycles, where the cycles could be of any lengths as long as they add up to $8$. So the $6769$ cycles counted by $\left[ 8 \over 4 \right]$ would include, for example, partitioning into four $2$-cycles.

Your problem is a bit easier than finding $\left[ 8 \over 4 \right]$ would be (if you didn't have a handy table of Stirling numbers) because there is only one breakup to deal with. First, observe that for a 1-cycle and for the two 2-cycles, once you choose the elements there is only one choice as to what the cycle is. But for the 3-cycle, there are two choices (cycles isomorphic to $(e_1e_2e_3)$ aand cycles isomorphic to $(e_3e_2e_1)$ ).

So pick the element in the 1-cycle: This can be done in $8$ ways.

Then pick the four elements forming the two $2$-cycles: This can be done in $\binom74 = 35$ ways. But for each of those ways there are $3$ distinct ways to break those four into two pairs. Finally, make a choice of "direction" among the $2$ possibilities for the 3-cycle.

The product is then $$ 8\cdot 35\cdot 3\cdot 2 = 1680 $$ ways to partition the eight elements as required.

Mark Fischler
  • 41,743
1

I post the species equation for future reference. The species equation for permutations of cycle shape $a_1 a_2^2 a_3$ is $$\mathfrak{C}_{=1}(\mathcal{Z}) \times \mathfrak{P}_{=2}( \mathfrak{C}_{=2}(\mathcal{Z}) ) \times \mathfrak{C}_{=3}(\mathcal{Z}).$$ This yields the EGF $$f(z) = \frac{z}{1}\times \frac{1}{2} \left(\frac{z^2}{2}\right)^2 \times \left(\frac{z^3}{3}\right) = \frac{z^8}{24}.$$

Extracting coefficients from this EGF we get $$8! [z^8] \frac{z^8}{24} = \frac{8!}{24} = 1680.$$

Wikipedia has an entry for the notation.

Marko Riedel
  • 61,317