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[edit | edit source]

The 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 ( n k ) {\displaystyle {\tbinom {n}{k}}} and the top entry of the column.
The sequence of top entries could be called the refined subfactorials, and might be denoted  ? i {\displaystyle ?i} .
So the triangle entries can be derived from Pascal's triangle and the refined subfactorials:  (k implicitly derived from i.)

T ( n , i ) = ( n k ) ⋅ ? i {\displaystyle T(n,i)~=~{\binom {n}{k}}~\cdot ~?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  ( k − 1 ) ! {\displaystyle (k-1)!} .
This means that among the  ! k {\displaystyle !k} derangements of k elements there are  ( k − 1 ) ! {\displaystyle (k-1)!} 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[edit | edit source]

This 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  ! k {\displaystyle !k} is the number of derangements of k elements.

T ( n , k ) = ( n k ) ⋅ ! k {\displaystyle T(n,k)~=~{\binom {n}{k}}~\cdot ~!k}

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8

|
|
|
|
|
|
|
|
|

0  | 1  |  |  |  |  |  |  |  |
1  | 1  | 0  |  |  |  |  |  |  |
2  | 1  | 0  | 1  |  |  |  |  |  |
3  | 1  | 0  | 3  | 2  |  |  |  |  |
4  | 1  | 0  | 6  | 8  | 9  |  |  |  |
5  | 1  | 0  | 10  | 20  | 45  | 44  |  |  |
6  | 1  | 0  | 15  | 40  | 135  | 264  | 265  |  |
7  | 1  | 0  | 21  | 70  | 315  | 924  | 1855  | 1854  |
8  | 1  | 0  | 28  | 112  | 630  | 2464  | 7420  | 14832  | 14833

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8

|
|
|
|
|
|
|
|
|

0  | 1⋅1 |  |  |  |  |  |  |  |
1  | 1⋅1 | 1⋅0 |  |  |  |  |  |  |
2  | 1⋅1 | 2⋅0 | 1⋅1 |  |  |  |  |  |
3  | 1⋅1 | 3⋅0 | 3⋅1 | 1⋅2 |  |  |  |  |
4  | 1⋅1 | 4⋅0 | 6⋅1 | 4⋅2 | 1⋅9 |  |  |  |
5  | 1⋅1 | 5⋅0 | 10⋅1 | 10⋅2 | 5⋅9 | 1⋅44 |  |  |
6  | 1⋅1 | 6⋅0 | 15⋅1 | 20⋅2 | 15⋅9 | 6⋅44 | 1⋅265 |  |
7  | 1⋅1 | 7⋅0 | 21⋅1 | 35⋅2 | 35⋅9 | 21⋅44 | 7⋅265 | 1⋅1854 |
8  | 1⋅1 | 8⋅0 | 28⋅1 | 56⋅2 | 70⋅9 | 56⋅44 | 28⋅265 | 8⋅1854 | 1⋅14833