I am reading the book Combinatorics of Permutations (2nd edition) by Miklós Bóna, and in $\S$1.2 Alternating Runs, he states and proves a lemma on page 29 whose proof I do not fully understand.

Assume $n > 1$. Let $p := p_1 p_2 \dotsm p_n$ be a permutation in $S_n$. We say that $p$ changes direction at $i \in \left\{2,3,\ldots,n-1\right\}$ 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$ alternating runs if $p$ changes direction at $k-1$ points. Let $r(p)$ denote the number of alternating runs of $p$.

Let $G(n,k) := \lvert\{ p \in S_n : r(p) = k\}\rvert$, that is, $G(n,k)$ equals the number of permutations in $S_n$ having $k$ alternating runs. Consider the generating function $$ G_n(x) := \sum_{p \in S_n} x^{r(p)} = \sum_{k = 1}^{n-1} G(n,k) x^k $$

  • Observe that the coefficients of $G_n(x)$ are all even, because if $p \in S_n$ has $k$ alternating runs, then so does $p^c$, the complement of $p$, given by $p^c(i) := n + 1 - p(i)$.
  • One also empirically observes that $-1$ is a root of $G_n(x)$ with multiplicity $\lfloor n/2 \rfloor - 1$, by computing $G_n(x)$ for many small values of $n$.

Bóna gives a combinatorial proof that the second observation holds for all $n > 1$, and this is essentially the content of the lemma on page 29. Some more definitions before stating it:

Let $1 \leq j \leq \lfloor n/2 \rfloor$ and $p \in 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 S_n$, define $r_j(p)$ to be the number of alternating 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$ (the number of descents of a sequence $u_1, u_2, \ldots, u_k$ is the cardinality of the set $\{i \in [k-1] : u_i > u_{i+1}\}$). Define $t_j(p) := r_j(p) + s_j(p)$, and define $$ G_{n,j}(x) := \sum_{p} x^{t_j(p)}, $$ where the sum is taken over all the $(j+1)$-half-ascending permutations $p$ in $S_n$. Now, we have the following lemma on page 29:

LEMMA 1.41
For all $n > 1$ and $0 \leq j \leq \lfloor n/2 \rfloor -1$, we have $$ \frac{G_n(x)}{2(1+x)^j} = G_{n,j}(x). $$

The proof is purportedly by induction. The base cases are easy: this is how they go.

Base case I: $j=0$ and $n \geq 2$.

A $1$-half-ascending permutation $p \in S_n$ satisfies the single constraint $p_{n-1} < p_n$. Clearly, $r_0(p) = r(p)$ and $s_0(p) = 0$, so $t_0(p) = r(p)$. Since $r(p) = r(p^c)$, and for every $p \in S_n$ either $p$ or $p^c$ is $1$-half-ascending, we see that $$ \frac{G_n(x)}{2} = G_{n,0}(x), $$ as required.

Base Case II: $j = 1$ and $n \geq 4$.

A similar argument as in the previous case shows that $$ \frac{G_n(x)}{2} = \sum_{p : p_{n-3} < p_{n-2}} x^{r(p)}. $$ Let $I \colon S_n \to S_n$ be the involution defined by $I(p_1\dotsm p_{n-2}p_{n-1}p_n) := p_1\dotsm p_{n-2}p_n p_{n-1}$, that is, $I$ 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$. 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')$, so that $$ \sum_{q(p)} x^{r(q)} = \sum_{q'(p)} x^{t_1(q')} = G_{n,1}(x). $$ Hence, $$ \frac{G_n(x)}{2(1+x)} = G_{n,1}(x), $$ as required.

Now, how does one check that $r(q) = t_1(q')$? Note that it suffices to check this in the case $n = 4$, because it is only the last $4$ terms in the sequence $p_1,\dotsc,p_n$ that are really relevant here. Thus, one just writes down all $6$ pairs of elements of the form $(p,I(p))$ where $p \in S_4$ is $2$-half-ascending, and checks that $t_1(p)$ equals the number of alternating runs of that permutation between $p$ and $I(p)$ which has smaller number of alternating runs.

This completes the second base case.

Induction Step.

Now, this is what Bóna has to say regarding the induction step (on pages 29–30):

Now let us assume that we know that the statement holds for $j-1$ and prove it for $j$. 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. $\blacksquare$

Quite frankly, this is completely confusing and I can find no interpretation of this paragraph that actually works. For example, what does

. . .apply the induction hypothesis to the leftmost $n-2$ elements. . .

mean? How does one apply the induction hypothesis to individual elements? This is just one of many points due to which the given outline for the inductive step does not go through, in my opinion. Can anyone help me find out how to fix the proof, or even exhibit how the inductive step works in the case $n = 6$?


  • 1
    $\begingroup$ Before I read through this whole argument, let me mention one standard abuse of notation common in bijective combinatorics of permutations: Often one identifies a permutation $\pi \in S_n$ with the sequence $\left(\pi\left(1\right),\pi\left(2\right),\ldots,\pi\left(n\right)\right)$, which is an $n$-tuple containing each of the $n$ numbers $1,2,\ldots,n$ exactly once. Now, if $I$ is any $n$-element set of integers, then we can define a "fake permutation of $I$" to be an $n$-tuple containing each of the $n$ elements of $I$ exactly once. ... $\endgroup$ Jan 15 '20 at 21:32
  • 1
    $\begingroup$ ... The fake permutations of $I$ are in bijection with the permutations of $\left\{1,2,\ldots,n\right\}$, since we can just replace the smallest element of $I$ by $1$, the second-smallest element of $I$ by $2$, and so on. This bijection preserves all kinds of relative-order properties of these fake permutations (such as descents, inversions, alternating runs, peaks, major index, etc.). Thus, things that have been proven for permutations of $\left\{1,2,\ldots,n\right\}$ can be automatically inferred to be true for fake permutations of $n$-element sets $I$ of integers. This ... $\endgroup$ Jan 15 '20 at 21:34
  • 1
    $\begingroup$ ... is what people often mean when they talk of a subsequence of a permutation as if it was a permutation itself: In general, it is not, but it is a fake permutation, and so shares most order-theoretic properties of permutations. This is what I think goes on when Bóna applies the induction hypothesis "to individual elements" (actually, not to individual elements, but rather to a subsequence). $\endgroup$ Jan 15 '20 at 21:36
  • 1
    $\begingroup$ Okay, this proof is mind-bogglingly unrigorous and confusing even for bijective combinatorics standards; I'm not surprised it got published in JCTA (I assume referees just gave up?), but I wonder what it is looking for in Chapter 1 of a textbook. Are you interested in the specific proof, or just in some proof of Lemma 1.41, or just in the divisibility of $G_n\left(x\right)$ by $2\left(1+x\right)^j$ ? Because in any but the former case, I'd recommend ditching the bijective proof. $\endgroup$ Jan 15 '20 at 23:33
  • 2
    $\begingroup$ Crossposted on MathOverflow $\endgroup$
    – user279515
    May 16 '20 at 11:58

Your Answer

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