A combinatorial proof of the log-concavity of the numbers of permutations with \(k\) runs (Q1570759): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(6 intermediate revisions by 5 users not shown) | |||
Property / reviewed by | |||
Property / reviewed by: László A. Székely / rank | |||
Property / reviewed by | |||
Property / reviewed by: László A. Székely / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2126537558 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: math/9902020 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4320807 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4769056 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the Neggers-Stanley conjecture and the Eulerian polynomials / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5585020 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Inductive and injective proofs of log concavity results / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4294628 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 10:57, 30 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A combinatorial proof of the log-concavity of the numbers of permutations with \(k\) runs |
scientific article |
Statements
A combinatorial proof of the log-concavity of the numbers of permutations with \(k\) runs (English)
0 references
13 December 2000
0 references
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.
0 references
lattice paths
0 references
permutation
0 references
runs
0 references
generating function
0 references
log-concavity
0 references
Eulerian numbers
0 references