This is a crosspost of a question I asked on Mathematics SE four months ago. Periodically bumping it and placing a bounty on it to attract more attention were to no avail. There are some comments underneath it by @darijgrinberg that I found useful, but the only conclusion in that discussion was that the proof really is confusing.

I am having trouble with Lemma 2.3 in the paper "A combinatorial proof of the log-concavity of the numbers of permutations with $k$ runs" by Bóna and Ehrenborg, and I was hoping to get some help in clarifying how the proof works.

Let $n > 1$. We say that the permutation $p \in \mathfrak{S}_n$ has $k$ alternating runs (or just $k$ runs) if $p$ changes direction at $k-1$ points, that is, if there are $k$ values of $i \in \left\{2,3,\ldots,n-1\right\}$ such that either $p_{i-1} < p_i > p_{i+1}$ or $p_{i-1} > p_i < p_{i+1}$. Let $r(p)$ be the number of runs of $p$, and $$R_n(x) := \sum_{p \in \mathfrak{S}_n} x^{r(p)}.$$ The authors give a combinatorial proof of the fact that $-1$ is a root of $R_n(x)$ with multiplicity $m = \lfloor (n - 2) / 2\rfloor$ for all $n \geq 4$.

Let $1 \leq j \leq m+1$ and $p \in \mathfrak{S}_n$. We say that $p$ is $j$-half-ascending if the last $j$ disjoint pairs of elements in the sequence $p_1,p_2,\dotsc,p_n$ are ascending, that is, if $p_{n+1-2i} < p_{n+2-2i}$ for all $1 \leq i \leq j$. For a $(j+1)$-half-ascending permutation $p \in \mathfrak{S}_n$, define $r_j(p)$ to be the number of runs of the subsequence $p_1,p_2,\dotsc,p_{n-2j}$, and $s_j(p)$ to be the number of descents of the subsequence $p_{n-2j},p_{n-2j+1},\dotsc,p_n$. Define $t_j(p) := r_j(p) + s_j(p)$, and let $$R_{n,j}(x) := \sum_{p} x^{t_j(p)},$$ where the sum is taken over all the $(j+1)$-half-ascending permutations $p$ in $\mathfrak{S}_n$. (In the paper, the sum is apparently taken over all $p \in \mathfrak{S}_n$, but that is surely a typo because $t_j(p)$ does not make sense for all $p \in \mathfrak{S}_n$.)

Lemma 2.3. For all $n \geq 4$ and $1 \leq j \leq m$, we have $$\frac{R_n(x)}{2(x+1)^j} = R_{n,j}(x).$$

The proof goes by induction. For the base case, we first note that $p$ and $p^c$ (the complement of $p$) have the same number of runs, so that $$ \frac{R_n(x)}{2} = \sum_{p : p_{n-3} < p_{n-2}} x^{r(p)}. $$ Let $I$ be the involution on $\mathfrak{S}_n$ that swaps $p_{n-1}$ and $p_n$. One can check that for every $p \in S_n$ such that $p_{n-3} < p_{n-2}$, $r(p)$ and $r(I(p))$ differ by $1$ (it suffices to check this only for the permutations in $\mathfrak{S}_4$, since it is only the last $4$ terms in the sequence $p_1,\dotsc,p_n$ that are really relevant here). Let $q \equiv q(p)$ be that permutation in the set $\{ p, I(p) \}$ with smaller number of alternating runs. Then, $$ \sum_{p : p_{n-3} < p_{n-2}} x^{r(p)} = \sum_{q(p)} \bigl(x^{r(q)} + x^{r(q)+1}\bigr) = (1+x) \sum_{q(p)} x^{r(q)}. $$ Let $q' \equiv q'(p)$ be that permutation in the set $\{ p, I(p) \}$ which is $2$-half-ascending. Then, it turns out that $r(q) = t_1(q')$ (again, it suffices to only check this for the permutations in $\mathfrak{S}_4$). So, $$ \sum_{q(p)} x^{r(q)} = \sum_{q'(p)} x^{t_1(q')} = R_{n,1}(x). $$ Hence, $R_n(x)/2(1+x) = R_{n,1}(x)$, as required.

Now, this is what the authors say regarding the induction step:

Now suppose we know the statement for $j-1$ and prove it for $j$. As above, apply $I$ to the two rightmost entries of our permutations to get pairs as in the initial case, and apply the induction hypothesis to the leftmost $n-2$ elements. By the induction hypothesis, the string of the leftmost $n-2$ elements can be replaced by a $j$-half-ascending $n-2$-permutation, and the number of runs can be replaced by the $t_{j-1}$-parameter. In particular, $p_{n-3} < p_{n-2}$ will hold, and therefore we can verify that our statement holds in both cases ($p_{n-2} < p_{n-1}$ or $p_{n-2} > p_{n-1}$) exactly as we did in the proof of the initial case. . .

This is quite confusing to me; I cannot interpret this paragraph in a way to actually make the proof work. I would be happy to even just see how the inductive step works in the case $n = 6$.



I will try to write up a more transparent proof.

  • 1
    $\begingroup$ Oh my, I didn't expect a reply from one of the authors themselves :) $\endgroup$
    – user82537
    May 17 '20 at 5:04
  • $\begingroup$ Update: I came up with what I think is a nice proof. (Somewhat similar to the one in the question, but much easier to visualize). Due to a talk I am going to give on Friday, and the 3-day week-end, it could be a week or so before I type it up, but I will definitely do it in that time frame. $\endgroup$ May 21 '20 at 0:24
  • $\begingroup$ That would be great, I look forward to your update :) $\endgroup$
    – user82537
    May 22 '20 at 7:25
  • 4
    $\begingroup$ Ok, my new, direct proof is at people.clas.ufl.edu/bona/files/altruns.pdf . $\endgroup$ May 25 '20 at 3:57
  • $\begingroup$ The proof is really nice, thank you for writing it up. I spotted a couple of minor typos: $R_n(z) = \color{red}{\sum_p} z^{\mathrm{run}(p)}$ in the introduction, and $G_{\color{red}{m}}$ in the statement of Lemma 2.6. $\endgroup$
    – user82537
    May 25 '20 at 13:54

Your Answer

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