Permutations by cycle type
The conjugacy classes of the symmetric group Sn are defined by the permutations' cycle types.
The cycle types correspond to the integer partitions of n. So the number of conjugacy classes of Sn is A000041(n).
The first 8! = 40320 finite permutations have A000041(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 A198380).
Refined rencontres numbers
editThe irregular triangle A181897 shows how many permutations of n=0..8 elements have cycle type i=0..21,
where i is an index number of A194602, denoting an integer partition.
(E.g. column 11 counts the number of permutations with a 3-cycle and two 2-cycles.)
The columns are grouped together based on how many elements k=0..8 are moved. (There is no column for k=1, because no permutation can move only one element.)
k | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | ||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
n | 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 |
n! | ||||||||||||||||||
0 | 1 | 1 | 1 | 1 | |||||||||||||||||||||||||||||||||||||
1 | 1 | 1 | 1 | 1 | 0 | 1 | |||||||||||||||||||||||||||||||||||
2 | 1 | 1 | 1 | 2 | 0 | 1 | 1 | 1 | 2 | ||||||||||||||||||||||||||||||||
3 | 1 | 1 | 1 | 3 | 0 | 3 | 3 | 3 | 1 | 2 | 2 | 6 | |||||||||||||||||||||||||||||
4 | 1 | 1 | 1 | 4 | 0 | 6 | 6 | 6 | 4 | 8 | 8 | 1 | 3 | 6 | 9 | 24 | |||||||||||||||||||||||||
5 | 1 | 1 | 1 | 5 | 0 | 10 | 10 | 10 | 10 | 20 | 20 | 5 | 15 | 30 | 45 | 1 | 20 | 24 | 44 | 120 | |||||||||||||||||||||
6 | 1 | 1 | 1 | 6 | 0 | 15 | 15 | 15 | 20 | 40 | 40 | 15 | 45 | 90 | 135 | 6 | 120 | 144 | 264 | 1 | 15 | 90 | 40 | 120 | 265 | 720 | |||||||||||||||
7 | 1 | 1 | 1 | 7 | 0 | 21 | 21 | 21 | 35 | 70 | 70 | 35 | 105 | 210 | 315 | 21 | 420 | 504 | 924 | 7 | 105 | 630 | 280 | 840 | 1855 | 1 | 210 | 504 | 420 | 720 | 1854 | 5040 | |||||||||
8 | 1 | 1 | 1 | 8 | 0 | 28 | 28 | 28 | 56 | 112 | 112 | 70 | 210 | 420 | 630 | 56 | 1120 | 1344 | 2464 | 28 | 420 | 2520 | 1120 | 3360 | 7420 | 8 | 1680 | 4032 | 3360 | 5760 | 14832 | 1 | 105 | 1260 | 1120 | 3360 | 2688 | 1260 | 5040 | 14833 | 40320 |
An entry in row n and column group k is the product of the binomial and the top entry of the column.
The sequence of top entries could be called the refined subfactorials, and might be denoted .
So the triangle entries can be derived from Pascal's triangle and the refined subfactorials: (k implicitly derived from i.)
The last column in column group k counts the permutations with a complete k-cycle.
An interesting fact is that the refined subfactorials in these columns are factorials, namely .
This means that among the derangements of k elements there are with complete k-cycles.
(E.g. here are the 24 derangements with 5-cycles.)
By excluding the full cycles one could define this rather silly sequence: 0, 0, 0, 0, 3, 20, 145, 1134, 9793...
Some rows have repeating entries, e.g. row 4 contains entry 6 twice. The number of distinct entries per row is A073906.
This triangle (with the same order of partitions) is shown in Sayma (ya da Kombinasyon Hesapları) by Ali Nesin (p. 151).
Rencontres numbers
editThis is the triangle A098825 of rencontres numbers ordered by number of moved elements k. (Usually they are ordered by number of fixed points.)
Its entries are the product of binomials and subfactorials. The subfactorial is the number of derangements of k elements.
|
|