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:
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.