[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
3 2 1 4
4 2 3 1
1 3 2 4
1 4 3 2
1 2 4 3

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 Friday, 27-Jan-2017 18:19:48 PST.
--> [Error Opening Counter File -- Click for more info]
©Frank Ruskey, 1995-2003.