A combinatorial proof of the log-concavity of the numbers of permutations with \(k\) runs (Q1570759): Difference between revisions

For a permutation \(p= p_1p_2\cdots p_n\) of the set \(\{1,2,\dots, n\}\), we say that \(p\) changes direction at \(i\) if either \(p_{i-1}< p_i> p_{i+1}\), or \(p_{i-1}> p_i> p_{i+1}\). We say that \(p\) has \(k\) runs if \(p\) changes direction at \(k-1\) indices \(i\). Let \(R(n,k)\) denote the number of permutations of \(n\) elements with exactly \(k\) runs. The main result of the paper is that the sequence \(R(n,k)\) is log-concave, i.e. for all \(k= 0,1,\dots, n-1\) one has \(R(n,k-1)\times R(n,k+1)\leq R(n,k)^2\); and in particular, the same sequence is unimodal. It is also shown that roughly half of the roots of the ordinary generating function \(R_n(x)= \sum^{n-1}_{k=1} R(n,k) x^k\) is equal to \(-1\), and a combinatorial interpretation is given for the term what remains when one divides \(R_n(x)\) by all of its \((x+1)\) factors. A by-product is a new proof to the log-concavity of Eulerian numbers.