# Induction step in Bóna and Ehrenborg's proof that the generating function of the alternating runs has -1 as a root of a certain multiplicity

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$$.

### References

I will try to write up a more transparent proof.

• Oh my, I didn't expect a reply from one of the authors themselves :)
– user82537
May 17 '20 at 5:04
• 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. May 21 '20 at 0:24
• That would be great, I look forward to your update :)
– user82537
May 22 '20 at 7:25
• Ok, my new, direct proof is at people.clas.ufl.edu/bona/files/altruns.pdf . May 25 '20 at 3:57
• 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.
– user82537
May 25 '20 at 13:54