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:


It was last updated .