Categories
  Encyclosphere.org ENCYCLOREADER
  supported by EncyclosphereKSF

Permutations by cycle type

From Wikiversity - Reading time: 2 min

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 Sloane'sA000041(n).

The first 8! = 40320 finite permutations have Sloane'sA000041(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 Sloane'sA198380).

Refined rencontres numbers

[edit | edit source]

The irregular triangle Sloane'sA181897 shows how many permutations of n=0..8 elements have cycle type i=0..21,
where i is an index number of Sloane'sA194602, 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 Sloane'sA073906.

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 Sloane'sA098825 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.

k
n
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
k
n
0 1 2 3 4 5 6 7 8
0 11
1 11 10
2 11 20 11
3 11 30 31 12
4 11 40 61 42 19
5 11 50 101 102 59 144
6 11 60 151 202 159 644 1265
7 11 70 211 352 359 2144 7265 11854
8 11 80 281 562 709 5644 28265 81854 114833

Licensed under CC BY-SA 3.0 | Source: https://en.wikiversity.org/wiki/Permutations_by_cycle_type
37 views |
↧ Download this article as ZWI file
Encyclosphere.org EncycloReader is supported by the EncyclosphereKSF