0
$\begingroup$

How does one prove that the # of n- element permutations with k left-right minima is given by the 1st kind stirling number?

I understand one should consider sigma(1)=n and sigma(1)=/=n, but I am totally lost on the process A left-right minimum of a permutation σ is an index σ(j) such that σ(j) < σ(i) for all i < j

$\endgroup$
0
$\begingroup$

Think of a permutation as a list of the numbers $1,\ldots,n$ in some order. One gets such a permutation by "inserting" $n$ somewhere in a permutation of $1,\ldots,n-1$. If one inserts it at the beginning one gains one left-right minimum. If one inserts it elsewhere the number of left-right minima remains the same.

So to get an $n$-permutation with $k$ left-right minima, either one prefixes an $(n-1)$-permutation with $k-1$ minima with an $n$, or else inserts an $n$ into an $(n-1)$-permutation with $k$ minima in one of the $n-1$ possible locations that's not at the front.

This gives the Stirling recurrence.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.