Question

How do I calculate the number of permutations of the set {1,2,3,4,5,6} that consist of 3 2-cycles. What about the number of permutations of 2 3-cycles. Essentially looking for the generalized result to this problem...

Answer 1

I am not certain that there is an explicit function \(f(a,b)\) which tells you the amount of \(a\) \(b\)-cycles. This seems directly related to the symmetric group \(S_n.\) It isn't immediately obvious how to answer this question.

Answer 2

Yea He is right

Answer 3

@satellite73, got any idea on this one? @KingGeorge, what about you?

Answer 4

Hmm. OK. We were given a problem which essentially amounted to finding the number of permutations of {1,2,3,4,5,6} that have at least one 2-cycle and I'm trying to figure out an efficient way to approach the problem. Counting them seems a bit crazy as there are 105 total...

Answer 5

Question. What grade of math is this? There may be a simple thing I am overlooking.

Answer 6

Also, \(S_6\) has \(6!=720\) unique permutations. How did you get \(105?\)

Answer 7

Discrete Math. (calculus is a prerequisite)

Answer 8

Though the chapter is on subsets and has nothing to do with calculus. Just giving you an idea of the level

Answer 9

105 total permutations that contain at least one 2-cycle

Answer 10

Let's clarify. By a cycle, do you mean e.g. \((1\,2)\) which is a permutation mapping the symbol \(1\) to \(2\) and the symbol \(2\) to \(1?\) I may be applying the group-theory based concept and it may not be the same thing.

Answer 11

yes. (1 2) is a 2-cycle where 1 maps to 2 and 2 to 1. (1 2 3) is a 3-cycle where 1 maps to 2, 2 to 3, and 3 to 1.

Answer 12

hmm.. Well, in your example, it has \(720\) different permutations. I am still not sure how you arrived at there being only \(105\) permutations that contain at least one 2-cycle.

Answer 13

Can you elaborate on that?

Answer 14

yes I misspoke. It's 105 permutations that have at least one 2-cycle but no 3,4,5, or 6 cycles.

Answer 15

Anyway, I'm not concerned with this specific problem per says as I am with figuring out an efficient way to approach this in the future. Let's take a step back and just try to figure out an efficient way to find the number of permutations of {1,2,3,4,5,6} that consist of ONLY 2 cycles. or the permutations of {1,2,3,4} that consist of ONLY 2 cycles (there are only 3). How do we do this efficiently as the numbers get bigger?

Answer 16

Well, it depends. Think about this: Any cycle can be shown to be a product of cycles. What do we do about that?

This is what I mean: \((x_1\, x_2\, \dots\, x_n)=(x_1\,x_{n})(x_1\, x_{n-1})\cdots(x_1\, x_2).\)

How are we going to account for the fact there are equivalences such as this (and more) in cyclic notation?

Answer 17

Is this a rhetorical question? I'm a bit confused

Answer 18

No, it's literal. I see this as posing a huge issue. Are you going to count a cycle such as \((1\,3)(1\,2)=(1\,2\,3)\) as both two 2-cycles and one 3-cycle? Or are you going to restrict this to where cycles must be in their "simplest form"? (i.e. the form which is irreducible and uses as few cycles as possible.)

Answer 19

Do you see how this affects the situation and complicates things?

Answer 20

AH. I see what you are saying but in the context of the unit I'm doing we are talking irreducible.

Answer 21

hmmm....

Answer 22

I suppose you could try to look for a pattern in the enumerations.

Answer 23

AH! I just found it in my notes. The only way to have a generalized result is a recursive solution

Answer 24

S(n,k) where n-set of k partitions = S(n-1,k-1)+k*[S(n-1,k)]

Answer 25

