Information on permutations with exactly kcycles
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:
OneLine 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(n1,k1)
+ (n1) c(n1,k)
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, 10May2006 10:32:14 PDT.
>
There have been 4598 visitors to this page since May 16, 2000
.
©Frank Ruskey, 19952003.