I’m trying to solve a problem that counts the number of permutations of N elements with K maximums, where a maximum is defined as an element in the permutation that is greater than all of the elements to its left. For simplicity let’s consider the elements 1..n{1..n}.

As an example, for N=3 and K=2, the number is 3

1 3 2, 2 1 3

and

2 3 1

Here’s a recurrence for this that I have found:

P[n][k]=∑i

Clearly P(n,0)=0P(n,0)=0 for n>0n>0, since a non-empty permutation always has at least one left-to-right maximum, and the empty permutation has no left-to-right maxima, so P(0,n)=0P(0,n)=0 for n>0n>0. If (1)(1) is to hold for n=0n=0 and k=1k=1, we must have P(1,1)=P(0,0)P(1,1)=P(0,0), and since P(1,1)P(1,1) is certainly 11, we should set P(0,0)=1P(0,0)=1. It follows that

P(n,k)={n\brack k}\;,P(n,k)={n\brack k}\;,

the unsigned Stirling number of the first kind.

We can also establish this directly by exhibiting a bijection between permutations of [n][n] with kk left-to-right maxima and permutation of [n][n] with kk cycles.

If a permutation \pi\pi of [n][n] is written in cycle notation, we can put the representation in standard form by writing each cycle with its largest element first and listing the cycles in order of increasing maximum element, including 11-cycles; removing the parentheses yields a one-line permutation of [n][n] with kk left-to-right maxima. If we start with the latter, we can recover the original permutation in cycle notation by enclosing it in parentheses and inserting )( immediately before each left-to-right maximum except the first.

As an example, let n=8n=8, and consider the permutation \pi=(134)(27)(56)\pi=(134)(27)(56); as a permutation of [8][8] this has 44 cycles, the 11-cycle 88 being suppressed in the usual cycle notation. In standardized form this is (413)(65)(72)(8)(413)(65)(72)(8), yielding the one-line permutation \hat\pi=41365728\hat\pi=41365728 with 44 left-to-right maxima at 4,6,74,6,7, and 88, the maximum elements of their respective cycles in \pi\pi. Starting with \hat\pi\hat\pi in one-line form, we would enclose it in parentheses to get (41365728)(41365728) and then insert )( before 6,76,7, and 88 to get (413)(65)(72)(8)=\pi(413)(65)(72)(8)=\pi.