Info on Cycle Structure

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:

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.
There have been 4218 visitors to this page since May 16, 2000 .
©Frank Ruskey, 1995-2003.