# Stirling numbers and left right minima

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

• – Lord Shark the Unknown Oct 5 '18 at 3:33
• Could you please remind us what a "left-right minimum" is? – Lord Shark the Unknown Oct 5 '18 at 3:36
• Yep, added the information in :) – user600384 Oct 5 '18 at 3:38

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.