[Information Index] [Generation Index] [COS homepage]

Information on permutations with a given cycle structure

It is well known that permutation a=a(1),a(2),...,a(n) of [n]={1,2,...,n} can be written uniquely (up to re-ordering) as a product of disjoint cycles. Let N(i) be the number of cycles of length i in the cycle representation of a, then the polynomial:
                    N(1)     N(2)          N(n)
p(X ,X ,... ,X ) = X     +  X    + .... + X
   1  2       n     1        2             n
is called the cycle structure representation (CSR) of a. All permutations of [4] with CSR
                  2     1    0    0
p(X ,X ,X ,X ) = X  +  X  + X  + X
   1  2  3  4     1     2    3    4
are as follows:
One-Line Notation
Cycle Notation
1 2 4 3
(1)(2)(34)
1 4 3 2
(1)(24)(3)
4 2 3 1
(14)(2)(3)
1 3 2 4
(1)(23)(4)
3 2 1 4
(13)(2)(4)
2 1 3 4
(12)(3)(4)

The cycle structure representation of permutations is commonly used in Polya-Burnside theory of counting.

The algorithm used is from the paper: U. Taylor and F. Ruskey, Fast Generation of Restricted Classes of Permutations, Manuscript 1995.


Programs available:
[Information Index] [Generation Index] [COS homepage]

Questions?? Email The wizard of COS.
(Please note that the suffix XXXX must be removed from the preceeding email address.)
It was last updated Wednesday, 10-May-2006 10:32:14 PDT.
[Error Opening Counter File -- Click for more info]
©Frank Ruskey, 1995-2003.