Counting permutations with k maximums

Question

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}$.

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] = \sum_{i=1}^{i<k} P[n-i][j-1] * {n-1 \choose n-i} * (i-1)! = \sum_{i=1}^{i<k} P[n-i][j-1] * \frac{(n-1)!}{(n-i)!}$

Here's how I got to this: I try to put every digit $1..n$ on the first position and then I need to calculate the number of permutations of n-i elements with j-1 maximums (because i already have a maximum on the first position). n-i because the elements $1..i-1$ can never be maximums. And once i got that number I figure out the number of ways i can arrange all those since I have n-1 total elements.

Now I know there's a simpler recurrence for this, but I can't figure out how to get to it from what I have so far.

The simpler recurrence by the way is

$P[n][k] = (n-1) * P[n-1][k] + P[n-1][k-1]$

and is known as the Stirling number of the second kind if I'm not mistaken.

Answer 1

I will write $P(n,k)$ for your $P[n][k]$.

Suppose that $\pi$ is a permutation of $[n]$ with $k$ left-to-right maxima. Let $\pi'$ be the permutation of $[n+1]\setminus\{1\}$ obtained by setting $\pi_i'=\pi_i+1$ for $i\in[n]$; note that $\pi'$ has left-to-right maxima in the same positions as $\pi$. We can now get a permutation of $[n+1]$ by inserting $1$ into the permutation $\pi'=\pi_1'\pi_2'\ldots\pi_n'$ in any of the $n+1$ possible slots. If we insert it anywhere except before $\pi_1'$, we get a permutation of $[n+1]$ with $k$ left-to-right maxima, and it’s easy to see that every permutation of $[n+1]$ with $k$ left-to-right maxima that does not begin with $1$ can be obtained in this way. Thus, there are $nP(n,k)$ permtations of $[n+1]$ with $k$ left-to-right maxima that do not start with $1$.

We can get the permutations of $[n+1]$ that start with $1$ and have $k$ left-to-right maxima by starting with a permutation of $[n]$ with $k-1$ left-to-right maxima, increasing each entry by $1$ as before, and inserting $1$ at the beginning of the permutation. Thus, there are $P(n,k-1)$ permutations of $[n+1]$ that start with $1$ and have $k$ left-to-right maxima.

Combining results, we see have the recurrence

$$P(n+1,k)=nP(n,k)+P(n,k-1)\;,\tag{1}$$

which is identical to the recurrence

$${{n+1}\brack k}=n{n\brack k}+{n\brack{k-1}}$$

for unsigned Stirling numbers of the first kind. The initial conditions for the Stirling numbers are

$${0\brack 0}=1,\quad\text{and}\quad{n\brack 0}={0\brack n}=0\text{ for }n>0\;.$$

Clearly $P(n,0)=0$ for $n>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)=0$ for $n>0$. If $(1)$ is to hold for $n=0$ and $k=1$, we must have $P(1,1)=P(0,0)$, and since $P(1,1)$ is certainly $1$, we should set $P(0,0)=1$. It follows that

$$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]$ with $k$ left-to-right maxima and permutations of $[n]$ with $k$ cycles.

If a permutation $\pi$ of $[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 $1$-cycles; removing the parentheses yields a one-line permutation of $[n]$ with $k$ 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=8$, and consider the permutation $\pi=(134)(27)(56)$; as a permutation of $[8]$ this has $4$ cycles, the $1$-cycle $8$ being suppressed in the usual cycle notation. In standardized form this is $(413)(65)(72)(8)$, yielding the one-line permutation $\hat\pi=41365728$ with $4$ left-to-right maxima at $4,6,7$, and $8$, the maximum elements of their respective cycles in $\pi$. Starting with $\hat\pi$ in one-line form, we would enclose it in parentheses to get $(41365728)$ and then insert )( before $6,7$, and $8$ to get $(413)(65)(72)(8)=\pi$.