Permutations by cycle type

From Wikiversity
Jump to: navigation, search
Created by mate2code.

The conjugacy classes of the symmetric group Sn are defined by the permutations' cycle types,
which correspond to the integer partitions of n. So the number of conjugacy classes of Sn is OEISA000041(n).

The first 8! = 40320 finite permutations have OEISA000041(8) = 22 different cycle types corresponding to the 22 first integer partitions.
To determine the cycle type of a permutation of up to 8 elements see this table (a supporting file of OEISA198380).


The following table (OEISA181897) shows how many permutations of n elements have cycle type k. (Compare this table.)
Blue numbers are factorials.
The number of distinct entries per row is 1,1,3,4,6,7,11,16... = OEISA073906.
The difference tables always show the differences between the rows of the table above. On the left of the difference tables are always constant columns.



0
 
1
2
2
3
3
2,2
4
4
5
3,2
6
5
7
2,2,2
8
4,2
9
3,3
10
6
11
3,2,2
12
5,2
13
4,3
14
7
15
2,2,2,2
16
4,2,2
17
3,3,2
18
6,2
19
5,3
20
4,4
21
8
Σ
 1  1 1! = 1
2 1 1 2! = 2
3 1 3 2 3! = 6
4 1 6 8 3 6 4! = 24
5 1 10 20 15 30 20 24 5! = 120
6 1 15 40 45 90 120 144 15 90 40 120 6! = 720
7 1 21 70 105 210 420 504 105 630 280 840 210 504 420 720 7! = 5040
8 1 28 112 210 420 1120 1344 420 2520 1120 3360 1680 4032 3360 5760 105 1260 1120 3360 2688 1260 5040 8! = 40320
Differences 1
2 1 1
3 2 2 4
4 3 6 3 6 18
5 4 12 12 24 20 24 96
6 5 20 30 60 100 120 15 90 40 120 600
7 6 30 60 120 300 360 90 540 240 720 210 504 420 720 4320
8 7 42 105 210 700 840 315 1890 840 2520 1470 3528 2940 5040 105 1260 1120 3360 2688 1260 5040 35280
Differences 2
3 1 2 3
4 1 4 3 6 14
5 1 6 9 18 20 24 78
6 1 8 18 36 80 96 15 90 40 120 504
7 1 10 30 60 200 240 75 450 200 600 210 504 420 720 3720
8 1 12 45 90 400 480 225 1350 600 1800 1260 3024 2520 4320 105 1260 1120 3360 2688 1260 5040 30960
Differences 3
4 2 3 6 11
5 2 6 12 20 24 64
6 2 9 18 60 72 15 90 40 120 426
7 2 12 24 120 144 60 360 160 480 210 504 420 720 3216
8 2 15 30 200 240 150 900 400 1200 1050 2520 2100 3600 105 1260 1120 3360 2688 1260 5040 27240
Differences 4
5 3 6 20 24 53
6 3 6 40 48 15 90 40 120 362
7 3 6 60 72 45 270 120 360 210 504 420 720 2790
8 3 6 80 96 90 540 240 720 840 2016 1680 2880 105 1260 1120 3360 2688 1260 5040 24024


Transpositions[edit]

The OEISA181897(8,1) = \tbinom{8}{2} = 28 transpositions of 8 elements ordered in an array