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

Information on permutations with exactly k-cycles

It is well known that any permutation of [n]={1,2,...,n} can be written uniquely as a product of disjoint cycles. The objects generated here are all permutations of [n] that have exactly k cycles. For example, all permutations of [4] with exactly 3 cycles are:

One-Line Notation
Cycle Notation
2 1 3 4
(12)(3)(4)
3 2 1 4
(13)(2)(4)
4 2 3 1
(14)(2)(3)
1 3 2 4
(1)(23)(4)
1 4 3 2
(1)(24)(3)
1 2 4 3
(1)(2)(34)

Let c(n,k) denote the number of permutations of [n] with exactly k cycles. These numbers are known as the Stirling numbers of the First Kind, and satisfy the following recurrence relation:

c(n,k) = c(n-1,k-1) + (n-1) c(n-1,k)

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