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

Information on permutations with exactly k left-to-right maxima

Let a = a(1),a(2),...,a(n) be a permutation of [n]={1,2,...,n}. We call a(i) a left-to-right maximum if a(i) > a(j) for all j < i.

The 6 permutations of [4] with exactly 3 left-to-right maxima are:

One-Line Notation
1 2 4 3
1 3 4 2
1 3 2 4
2 3 4 1
2 3 1 4
2 1 3 4

The Stirling numbers of the First Kind, c(n,k), which are given by the following well known recurrence relation:

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

count the number of permutations of [n] with exactly k left-to-right maxima. The numbers c(n,k) also count the number of permutations of [n] with exactly k cycles.

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.