(\(e\) is the \(1\) cycle: \(e=(1).\))
\[S_1=\left(\{e\},\circ\right)\]
\[S_2=\left(\{e,(1\,2)\},\circ\right)\]
\[S_3=\left(\{e,(1\,2),(1\,3),(2\,3),(1\,2\,3),(1\,3\,2)\},\circ \right)\]
\[S_4=\left( \{e,(1\,2),(1\,3),(2\,3),(1\,2\,3),(1\,3\,2),\\(3\,4),(2\,3\,4),(2\,4\,3),(2\,4),(1\,2)(3\,4),(1\,2\,3\,4),\\(1\,2\,4\,4),(1\,2\,4),(1\,3\,4\,2),(1\,3\,4),(1\,3)(2\,4),(1\,3\,2\,4),\\(1\,4\,3\,2),(1\,4\,2),(1\,4\,3),(1\,4),(1\,4\,2\,3),(1\,4)(2\,3)\},\circ \right)\]

--------

Recursive solution? That's the only one? Makes sense.

Answer 26

1
1 1
1 3 1
1 7 6 1

etc

Answer 27

thanks and have a good day

Answer 28

You, too. Thanks for the interesting problem.

Answer 29

I'm a little late to the party here, but for the symmetric group, there is indeed an explicit formula for this. This link here has the formula, and an explanation of how to use it. btw, it only makes sense if you're familiar with the conjugacy classes of \(S_n\). http://groupprops.subwiki.org/wiki/Conjugacy_class_size_formula_for_symmetric_group

Using the formula, I get that there are \[\frac{6!}{2^33!}=15\]elements consisting of three 2-cycles. Likewise, there are \[\frac{6!}{3^22!}=40\]elements consisting of two 3-cycles.

Answer 30

Now for an explanation of what the conjugacy classes of \(S_n\) are.

Let \(c\) be a conjugacy class of \(S_n\), and let \(a\) be a representative of the conjugacy class. Then \(g\in c\) iff there exists some \(h\in S_n\) such that \(a=hgh^{-1}\). In the symmetric group, you can easily tell if two elements are conjugate (in the same conjugacy class) since they are conjugate iff they have the same cycle type. This means I can immediately say that \[(32897)(14)(56) \quad \text{is conjugate to}\quad (12345)(67)(89)\]without doing any lengthy calculations.

Answer 31

@KingGeorge, brilliant job. I am too tired to fully comprehend what you're talking about. But, nonetheless, bravo.

Answer 32

Also, not to rain on the party, but the recursive formula given above, does not count the right things. It counts the number of elements with 3 unique cycles in their decomposition.

For n=6, k=3, it outputs the value 90. This means that you can partition {1, 2, 3, 4, 5, 6} in 3 parts, 90 different ways. These ways include
(1)(2)(3, 4, 5, 6), (1)(2, 3)(4, 5, 6), (1, 2)(3,4)(5,6), (1,5,6,3)(2)(4) ... and so on.

There should be 90 of these in total. However, you only want those of the form (12)(34)(56). This is an entirely different counting problem.

Answer 33

If you want to know how to count these combinatorically, you may do so as follows.

For three 2-cycles: Choose 2 numbers from 6 to be in the first 2-cycle. This is \(\binom{6}{2}\). Now choose two more from the 4 remaining numbers. This is \(\binom{4}{2}\). However, we need to remember that \((12)(34)(56)=(34)(56)(12)=...\). Hence, we need to divide by \(3!\). This leaves us with \[\frac{\binom{6}{2}\binom{4}{2}}{3!}=\frac{15\cdot6}{6}=15\]

Answer 34

For two 3-cycles: Choose 3 numbers from 6 to be in the first 3-cycle. This is \(\binom{6}{3}\). Now we also have to consider orderings of this, since \((123)\neq(132)\). So we multiply by \(3!\), and divide by 3 since \((123)=(231)=(312)\). Since we have two 3-cycles, we do this twice. Like before however, we know \((123)(456)=(456)(123)\), so we divide by \(2!\). This leaves us with \[\frac{\binom{6}{3}\cdot 2\cdot\frac{3!}{3}}{2!}=\frac{20\cdot2\cdot2}{2}=40\]