The Symmetric Group -- Abstract Algebra Examples 5 

I’m quite new to symmetric groups and I feel like it does have SOMETHING to do with it. To first get the k cycle we have to CHOOSE k integers from the set {1,….,n} (using non other than binomial coefficients)…. Giving us n!/(n-k)!k! options. But for these k-cycles pick the starting number and … the order of the (k-1) remaining elements in the cycle certainly matters. So we have to account for all of these possibilities by multiplying back by (k-1)!. Giving the number of possible k cycles to be…. (k-1)!n!/(n-k)!k!= n(n-1)….(n-k+1)/k 😁

​@@dalitlegreenfuzzyman Binomial coefficients count the number of unordered collections, so while you are of course correct, you have counted (cyclically) ordered objects by instead counting unordered objects and then putting a (cyclical) order on them, which is a bit of a roundabout way of doing things. The connection you have noticed is not particular to symmetric groups; combinations (unordered collections) are related to permutations (ordered collections) by the formulas nCk = nPk/k! and nPk = nCk*k!, where nCk is the number of k-element subsets of n elements, also known as n choose k, and nPk is the number of k-element ordered subsets of n elements: the "/k!" corresponds to dividing out by the number of ways to rearrange each ordered subset of k elements, and the "*k!" corresponds to multiplying by the number of ways to order each subset of k elements. I will admit that my " _nothing to do with_ " was a bit over the top as the connection between permutations and combinations didn't come to mind at the time, so good spot! I've therefore removed the italics :p

yes, looks like true

Another one that was missed: 12=5+4+3 and lcm(5,4,3)=60

Do you know any fast algorithm of finding possible orders? Except the brute-force method of course.

Agreed. As a previous (now deleted?) comment indicated, 3 +4 +5 = 12 so an order of 3*4*5 = 60 is also possible.

yes Justin was wrong. The number of 5-cycles ( _a b c d e_ ) in S_8 is 8·7·6·5·4/5 = 1344 (there are 8! = 40320 elements in S_8), as there are 8 choices for _a_ , then 7 choices for _b_ , ..., down to 4 choices for _8_ , and then we divide by 5 because cyclically shifting the members of a cyclic does not change it (i.e. ( _a b c d e_ ) = ( _b c d e a_ ) etc.). In general, the number of k-cycles in S_n is n(n-1)...(n-k+1)/k. You can similarly count the number of elements of a given cycle type: for example, the number of elements of cycle type [3,3,2] in S_10 - i.e. elements of the form ( _a b c_ )( _d e f_ )( _g h_ ) - is (10·9·8)·(7·6·5)·(4·3)/((3·3·2)·2) = 50400, because we have 10 choices for _a_ all the way down to 3 choices for _h_ - then we have 3 ways to cyclically permute the first 3-cycle, 3 ways to cyclically permute the second 3-cycle, and 2 ways to cyclically permute the 2-cycle, and finally we divide by a factor of 2 because there are 2! = 2 ways to permute the two 3-cycles (we have ( _a b c_ )( _d e f_ ) = ( _d e f_ )( _a b c_ )).

Yeah, clearly michael isn't taking the 10 minutes to skim through these videos...

P(n) = a composition of 2n-1 2-cycles can't be result in the identity. Base case, for n=1... 2n-1=1 2c-cycle can't result in the identity. Step given P(k)... consider P(k+1), given composition of 2k+1 cycles... note that(he does that in more detail) either: - you shuffle things so you can simplify 2 cycles there... so you have 2k-1.... due to P(k), it can't be the identity - you can move the (a b) pair as the rightmost permutation in such a way there's no other "a" in the other cycles... so the resulting composition will definitely change the place of "a"... so it can't be the identity. It could have been presented better, but is still an induction proof.

I'd say the fact that it's logically sound and therefore allows us to get away with doing less work, by not checking, is satisfying

Oh god.