Let $\sigma=\sigma_1 \sigma_2 \cdot \cdot \cdot \sigma_n \in S_n$ which means a permutation of the elements $1,2,...,n$. $\sigma_j$ is called a left-right maximum of $ \sigma$ if $\sigma_k <\sigma_j$ for all $k<j$. $a_{n,k}$ is the number of permutations in $S_n$ with exactly $k$ left right maxima. I have to show that $a_{n,k}=\frac{n!}{k!}[z^n](\log\frac{1}{1-z})^k$.

I know that these are the Stirling numbers of first kind, but I have no idea how to proove it. Do you have ideas? Please help me.

  • $\begingroup$ where does this $z$ come from ? $\endgroup$ – MJ73550 Apr 21 '16 at 17:25
  • $\begingroup$ @MJ73550 it means the coefficient of $z^n$ of $ f(z)$ $\endgroup$ – G Cab Apr 21 '16 at 17:28
  • $\begingroup$ sorry for I am not familiar with this kind of maths, what $f$ is supposed to be ? $\endgroup$ – MJ73550 Apr 21 '16 at 17:36
  • $\begingroup$ a sequence can be transformed into a formal power series, or z -transform, f(z) and $\left[ {z^{\,n} } \right]f(z)$ gives you back the $n$-th element of the sequence, whose transform is f(z). see en.wikipedia.org/wiki/Formal_power_series $\endgroup$ – G Cab Apr 21 '16 at 17:53
  • $\begingroup$ @Mathfreak I am not sure to grasp exactly the meaning of your definition. it seems to me that the permutation with exactly $k$ right maxima is the one which is strictly increasing till position $k$, is that right? $\endgroup$ – G Cab Apr 21 '16 at 18:08

Ask how we can obtain a permutation on $[n+1]$ having $k$ left-right maxima from a permutation on $[n]$ by incrementing all elements of the latter and adding a smallest element, one. A permutation on $[n]$ having $k-1$ maxima produces a permutation on $[n+1]$ having $k$ maxima if we place the smallest element in front, for a contribution of $\left[n\atop k-1\right]$ (we gain a maximum from the new first element). On the other hand if we place the smallest element anywhere else ($n$ possibilities) in a permutation on $[n]$ having $k$ maxima it does not affect the these, for a contribution of $n \left[n\atop k\right].$ This yields the recurrence

$$\left[n+1\atop k\right] = \left[n\atop k-1\right] + n \left[n\atop k\right]$$

which is the Stirling number recurrence.


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.