3
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Kyle Jun 13 '15 at 1:23
  • $\begingroup$ (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). $\endgroup$ – Christopher Mowla Jun 13 '15 at 5:15
  • $\begingroup$ 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). $\endgroup$ – Christopher Mowla Jun 13 '15 at 5:20
  • $\begingroup$ 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. $\endgroup$ – Christopher Mowla Jun 13 '15 at 5:50
  • $\begingroup$ 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? $\endgroup$ – Kyle Jun 14 '15 at 22:16
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\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.