$\newcommand{\cyc}{\operatorname{cyc}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\BB}{\mathbf{B}}
\newcommand{\AA}{\mathbf{A}}
$
PART 2 OF 3
[This is part of a long answer, which I had to split into 3 posts.
Go to part 1. Go to part 2. Go to part 3.]
3. Proof of Theorem 2
The proof of Theorem 2 is bijective, and, as most bijective proofs, it
involves a lot of combinatorial verification that is quick if you know your
way around the symmetric groups but turns into awkward drudgery when you try
to write it up. Garsia conveniently sweeps it under the rug in his preprint
with the magic broom of "easily seen", and I cannot blame him for doing that
in a preprint that he did not even publish himself (also, he gives two proofs
for Theorem 2 in that preprint). I have less of a good excuse to skip it; if
I'm already copying all the ideas from Garsia, I guess I should at least
improve on the exposition. So I'm going to give an undergrad-friendly version
of the proof, with all the details included. (It's an undergrad-friendly
theorem after all -- you just need to know what a group ring is.)
For this whole section, let us fix $a \in \left\{ 0,1,\ldots,n-1 \right\}$.
Thus, $0\leq a\leq n-1$, so that $n-1\geq0$ and thus $n\geq1$.
Also, from $a \in \left\{ 0,1,\ldots,n-1 \right\}$, we obtain
$a+1 \in \left[ n \right]$.
For every $i\in\left[ n\right] $, we define a permutation $z_i\in S_n$
by
\begin{equation}
z_i=\cyc_{1,2,\ldots,i}.
\label{eq.defzi} \tag{3.1}
\end{equation}
For every $b\in\left[ n\right] $, $i\in\left[ n\right] $ and $j\in\left[
n\right] $, we define a subset $B_{b,j\to i}$ of $B_{b}$ by
\begin{equation}
B_{b,j\to i}=\left\{ \sigma\in B_{b}\ \mid\ \sigma\left( j\right)
=i\right\} .
\label{eq.defBbji} \tag{3.2}
\end{equation}
The next two lemmas will build up bijections between certain pieces of $B_a$
and $B_{a+1}$.
Lemma 7. Let $i\in\left[ a\right] $. Let $j\in\left[ n\right] $. Then,
the map
\begin{align*}
B_{a,1\to i} & \to B_{a,j\to i},\\
\alpha & \mapsto\alpha\circ z_j
\end{align*}
is well-defined and a bijection.
Proof of Lemma 7. The definition of $z_j$ yields $z_j
=\cyc_{1,2,\ldots,j}$. Hence, $z_j\left( j\right)
=1$ and therefore $z_j^{-1}\left( 1\right) =j$. Also, from $z_j
=\cyc_{1,2,\ldots,j}$, we obtain $z_j^{-1}=\left(
\cyc_{1,2,\ldots,j}\right) ^{-1}
=\cyc_{j,j-1,\ldots,1}$.
From $i\in\left[ a\right] $, we obtain $i\leq a\leq n-1\leq n$ and thus
$i\in\left[ n\right] $.
The definition of $B_{a,1\to i}$ yields
\begin{equation}
B_{a,1\to i}=\left\{ \sigma\in B_{a}\ \mid\ \sigma\left( 1\right)
=i\right\} .
\end{equation}
The definition of $B_{a,j\to i}$ yields
\begin{equation}
B_{a,j\to i}=\left\{ \sigma\in B_{a}\ \mid\ \sigma\left( j\right)
=i\right\} .
\end{equation}
Let $\alpha\in B_{a,1\to i}$. We shall show that $\alpha\circ z_j\in
B_{a,j\to i}$.
We have $\alpha\in B_{a,1\to i}=\left\{ \sigma\in B_{a}\ \mid
\ \sigma\left( 1\right) =i\right\} $. In other words, $\alpha\in B_a$ and
$\alpha\left( 1\right) =i$. From $\alpha\in B_a$, we obtain
\begin{equation}
\alpha^{-1}\left( a+1\right) <\alpha^{-1}\left( a+2\right) <\cdots
<\alpha^{-1}\left( n\right)
\label{pf.l7.0} \tag{3.3}
\end{equation}
(by the definition of $B_a$).
Moreover, for each $k\in\left\{ a+1,a+2,\ldots,n\right\} $, we have
\begin{equation}
\alpha^{-1}\left( k\right) \in\left\{ 2,3,\ldots,n\right\} .
\label{pf.l7.1} \tag{3.4}
\end{equation}
[Proof: Let $k\in\left\{ a+1,a+2,\ldots,n\right\} $. We must show that
$\alpha^{-1}\left( k\right) \in\left\{ 2,3,\ldots,n\right\} $. Indeed,
assume the contrary. Thus, $\alpha^{-1}\left( k\right) \notin\left\{
2,3,\ldots,n\right\} $, so that $\alpha^{-1}\left( k\right) \in\left[
n\right] \setminus\left\{ 2,3,\ldots,n\right\} =\left\{ 1\right\} $.
Thus, $\alpha^{-1}\left( k\right) =1$. Hence, $k=\alpha\left( 1\right)
=i\leq a$. This contradicts $k>a$ (which follows from $k\in\left\{
a+1,a+2,\ldots,n\right\} $). This contradiction completes our proof of \eqref{pf.l7.1}.]
Recall that $z_j^{-1}=\cyc_{j,j-1,\ldots,1}$. Thus,
the one-line notation of $z_j^{-1}$ is $\left( j,1,2,\ldots
,j-1,j+1,j+2,\ldots,n\right) $. This reveals that the map $z_j^{-1}$ is
strictly increasing on the interval $\left\{ 2,3,\ldots,n\right\} $. Now,
the $n-a$ integers $\alpha^{-1}\left( a+1\right) ,\alpha^{-1}\left(
a+2\right) ,\ldots,\alpha^{-1}\left( n\right) $ belong to the interval
$\left\{ 2,3,\ldots,n\right\} $ (by \eqref{pf.l7.1}) and are listed in
strictly increasing order (by \eqref{pf.l7.0}). Hence, applying the map
$z_j^{-1}$ to them preserves this strictly increasing order (since the map
$z_j^{-1}$ is strictly increasing on the interval $\left\{ 2,3,\ldots
,n\right\} $). In other words,
\begin{equation}
z_j^{-1}\left( \alpha^{-1}\left( a+1\right) \right) <z_j^{-1}\left(
\alpha^{-1}\left( a+2\right) \right) <\cdots<z_j^{-1}\left( \alpha
^{-1}\left( n\right) \right) .
\end{equation}
This rewrites as
\begin{equation}
\left( \alpha\circ z_j\right) ^{-1}\left( a+1\right) <\left(
\alpha\circ z_j\right) ^{-1}\left( a+2\right) <\cdots<\left( \alpha\circ
z_j\right) ^{-1}\left( n\right)
\end{equation}
(since $z_j^{-1}\left( \alpha^{-1}\left( k\right) \right) =\left(
\alpha\circ z_j\right) ^{-1}\left( k\right) $ for each $k\in\left[
n\right] $).
In other words, the permutation $\alpha\circ z_j$ belongs to
$B_a$ (by the definition of $B_a$).
So we have shown that $\alpha\circ z_j\in B_a$. Combining this with
$\left( \alpha\circ z_j\right) \left( j\right) =\alpha\left(
\underbrace{z_j\left( j\right) }_{=1}\right) =\alpha\left( 1\right)
=i$, we obtain
\begin{equation}
\alpha\circ z_j\in\left\{ \sigma\in B_{a}\ \mid\ \sigma\left( j\right)
=i\right\} =B_{a,j\to i}.
\end{equation}
Forget that we fixed $\alpha$. We thus have shown that $\alpha\circ z_j\in
B_{a,j\to i}$ for each $\alpha\in B_{a,1\to i}$. Thus, the
map
\begin{align*}
B_{a,1\to i} & \to B_{a,j\to i},\\
\alpha & \mapsto\alpha\circ z_j
\end{align*}
is well-defined. Let us denote this map by $\mathbf{f}$. It remains to show
that $\mathbf{f}$ is a bijection.
On the other hand, let $\beta\in B_{a,j\to i}$. We shall prove that
$\beta\circ z_j^{-1}\in B_{a,1\to i}$.
Let $\gamma$ be the permutation $\beta \circ z_j^{-1} \in S_n$.
Thus, $\gamma^{-1} = \left( \beta \circ z_j^{-1} \right)^{-1}
= z_j \circ \beta^{-1}$.
Hence, each $k \in \left[ n\right]$ satisfies
$\gamma^{-1}\left(k\right) = \left( z_j \circ \beta^{-1} \right) \left( k \right)
= z_j \left( \beta^{-1} \left( k \right) \right)$.
We have $\beta\in B_{a,j\to i}=\left\{ \sigma\in B_{a}\ \mid
\ \sigma\left( j\right) =i\right\} $ (by the definition of
$B_{a,j\to i}$). In other words, $\beta\in B_a$ and $\beta\left(
j\right) =i$. From $\beta\in B_a$, we obtain
\begin{equation}
\beta^{-1}\left( a+1\right) <\beta^{-1}\left( a+2\right) <\cdots
<\beta^{-1}\left( n\right)
\label{pf.l7.5} \tag{3.5}
\end{equation}
(by the definition of $B_a$).
Moreover, for each $k\in\left\{ a+1,a+2,\ldots,n\right\} $, we have
\begin{equation}
\beta^{-1}\left( k\right) \in\left[ n\right] \setminus\left\{ j\right\}
.
\label{pf.l7.6} \tag{3.6}
\end{equation}
[Proof: Let $k\in\left\{ a+1,a+2,\ldots,n\right\} $. We must show that
$\beta^{-1}\left( k\right) \in\left[ n\right] \setminus\left\{ j\right\}
$. Indeed, assume the contrary. Thus, $\beta^{-1}\left( k\right)
\notin\left[ n\right] \setminus\left\{ j\right\} $, so that $\beta
^{-1}\left( k\right) \in\left[ n\right] \setminus\left( \left[ n\right]
\setminus\left\{ j\right\} \right) =\left\{ j\right\} $. Thus,
$\beta^{-1}\left( k\right) =j$. Hence, $k=\beta\left( j\right) =i\leq a$.
This contradicts $k>a$ (which follows from $k\in\left\{ a+1,a+2,\ldots
,n\right\} $). This contradiction completes our proof of \eqref{pf.l7.6}.]
Recall that $z_j=\cyc_{1,2,\ldots,j}$. Hence, the
one-line notation of $z_j$ is $\left( 2,3,\ldots,j,1,j+1,j+2,\ldots
,n\right) $. This reveals that the map $z_j$ is strictly increasing on the
subset $\left[ n\right] \setminus\left\{ j\right\}$ of its domain. Now, the $n-a$ integers $\beta^{-1}\left( a+1\right) ,\beta^{-1}\left( a+2\right) ,\ldots,\beta^{-1}\left( n\right) $ belong to this subset $\left[ n\right] \setminus\left\{ j\right\} $ (by \eqref{pf.l7.6}) and are listed in strictly
increasing order (by \eqref{pf.l7.5}). Hence, applying the map $z_j$ to them preserves this strictly increasing order (since the map $z_j$ is strictly
increasing on the subset $\left[ n\right] \setminus\left\{ j\right\}$). In other words,
\begin{equation}
z_j\left( \beta^{-1}\left( a+1\right) \right) <z_j\left( \beta
^{-1}\left( a+2\right) \right) <\cdots<z_j\left( \beta^{-1}\left(
n\right) \right) .
\end{equation}
This rewrites as
\begin{equation}
\gamma^{-1}\left( a+1\right) <
\gamma^{-1}\left( a+2\right) <
\cdots
<\gamma^{-1}\left( n\right)
\end{equation}
(since each $k \in \left[ n\right]$ satisfies
$\gamma^{-1}\left(k\right) = z_j \left( \beta^{-1} \left( k \right) \right)$).
In other words, the permutation $\gamma$ belongs to $B_a$
(by the definition of $B_a$). In other words, $\gamma \in B_a$.
Also, from $\gamma = \beta \circ z_j^{-1}$, we obtain
$\gamma\left(1\right)
= \left( \beta\circ z_j^{-1}\right) \left( 1\right)
= \beta\left( \underbrace{z_j^{-1}\left( 1\right) }_{=j}\right)
=\beta\left( j\right) =i$.
Combining this with $\gamma \in B_a$, we obtain
\begin{equation}
\gamma\in\left\{ \sigma\in B_a \ \mid\ \sigma\left(
1\right) =i\right\} =B_{a,1\to i}.
\end{equation}
Hence, $\beta\circ z_j^{-1} = \gamma \in B_{a, 1\to i}$.
Forget that we fixed $\beta$. We thus have shown that $\beta\circ z_j
^{-1}\in B_{a,1\to i}$ for each $\beta\in B_{a,j\to i}$. Thus,
the map
\begin{align*}
B_{a,j\to i} & \to B_{a,1\to i},\\
\beta & \mapsto\beta\circ z_j^{-1}
\end{align*}
is well-defined. Let us denote this map by $\mathbf{g}$.
The map $\mathbf{f}$ multiplies each permutation $\sigma$ in its domain by
$z_j$ on the right, whereas the map $\mathbf{g}$ multiplies each permutation $\sigma$ in its domain by $z_j^{-1}$ on the right. Thus, these two maps $\mathbf{f}$ and $\mathbf{g}$ are mutually inverse. Hence, the map $\mathbf{f}$ is a bijection. Since $\mathbf{f}$ was defined as the map
\begin{align*}
B_{a,1\to i} & \to B_{a,j\to i},\\
\alpha & \mapsto\alpha\circ z_j,
\end{align*}
we thus conclude that this map
\begin{align*}
B_{a,1\to i} & \to B_{a,j\to i},\\
\alpha & \mapsto\alpha\circ z_j
\end{align*}
is a bijection. This proves Lemma 7. $\blacksquare$
Lemma 8. Let $j\in\left[ n\right] $. Then, the map
\begin{align*}
B_{a,1\to a+1} & \to B_{a+1,j\to a+1},\\
\alpha & \mapsto\alpha\circ z_j
\end{align*}
is well-defined and a bijection.
Proof of Lemma 8. The definition of $z_j$ yields
$z_j =\cyc_{1,2,\ldots,j}$. Hence,
$z_j\left( j\right) =1$ and therefore
$z_j^{-1}\left( 1\right) =j$. Also, from
$z_j =\cyc_{1,2,\ldots,j}$, we obtain
$z_j^{-1} = \left( \cyc_{1,2,\ldots,j}\right) ^{-1}
=\cyc_{j,j-1,\ldots,1}$.
The definition of $B_{a,1\to a+1}$ yields
\begin{equation}
B_{a,1\to a+1}
= \left\{ \sigma\in B_{a}\ \mid\ \sigma\left( 1\right) =a+1\right\} .
\end{equation}
The definition of $B_{a+1,j\to a+1}$ yields
\begin{equation}
B_{a+1,j\to a+1}
= \left\{ \sigma\in B_{a+1}\ \mid\ \sigma\left( j\right) =a+1\right\} .
\end{equation}
Recall that $B_{a+1}$ is the set of all permutations $\sigma\in S_n$
satisfying $\sigma^{-1}\left( a+2\right) <\sigma^{-1}\left( a+3\right)
<\cdots<\sigma^{-1}\left( n\right) $ (by the definition of $B_{a+1}$).
Let $\alpha\in B_{a,1\to a+1}$. We shall show that $\alpha\circ
z_j\in B_{a+1,j\to a+1}$.
We have $\alpha\in B_{a,1\to a+1}=\left\{ \sigma\in B_{a}
\ \mid\ \sigma\left( 1\right) =a+1\right\} $. In other words, $\alpha\in
B_a$ and $\alpha\left( 1\right) =a+1$. From $\alpha\in B_a$, we obtain
\begin{equation}
\alpha^{-1}\left( a+1\right) <\alpha^{-1}\left( a+2\right) <\cdots
<\alpha^{-1}\left( n\right)
\end{equation}
(by the definition of $B_a$). Hence,
\begin{equation}
\alpha^{-1}\left( a+2\right) <\alpha^{-1}\left( a+3\right) <\cdots
<\alpha^{-1}\left( n\right) .
\label{pf.l8.0} \tag{3.7}
\end{equation}
Moreover, for each $k\in\left\{ a+2,a+3,\ldots,n\right\} $, we have
\begin{equation}
\alpha^{-1}\left( k\right) \in\left\{ 2,3,\ldots,n\right\} .
\label{pf.l8.1} \tag{3.8}
\end{equation}
[Proof: Let $k\in\left\{ a+2,a+3,\ldots,n\right\} $. We must show that
$\alpha^{-1}\left( k\right) \in\left\{ 2,3,\ldots,n\right\} $. Indeed,
assume the contrary. Thus, $\alpha^{-1}\left( k\right) \notin\left\{
2,3,\ldots,n\right\} $, so that $\alpha^{-1}\left( k\right) \in\left[
n\right] \setminus\left\{ 2,3,\ldots,n\right\} =\left\{ 1\right\} $.
Thus, $\alpha^{-1}\left( k\right) =1$. Hence, $k=\alpha\left( 1\right)
=a+1$. This contradicts $k>a+1$ (which follows from $k\in\left\{
a+2,a+3,\ldots,n\right\} $). This contradiction completes our proof of \eqref{pf.l8.1}.]
Recall that $z_j^{-1}=\cyc_{j,j-1,\ldots,1}$. Thus,
the one-line notation of $z_j^{-1}$ is $\left( j,1,2,\ldots
,j-1,j+1,j+2,\ldots,n\right) $. This reveals that the map $z_j^{-1}$ is
strictly increasing on the interval $\left\{ 2,3,\ldots,n\right\} $. Now,
the $n-a-1$ integers $\alpha^{-1}\left( a+2\right) ,\alpha^{-1}\left(
a+3\right) ,\ldots,\alpha^{-1}\left( n\right) $ belong to the interval
$\left\{ 2,3,\ldots,n\right\} $ (by \eqref{pf.l8.1}) and are listed in
strictly increasing order (by \eqref{pf.l8.0}). Hence, applying the map
$z_j^{-1}$ to them preserves this strictly increasing order (since the map
$z_j^{-1}$ is strictly increasing on the interval $\left\{ 2,3,\ldots
,n\right\} $). In other words,
\begin{equation}
z_j^{-1}\left( \alpha^{-1}\left( a+2\right) \right) <z_j^{-1}\left(
\alpha^{-1}\left( a+3\right) \right) <\cdots<z_j^{-1}\left( \alpha
^{-1}\left( n\right) \right) .
\end{equation}
This rewrites as
\begin{equation}
\left( \alpha\circ z_j\right) ^{-1}\left( a+2\right) <\left(
\alpha\circ z_j\right) ^{-1}\left( a+3\right) <\cdots<\left( \alpha\circ
z_j\right) ^{-1}\left( n\right)
\end{equation}
(since $z_j^{-1}\left( \alpha^{-1}\left( k\right) \right) =\left(
\alpha\circ z_j\right) ^{-1}\left( k\right) $ for each $k\in\left[
n\right] $).
In other words, the permutation $\alpha\circ z_j$ belongs to
$B_{a+1}$ (by the definition of $B_{a+1}$).
So we have shown that $\alpha\circ z_j\in B_{a+1}$. Combining this with
$\left( \alpha\circ z_j\right) \left( j\right) =\alpha\left(
\underbrace{z_j\left( j\right) }_{=1}\right) =\alpha\left( 1\right)
=i$, we obtain
\begin{equation}
\alpha\circ z_j\in\left\{ \sigma\in B_{a+1}\ \mid\ \sigma\left( j\right)
=i\right\} =B_{a+1,j\to a+1}.
\end{equation}
Forget that we fixed $\alpha$. We thus have shown that $\alpha\circ z_j\in
B_{a+1,j\to a+1}$ for each $\alpha\in B_{a,1\to a+1}$. Thus,
the map
\begin{align*}
B_{a,1\to a+1} & \to B_{a+1,j\to a+1},\\
\alpha & \mapsto\alpha\circ z_j
\end{align*}
is well-defined. Let us denote this map by $\mathbf{f}$. It remains to show
that $\mathbf{f}$ is a bijection.
On the other hand, let $\beta\in B_{a+1,j\to a+1}$. We shall prove
that $\beta\circ z_j^{-1}\in B_{a,1\to a+1}$.
Let $\gamma$ be the permutation $\beta \circ z_j^{-1} \in S_n$.
Thus, $\gamma^{-1} = \left( \beta \circ z_j^{-1} \right)^{-1}
= z_j \circ \beta^{-1}$.
Hence, each $k \in \left[ n\right]$ satisfies
$\gamma^{-1}\left(k\right) = \left( z_j \circ \beta^{-1} \right) \left( k \right)
= z_j \left( \beta^{-1} \left( k \right) \right)$.
We have $\beta\in B_{a+1,j\to a+1}=\left\{ \sigma\in B_{a+1}
\ \mid\ \sigma\left( j\right) =a+1\right\} $ (by the definition of
$B_{a+1,j\to a+1}$). In other words, $\beta\in B_{a+1}$ and
$\beta\left( j\right) =a+1$. From $\beta\in B_{a+1}$, we obtain
\begin{equation}
\beta^{-1}\left( a+2\right) <\beta^{-1}\left( a+3\right) <\cdots
<\beta^{-1}\left( n\right)
\label{pf.l8.5} \tag{3.9}
\end{equation}
(by the definition of $B_{a+1}$).
Moreover, for each $k\in\left\{ a+2,a+3,\ldots,n\right\} $, we have
\begin{equation}
\beta^{-1}\left( k\right) \in\left[ n\right] \setminus\left\{ j\right\}
.
\label{pf.l8.6} \tag{3.10}
\end{equation}
[Proof: Let $k\in\left\{ a+2,a+3,\ldots,n\right\} $. We must show that
$\beta^{-1}\left( k\right) \in\left[ n\right] \setminus\left\{ j\right\}
$. Indeed, assume the contrary. Thus, $\beta^{-1}\left( k\right)
\notin\left[ n\right] \setminus\left\{ j\right\} $, so that $\beta
^{-1}\left( k\right) \in\left[ n\right] \setminus\left( \left[ n\right]
\setminus\left\{ j\right\} \right) =\left\{ j\right\} $. Thus,
$\beta^{-1}\left( k\right) =j$. Hence, $k=\beta\left( j\right) =a+1$. This
contradicts $k>a+1$ (which follows from $k\in\left\{ a+2,a+3,\ldots
,n\right\} $). This contradiction completes our proof of \eqref{pf.l8.6}.]
Recall that $z_j=\cyc_{1,2,\ldots,j}$. Hence, the
one-line notation of $z_j$ is $\left( 2,3,\ldots,j,1,j+1,j+2,\ldots
,n\right) $. This reveals that the map $z_j$ is strictly increasing on the
subset $\left[ n\right] \setminus\left\{ j\right\}$ of its domain. Now, the
$n-a-1$ integers $\beta^{-1}\left( a+2\right) ,\beta^{-1}\left( a+3\right)
,\ldots,\beta^{-1}\left( n\right) $ belong to this subset $\left[ n\right]
\setminus\left\{ j\right\}$ (by \eqref{pf.l8.6}) and are listed in strictly
increasing order (by \eqref{pf.l8.5}). Hence, applying the map $z_j$ to them
preserves this strictly increasing order (since the map $z_j$ is strictly
increasing on the subset $\left[ n\right] \setminus\left\{ j\right\}$). In
other words,
\begin{equation}
z_j\left( \beta^{-1}\left( a+2\right) \right) <z_j\left( \beta
^{-1}\left( a+3\right) \right) <\cdots<z_j\left( \beta^{-1}\left(
n\right) \right) .
\end{equation}
This rewrites as
\begin{equation}
\gamma^{-1}\left( a+2\right) <
\gamma^{-1}\left( a+3\right) <
\cdots<
\gamma^{-1}\left( n\right)
\label{pf.l8.7} \tag{3.11}
\end{equation}
(since each $k \in \left[ n\right]$ satisfies
$\gamma^{-1}\left(k\right) = z_j \left( \beta^{-1} \left( k \right) \right)$).
Now, we claim that
\begin{equation}
\gamma^{-1}\left( a+1\right) <
\gamma^{-1}\left( a+2\right) <
\cdots<
\gamma^{-1}\left( n\right) .
\label{pf.l8.8} \tag{3.12}
\end{equation}
[Proof: If $a+1\geq n$, then the chain of inequalities \eqref{pf.l8.8} is
vacuously true. Thus, we WLOG assume that $a+1<n$. Hence, $a+2\in\left[
n\right] $, so that $\gamma^{-1}\left( a+2\right)$ is well-defined.
The map $\gamma^{-1}$ is a permutation in
$S_n$, and thus is injective. Hence, from $a+1\neq a+2$, we obtain
$\gamma^{-1}\left( a+1\right) \neq \gamma^{-1}\left( a+2\right) $.
But from $\beta\left( j\right) =a+1$, we obtain $\beta^{-1}\left(
a+1\right) =j$. Recall that
each $k \in \left[ n\right]$ satisfies
$\gamma^{-1}\left(k\right)
= z_j \left( \beta^{-1} \left( k \right) \right)$.
Applying this to $k = a+1$, we obtain
\begin{equation}
\gamma^{-1}\left( a+1\right)
= z_j\left( \underbrace{\beta^{-1}\left( a+1\right) }_{=j}\right)
= z_j\left( j\right) =1
\leq\gamma^{-1}\left( a+2\right)
\end{equation}
(since $\gamma^{-1}\left( a+2\right) \in\left[ n\right] $).
Combining this with $\gamma^{-1}\left( a+1\right) \neq
\gamma^{-1}\left( a+2\right) $, we obtain the strict inequality
$\gamma^{-1}\left( a+1\right) < \gamma^{-1}\left( a+2\right) $.
Combining this with \eqref{pf.l8.7}, we obtain
\begin{equation}
\gamma^{-1}\left( a+1\right) <
\gamma^{-1}\left( a+2\right) <
\cdots<
\gamma^{-1}\left( n\right) .
\end{equation}
This proves \eqref{pf.l8.8}.]
So the inequalities \eqref{pf.l8.8} hold. In other words, the permutation
$\gamma$ belongs to $B_a$ (by the definition of $B_a$).
That is, $\gamma \in B_a$.
Also, from $\gamma = \beta \circ z_j^{-1}$, we obtain
$\gamma\left(1\right)
= \left( \beta\circ z_j^{-1}\right) \left( 1\right)
= \beta\left( \underbrace{z_j^{-1}\left( 1\right) }_{=j}\right)
= \beta\left( j\right) =a+1$.
Combining this with $\gamma \in B_a$, we obtain
\begin{equation}
\gamma \in\left\{ \sigma\in B_{a}\ \mid\ \sigma\left(
1\right) =a+1\right\} =B_{a,1\to a+1}.
\end{equation}
Thus, $\gamma = \beta\circ z_j^{-1} \in B_{a, 1\to a+1}$.
Forget that we fixed $\beta$. We thus have shown that $\beta\circ z_j
^{-1}\in B_{a,1\to a+1}$ for each $\beta\in B_{a+1,j\to a+1}$.
Thus, the map
\begin{align*}
B_{a+1,j\to a+1} & \to B_{a,1\to a+1},\\
\beta & \mapsto\beta\circ z_j^{-1}
\end{align*}
is well-defined. Let us denote this map by $\mathbf{g}$.
The map $\mathbf{f}$ multiplies each permutation $\sigma$ in its domain by
$z_j$ on the right, whereas the map $\mathbf{g}$ multiplies each permutation
$\sigma$ in its domain by $z_j^{-1}$ on the right. Thus, these two maps
$\mathbf{f}$ and $\mathbf{g}$ are mutually inverse. Hence, the map
$\mathbf{f}$ is a bijection. Since $\mathbf{f}$ was defined as the map
\begin{align*}
B_{a,1\to a+1} & \to B_{a+1,j\to a+1},\\
\alpha & \mapsto\alpha\circ z_j,
\end{align*}
we thus conclude that this map
\begin{align*}
B_{a,1\to a+1} & \to B_{a+1,j\to a+1},\\
\alpha & \mapsto\alpha\circ z_j
\end{align*}
is a bijection. This proves Lemma 8. $\blacksquare$
Lemmas 7 and 8 establish bijections between some subsets of $B_a$ and of
$B_{a+1}$. The next lemma shows that the subsets $B_{a,1\to i}$ for
$i \in \left[ a+1 \right]$ cover $B_a$:
Lemma 9. Let $\alpha\in B_a$. Then,
$\alpha\left( 1\right) \in \left[ a+1 \right]$.
Proof of Lemma 9. Assume the contrary. Thus, $\alpha\left( 1\right)
\notin\left[ a+1\right] $. Hence, $\alpha\left( 1\right) >a+1$. Hence,
$a+1<\alpha\left( 1\right) \leq n$. Thus, both $a+1$ and $\alpha\left(
1\right) $ are elements of the interval $\left\{ a+1,a+2,\ldots,n\right\} $.
From $\alpha\in B_a$, we obtain
\begin{equation}
\alpha^{-1}\left( a+1\right) <\alpha^{-1}\left( a+2\right) <\cdots
<\alpha^{-1}\left( n\right)
\end{equation}
(by the definition of $B_a$). In other words, if $u$ and $v$ are two
elements of the interval $\left\{ a+1,a+2,\ldots,n\right\} $ satisfying
$u<v$, then $\alpha^{-1}\left( u\right) <\alpha^{-1}\left( v\right) $.
Applying this to $u=a+1$ and $v=\alpha\left( 1\right) $, we obtain
$\alpha^{-1}\left( a+1\right) <\alpha^{-1}\left( \alpha\left( 1\right)
\right) $. In view of $\alpha^{-1}\left( \alpha\left( 1\right) \right)
=1$, this rewrites as $\alpha^{-1}\left( a+1\right) <1$. But this
contradicts the fact that $\alpha^{-1}\left( a+1\right) \in\left[ n\right]
$. This contradiction proves that our assumption was false. Hence, Lemma 9 is
proven. $\blacksquare$