Is this sum of cycles invertible in $\mathbb QS_n$?

$\newcommand{\cyc}{\operatorname{cyc}} \newcommand{\id}{\operatorname{id}} \newcommand{\BB}{\mathbf{B}} \newcommand{\AA}{\mathbf{A}} \newcommand{\kk}{\mathbf{k}} \newcommand{\ww}{\mathbf{w}} $

PART 1 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.]

The answer that follows is an elaboration on parts of the following preprint:

• Adriano Garsia, On the Powers of Top to Random Shuffling.

In particular, the proofs I will give are taken from Section 3 of the preprint (but I include more details). Unlike Garsia, I mean the exposition below to be elementary, relying only on the content of a typical "abstract algebra 1" class plus the definition of a group ring. (I even plan on reusing some of this post in my next semester's combinatorics class.)

1. Notations

Let $\kk$ be any commutative ring. For each integer $n$, we let $\left[ n\right]$ denote the set $\left\{ 1,2,\ldots,n\right\} $ (which is empty if $n\leq0$).

Fix a nonnegative integer $n$. Let $S_n$ be the $n$-th symmetric group; this is the group of all $n!$ permutations of $\left[ n\right] $. We define multiplication on $S_n$ in the continental way (i.e., if $\alpha\in S_n$ and $\beta\in S_n$ are two permutations, then $\alpha\circ\beta$ is the permutation that sends each $i\in\left[ n\right] $ to $\alpha\left( \beta\left( i\right) \right) $). The identity permutation in $S_n$ will be called $\id $. (You are calling it $e$ instead.)

The one-line notation of a permutation $\sigma\in S_n$ is defined to be the $n$-tuple $\left( \sigma\left( 1\right) ,\sigma\left( 2\right) ,\ldots,\sigma\left( n\right) \right) $.

For any $k$ distinct elements $i_1, i_2, \ldots, i_k$, we let $\cyc_{i_1, i_2, \ldots, i_k}\in S_n$ be the permutation that sends $i_1, i_2, \ldots, i_{k-1}, i_k$ to $i_2, i_3, \ldots, i_k, i_1$, while leaving all other elements of $\left[ n\right] $ unchanged. (You are calling this permutation $\left( i_1, i_2, \ldots, i_k \right)$. But that notation would clash with my one-line notation.)

Consider the group ring $\kk S_n$. We define an element $\AA \in\kk S_n$ by \begin{equation} \AA = \sum_{i=1}^{n} \cyc_{1,2,\ldots,i}. \label{eq.defA} \tag{1.1} \end{equation}

For each $k\in\left\{ 0,1,\ldots,n\right\} $, we let $B_k$ be the set of all permutations $\sigma\in S_n$ satisfying $\sigma^{-1}\left( k+1\right) <\sigma^{-1}\left( k+2\right) <\cdots<\sigma^{-1}\left( n\right) $. That is, $B_k$ is the set of all permutations $\sigma$ such that the numbers $k+1,k+2,\ldots,n$ occur in this order in the one-line notation of $\sigma$. For example, if $n=3$, then \begin{align*} B_0 & =\left\{ \left( 1,2,3\right) \right\} ,\\ B_1 & =\left\{ \left( 1,2,3\right) ,\left( 2,1,3\right) ,\left( 2,3,1\right) \right\} ,\\ B_2 & =\left\{ \left( 1,2,3\right) ,\left( 1,3,2\right) ,\left( 2,1,3\right) ,\left( 2,3,1\right) ,\left( 3,1,2\right) ,\left( 3,2,1\right) \right\} =S_3, \end{align*} where we represent each permutation $\sigma\in S_3$ by its one-line notation. Note that if $k\geq n-1$, then the chain of inequalities $\sigma^{-1}\left( k+1\right) <\sigma^{-1}\left( k+2\right) <\cdots <\sigma^{-1}\left( n\right) $ is vacuously true for every $\sigma\in S_n$. Thus, \begin{equation} \text{if }k\geq n-1\text{, then } B_k = S_n. \label{eq.Bk=Sn} \tag{1.2} \end{equation}

For each $k\in\left\{ 0,1,\ldots,n\right\} $, we define an element $\BB_k$ of $\kk S_n$ by \begin{equation} \BB_k = \sum_{\sigma\in B_k}\sigma. \label{eq.defBk} \tag{1.3} \end{equation}

Theorem 1. Let $n\geq1$. Then, $\BB_1 = \AA$.

Theorem 2. For each $a\in\left\{ 0,1,\ldots,n-1\right\} $, we have \begin{equation} \BB_a \AA = a \BB_a + \BB_{a+1}. \end{equation}

Theorem 3. We have \begin{equation} \prod_{i\in\left\{ 0,1,\ldots,n-2,n\right\} }\left( \AA-i\right) = 0 \label{eq.t3.claim} \tag{1.4} \end{equation} in the ring $\kk S_n$. (The factors in this product commute, since they are all polynomials in $\AA$.)

Corollary 4. The element $\id + \AA$ of $\kk S_n$ is invertible if the numbers $1,2,\ldots,n-1,n+1$ are invertible in $\kk$.

Corollary 5. All the $n+1$ elements $\BB_0,\BB_1,\ldots,\BB_n$ are polynomials (with integer coefficients) in $\AA$.

Corollary 6. For each $a\in\left\{ 0,1,\ldots,n-1\right\} $, we have \begin{equation} \AA \BB_a = a \BB_a + \BB_{a+1} . \end{equation}

Corollary 4 is your first claim, because $\id + \AA$ is exactly your $\phi_{n}$ (for $\kk =\mathbb{Q}$). Moreover, Theorem 3 shows that (again for $\kk = \mathbb{Q}$) the operator "left multiplication by $\AA$" on $\kk S_n$ is diagonalizable with eigenvalues being contained in the set $\left\{ 0,1,\ldots,n-2,n \right\}$ (indeed, it can also be shown that the spectrum is precisely this set; see Garsia's preprint for that and for the dimensions of the eigenspaces); therefore, the operator "left multiplication by $\id + \AA$" has positive integer eigenvalues. So this proves your second claim too.

Corollary 6 and Theorem 3 are the equations (3.1) and (3.5) from Garsia's preprint, except that he uses $\BB_1$ instead of $\AA$ (but this is equivalent due to Theorem 1).

The element $\BB_1$ of $\kk S_n$ is best known by its action on representations of $S_n$; namely, it acts as a so-called "top-to-random shuffle" or "random-to-top shuffle" (I don't remember precisely which one it is). It is also known as the "Tsetlin library" to probability theorists. Further references on the elements $\BB_0,\BB_1,\ldots,\BB_n$ of $\kk S_n$ include:

• the appendix of Nolan R. Wallach, Lie Algebra Cohomology and Holomorphic Continuation of Generalized Jacquet Integrals, Advanced Studies in Pure Math. 14 (1988) Representations of Lie Groups, Hiroshima, 1986, pp. 123--151. (At a quick glance, it proves the above Theorem 3 too.)

• Persi Diaconis, James Allen Fill and Jim Pitman, Analysis of Top to Random Shuffles, Combinatorics, Probability and Computing 1 (1992), pp. 135--155.

• Manfred Schocker, Idempotents for derangement numbers, Discrete Mathematics, vol. 269 (2003), pp. 239--248. (His $\Xi_{n,k}$ is our $\BB_k$.)

• F. Hivert, J.-G. Luque, J.-C. Novelli, J.-Y. Thibon, The (1-E)-transform in combinatorial Hopf algebras, arXiv:0912.0184v2, Journal of Algebraic Combinatorics, March 2011, Volume 33, Issue 2, pp. 277--312. (The formula (125) in this paper corresponds to our Theorem 3, but the notations aren't for the faint of heart.)

• A. B. Dieker, Franco Saliola, Spectral analysis of random-to-random Markov chains, arXiv:1509.08580v3, Advances in Mathematics 323 (2018), pp. 427--485. (This analyzes the much more complicated "random-to-random shuffle", which corresponds to the element $\omega\left( \AA \right) \cdot \AA$ of $\kk S_n$, where $\omega$ is the $\kk$-algebra anti-automorphism of $\kk S_n$ that sends each $g \in S_n$ to $g^{-1}$.)

• Darij Grinberg, The signed random-to-top operator on tensor space. (Couldn't help mentioning this -- it studies the kernel of the action of $\AA$ on the $n$-th tensor power of a vector space.)

There is probably plenty of probabilistic literature that I just don't know about.

2. Proof of Theorem 1

We warm ourselves up with proving the easy Theorem 1. Combinatorially, it simply says that the set $B_1$ contains the $n$ permutations $\cyc_{1,2,\ldots,i}$ for $i \in \left[ n \right]$ and no others (and that these $n$ permutations are distinct). If you find this obvious, move on to the next section; I'll do nothing to convince you otherwise.

Proof of Theorem 1. Let $i\in\left[ n\right] $. Then, the permutation $\cyc_{1,2,\ldots,i}$ has one-line notation $\left( 2,3,\ldots,i,1,i+1,i+2,\ldots,n\right) $. Thus, the numbers $2,3,\ldots,n$ occur in this order in the one-line notation of $\cyc_{1,2,\ldots,i}$; in other words, we have \begin{equation} \left( \cyc_{1,2,\ldots,i}\right) ^{-1}\left( 2\right) <\left( \cyc_{1,2,\ldots,i}\right) ^{-1}\left( 3\right) <\cdots <\left( \cyc_{1,2,\ldots,i}\right) ^{-1}\left( n\right) . \end{equation} In other words, $\cyc_{1,2,\ldots,i}\in B_1$ (because we have defined $B_1$ to be the set of all permutations $\sigma\in S_n$ satisfying $\sigma^{-1}\left( 2\right) <\sigma^{-1}\left( 3\right) <\cdots<\sigma^{-1}\left( n\right) $).

Now, forget that we fixed $i\in\left[ n\right] $. We thus have shown that $\cyc_{1,2,\ldots,i}\in B_1$ for each $i\in\left[ n\right] $. Hence, we can define a map \begin{align*} \mathbf{f}:\left[ n\right] & \to B_1,\\ i & \mapsto\cyc_{1,2,\ldots,i}. \end{align*} Consider this map $\mathbf{f}$. On the other hand, define a map \begin{align*} \mathbf{g}:B_1 & \to\left[ n\right] ,\\ \sigma & \mapsto\sigma^{-1}\left( 1\right) . \end{align*}

If $i\in\left[ n\right] $, then \begin{align*} \left( \mathbf{g}\circ\mathbf{f}\right) \left( i\right) & =\mathbf{g} \left( \underbrace{\mathbf{f}\left( i\right) }_{=\cyc_{1,2,\ldots,i}} \right) =\mathbf{g}\left( \cyc_{1,2,\ldots,i}\right) \\ & =\left( \cyc_{1,2,\ldots,i}\right) ^{-1}\left( 1\right) \qquad\left( \text{by the definition of }\mathbf{g}\right) \\ & =i=\id \left( i\right) . \end{align*} Thus, $\mathbf{g}\circ\mathbf{f}=\id $.

On the other hand, let $\sigma\in B_1$ be arbitrary. We shall show that $\left( \mathbf{f}\circ\mathbf{g}\right) \left( \sigma\right) =\id \left( \sigma\right) $.

In fact, $\sigma\in B_1$ and therefore $\sigma^{-1}\left( 2\right) <\sigma^{-1}\left( 3\right) <\cdots<\sigma^{-1}\left( n\right) $ (by the definition of $B_1$). Let $i=\mathbf{g}\left( \sigma\right) $. Thus, $i=\mathbf{g}\left( \sigma\right) =\sigma^{-1}\left( 1\right) $ (by the definition of $\mathbf{g}$). But $\sigma^{-1}$ is a permutation of $\left[ n\right] $; thus, the numbers $\sigma^{-1}\left( 2\right) ,\sigma ^{-1}\left( 3\right) ,\ldots,\sigma^{-1}\left( n\right) $ are precisely the elements of $\left[ n\right] $ distinct from $\sigma^{-1}\left( 1\right) $. In view of $\sigma^{-1}\left( 1\right) =i$, this rewrites as follows: The numbers $\sigma^{-1}\left( 2\right) ,\sigma^{-1}\left( 3\right) ,\ldots,\sigma^{-1}\left( n\right) $ are precisely the elements of $\left[ n\right] $ distinct from $i$. In other words, these numbers $\sigma^{-1}\left( 2\right) ,\sigma^{-1}\left( 3\right) ,\ldots ,\sigma^{-1}\left( n\right) $ are precisely the numbers $1,2,\ldots ,i-1,i+1,i+2,\ldots,n$ in some order. Moreover, we know what this order is: it is the increasing order (since $\sigma^{-1}\left( 2\right) <\sigma ^{-1}\left( 3\right) <\cdots<\sigma^{-1}\left( n\right) $). Thus, the numbers $\sigma^{-1}\left( 2\right) ,\sigma^{-1}\left( 3\right) ,\ldots,\sigma^{-1}\left( n\right) $ are precisely the numbers $1,2,\ldots,i-1,i+1,i+2,\ldots,n$ in this order. Combining this with $\sigma^{-1}\left( 1\right) =i$, we conclude that \begin{equation} \left( \sigma^{-1}\left( 1\right) ,\sigma^{-1}\left( 2\right) ,\ldots,\sigma^{-1}\left( n\right) \right) =\left( i,1,2,\ldots ,i-1,i+1,i+2,\ldots,n\right) . \end{equation} Hence, $\sigma^{-1}=\cyc_{i,i-1,\ldots,1}$. Therefore, $\sigma=\left( \cyc_{i,i-1,\ldots,1}\right) ^{-1}=\cyc_{1,2,\ldots,i}$. Comparing this with \begin{equation} \left( \mathbf{f}\circ\mathbf{g}\right) \left( \sigma\right) =\mathbf{f}\left( \underbrace{\mathbf{g}\left( \sigma\right) }_{=i}\right) =\mathbf{f}\left( i\right) =\cyc_{1,2,\ldots ,i}\qquad\left( \text{by the definition of }\mathbf{f}\right) , \end{equation} we obtain $\left( \mathbf{f}\circ\mathbf{g}\right) \left( \sigma\right) =\sigma=\id \left( \sigma\right) $.

Now, forget that we fixed $\sigma$. We thus have shown that $\left( \mathbf{f}\circ\mathbf{g}\right) \left( \sigma\right) =\id \left( \sigma\right) $ for each $\sigma\in B_1$. In other words, $\mathbf{f}\circ\mathbf{g}=\id $. Combining this with $\mathbf{g}\circ\mathbf{f}=\id $, we conclude that the maps $\mathbf{f}$ and $\mathbf{g}$ are mutually inverse. Hence, the map $\mathbf{f}:\left[ n\right] \to B_1$ is a bijection. Now, \begin{equation} \AA=\underbrace{\sum_{i=1}^{n}}_{=\sum_{i\in\left[ n\right] } }\underbrace{\cyc_{1,2,\ldots,i}} _{\substack{=\mathbf{f}\left( i\right) \\\text{(by the definition of }\mathbf{f}\text{)}}}=\sum_{i\in\left[ n\right] }\mathbf{f}\left( i\right) =\sum_{\sigma\in B_1}\sigma \end{equation} (here, we have substituted $\sigma$ for $\mathbf{f}\left( i\right) $ in the sum, since the map $\mathbf{f}:\left[ n\right] \to B_1$ is a bijection). Comparing this with \begin{equation} \BB_1 = \sum_{\sigma\in B_1}\sigma\qquad\left( \text{by the definition of }\BB_1 \right) , \end{equation} we obtain $\BB_1 = \AA$. This proves Theorem 1. $\blacksquare$

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

$\newcommand{\cyc}{\operatorname{cyc}} \newcommand{\id}{\operatorname{id}} \newcommand{\BB}{\mathbf{B}} \newcommand{\AA}{\mathbf{A}} \newcommand{\kk}{\mathbf{k}} \newcommand{\ww}{\mathbf{w}} $

PART 3 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.]

Now, we can finally prove Theorem 2:

Proof of Theorem 2. The definition of $\BB_a$ yields \begin{equation} \BB_{a}=\sum_{\sigma\in B_a}\sigma=\sum_{\alpha\in B_a}\alpha. \end{equation}

But Lemma 9 shows that each $\alpha\in B_a$ satisfies $\alpha\left( 1\right) \in\left[ a+1\right] $. Hence, we can replace the summation sign "$\sum_{\alpha\in B_a}$" by "$\sum_{i\in\left[ a+1\right] }\sum _{\substack{\alpha\in B_{a};\\\alpha\left( 1\right) =i}}$" on the right hand side of this equality. We thus obtain \begin{equation} \BB_{a}=\sum_{i\in\left[ a+1\right] }\sum_{\substack{\alpha\in B_{a};\\\alpha\left( 1\right) =i}}\alpha. \label{pf.t2.2} \tag{3.13} \end{equation}

For each $i\in\left[ a+1\right] $, we have $B_{a,1\to i}=\left\{ \sigma\in B_{a}\ \mid\ \sigma\left( 1\right) =i\right\} $ (by the definition of $B_{a,1\to i}$). Hence, we can replace the summation sign "$\sum_{\substack{\alpha\in B_{a};\\\alpha\left( 1\right) =i}}$" by "$\sum_{\alpha\in B_{a,1\to i}}$" on the right hand side of \eqref{pf.t2.2}. We thus obtain \begin{equation} \BB_{a}=\sum_{i\in\left[ a+1\right] }\sum_{\alpha\in B_{a,1\to i}}\alpha. \end{equation} Multiplying this equality with the equality \begin{equation} \AA=\underbrace{\sum_{i=1}^{n}}_{=\sum_{i\in\left[ n\right] } }\underbrace{\cyc_{1,2,\ldots,i}}_{\substack{=z_i \\\text{(by \eqref{eq.defzi})}}}=\sum_{i\in\left[ n\right] }z_i=\sum _{j\in\left[ n\right] }z_j, \end{equation} we obtain \begin{align} \BB_{a}\AA & =\left( \sum_{i\in\left[ a+1\right] } \sum_{\alpha\in B_{a,1\to i}}\alpha\right) \left( \sum_{j\in\left[ n\right] }z_j\right) =\sum_{i\in\left[ a+1\right] }\sum_{\alpha\in B_{a,1\to i}}\sum_{j\in\left[ n\right] }\alpha\circ z_j\\ & =\sum_{i\in\left[ a+1\right] }\sum_{j\in\left[ n\right] }\sum _{\alpha\in B_{a,1\to i}}\alpha\circ z_j\\ & =\sum_{i\in\left[ a\right] }\sum_{j\in\left[ n\right] }\sum_{\alpha\in B_{a,1\to i}}\alpha\circ z_j+\sum_{j\in\left[ n\right] } \sum_{\alpha\in B_{a,1\to a+1}}\alpha\circ z_j \label{pf.t2.3} \tag{3.14} \end{align} (here, we have split off the addend for $i=a+1$ from the outermost sum).

Now, Lemma 7 says that for each $i\in\left[ a\right] $ and $j\in\left[ n\right] $, 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. Hence, for each $i\in\left[ a\right] $ and $j\in\left[ n\right] $, we can substitute $\beta$ for $\alpha\circ z_j$ in the sum $\sum_{\alpha\in B_{a,1\to i}}\alpha\circ z_j$. Thus, for each $i\in\left[ a\right] $ and $j\in\left[ n\right] $, we obtain \begin{align} \sum_{\alpha\in B_{a,1\to i}}\alpha\circ z_j & =\sum_{\beta\in B_{a,j\to i}}\beta=\sum_{\substack{\beta\in B_{a};\\\beta\left( j\right) =i}}\beta\\ & \qquad\left( \begin{array} [c]{c} \text{since }B_{a,j\to i}=\left\{ \sigma\in B_{a}\ \mid \ \sigma\left( j\right) =i\right\} \\ \text{(by the definition of }B_{a,j\to i}\text{)} \end{array} \right) \\ & =\sum_{\substack{\beta\in B_{a};\\\beta^{-1}\left( i\right) =j} }\beta \label{pf.t2.4a} \tag{3.15} \end{align} (because for any $\beta\in B_a$, the statement $\left( \beta\left( j\right) =i\right) $ is equivalent to $\left( \beta^{-1}\left( i\right) =j\right) $).

Also, Lemma 8 says that for each $j\in\left[ n\right] $, 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. Hence, for each $j\in\left[ n\right] $, we can substitute $\beta$ for $\alpha\circ z_j$ in the sum $\sum_{\alpha\in B_{a,1\to a+1}}\alpha\circ z_j$. Thus, for each $j\in\left[ n\right] $, we obtain \begin{align} \sum_{\alpha\in B_{a,1\to a+1}}\alpha\circ z_j & =\sum_{\beta\in B_{a+1,j\to a+1}}\beta=\sum_{\substack{\beta\in B_{a+1};\\\beta\left( j\right) =a+1}}\beta\\ & \qquad\left( \begin{array} [c]{c} \text{since }B_{a+1,j\to a+1}=\left\{ \sigma\in B_{a+1}\ \mid \ \sigma\left( j\right) =a+1\right\} \\ \text{(by the definition of }B_{a+1,j\to a+1}\text{)} \end{array} \right) \\ & =\sum_{\substack{\beta\in B_{a+1};\\\beta^{-1}\left( a+1\right) =j} }\beta \label{pf.t2.4b} \tag{3.16} \end{align} (because for any $\beta\in B_{a+1}$, the statement $\left( \beta\left( j\right) =a+1\right) $ is equivalent to $\left( \beta^{-1}\left( a+1\right) =j\right) $).

Now, \eqref{pf.t2.3} becomes \begin{align} \BB_{a}\AA & =\sum_{i\in\left[ a\right] }\sum_{j\in\left[ n\right] }\underbrace{\sum_{\alpha\in B_{a,1\to i}}\alpha\circ z_j }_{\substack{=\sum_{\substack{\beta\in B_{a};\\\beta^{-1}\left( i\right) =j}}\beta\\\text{(by \eqref{pf.t2.4a})}}}+\sum_{j\in\left[ n\right] }\underbrace{\sum_{\alpha\in B_{a,1\to a+1}}\alpha\circ z_j }_{\substack{=\sum_{\substack{\beta\in B_{a+1};\\\beta^{-1}\left( a+1\right) =j}}\beta\\\text{(by \eqref{pf.t2.4b})}}}\\ & =\sum_{i\in\left[ a\right] }\sum_{j\in\left[ n\right] }\sum _{\substack{\beta\in B_{a};\\\beta^{-1}\left( i\right) =j}}\beta+\sum _{j\in\left[ n\right] }\sum_{\substack{\beta\in B_{a+1};\\\beta^{-1}\left( a+1\right) =j}}\beta. \label{pf.t2.5} \tag{3.17} \end{align}

For each $i\in\left[ a\right] $, we have \begin{equation} \BB_{a}=\sum_{\alpha\in B_a}\alpha=\sum_{\beta\in B_a}\beta =\sum_{j\in\left[ n\right] }\sum_{\substack{\beta\in B_{a};\\\beta ^{-1}\left( i\right) =j}}\beta \label{pf.t2.6a} \tag{3.18} \end{equation} (because for each $\beta\in B_a$, we have $\beta^{-1}\left( i\right) \in\left[ n\right] $). Also, the definition of $\BB_{a+1}$ yields \begin{equation} \BB_{a+1}=\sum_{\sigma\in B_{a+1}}\sigma=\sum_{\beta\in B_{a+1}} \beta=\sum_{j\in\left[ n\right] }\sum_{\substack{\beta\in B_{a+1} ;\\\beta^{-1}\left( a+1\right) =j}}\beta \label{pf.t2.6b} \tag{3.19} \end{equation} (because for each $\beta\in B_{a+1}$, we have $\beta^{-1}\left( a+1\right) \in\left[ n\right] $). Hence, \eqref{pf.t2.5} becomes \begin{align*} \BB_{a}\AA & =\sum_{i\in\left[ a\right] }\underbrace{\sum _{j\in\left[ n\right] }\sum_{\substack{\beta\in B_{a};\\\beta^{-1}\left( i\right) =j}}\beta}_{\substack{=\BB_{a}\\\text{(by \eqref{pf.t2.6a})} }}+\underbrace{\sum_{j\in\left[ n\right] }\sum_{\substack{\beta\in B_{a+1};\\\beta^{-1}\left( a+1\right) =j}}\beta}_{\substack{=\BB _{a+1}\\\text{(by \eqref{pf.t2.6b})}}}=\underbrace{\sum_{i\in\left[ a\right] }\BB_a}_{=\left\vert \left[ a\right] \right\vert \cdot \BB_a}+\BB_{a+1}\\ & =\underbrace{\left\vert \left[ a\right] \right\vert }_{=a}\cdot \BB_{a}+\BB_{a+1}=a\BB_{a}+\BB_{a+1}. \end{align*} This proves Theorem 2. $\blacksquare$

4. Proof of Theorem 3 and Corollaries 5 and 6

To prove Theorem 3 (again, following Garsia), let us first show the following:

Proposition 10. We have $B_{0}=\left\{ \id \right\} $.

Proof of Proposition 10. The set $B_{0}$ is the set of all permutations $\sigma\in S_n$ satisfying $\sigma^{-1}\left( 1\right) <\sigma^{-1}\left( 2\right) <\cdots<\sigma^{-1}\left( n\right) $ (by the definition of $B_{0} $). But $\id $ is clearly such a permutation (since $\id \nolimits^{-1}\left( 1\right) <\id \nolimits^{-1}\left( 2\right) <\cdots<\id \nolimits^{-1} \left( n\right) $). Hence, $\id \in B_{0}$. In other words, $\left\{ \id \right\} \subseteq B_{0}$.

Let $\sigma\in B_{0}$. Thus, $\sigma$ is a permutation in $S_n$ satisfying $\sigma^{-1}\left( 1\right) <\sigma^{-1}\left( 2\right) <\cdots <\sigma^{-1}\left( n\right) $ (by the definition of $B_{0}$).

The map $\sigma^{-1}:\left[ n\right] \to\left[ n\right] $ is strictly increasing (since $\sigma^{-1}\left( 1\right) <\sigma^{-1}\left( 2\right) <\cdots<\sigma^{-1}\left( n\right) $). But the only strictly increasing map from $\left[ n\right] $ to $\left[ n\right] $ is the identity map $\id $. Hence, $\sigma^{-1}$ must be the identity map $\id $. In other words, $\sigma^{-1}=\id $. Hence, $\sigma=\id \nolimits^{-1}=\id \in\left\{ \id \right\} $.

Now, forget that we fixed $\sigma$. We thus have proven that $\sigma \in\left\{ \id \right\} $ for each $\sigma\in B_{0}$. In other words, $B_{0}\subseteq\left\{ \id \right\} $. Combining this with $\left\{ \id \right\} \subseteq B_{0}$, we obtain $B_{0}=\left\{ \id \right\} $. This proves Proposition 10.

Proposition 11. For each $k\in\left\{ 0,1,\ldots,n\right\} $, we have \begin{equation} \BB_{k}=\prod_{i=0}^{k-1}\left( \AA-i\right) . \end{equation} (Here, the factors in this product commute, since they are all polynomials in $\AA$.)

Proof of Proposition 11. We proceed by induction on $k$:

Induction base: The definition of $\BB_{0}$ yields $\BB _{0}=\sum_{\sigma\in B_{0}}\sigma=\sum_{\sigma\in\left\{ \id \right\} }\sigma$ (since Proposition 10 yields $B_{0}=\left\{ \id \right\} $). Hence, $\BB_{0}=\sum_{\sigma\in\left\{ \id \right\} }\sigma=\id =1$ in $\kk S_n$. Comparing this with $\prod_{i=0}^{0-1}\left( \AA-i\right) =\left( \text{empty product}\right) =1$, we obtain $\BB_{0}=\prod_{i=0} ^{0-1}\left( \AA-i\right) $. In other words, Proposition 11 holds for $k=0$. This completes the induction base.

Induction step: Let $a\in\left\{ 0,1,\ldots,n-1\right\} $. Assume that Proposition 11 holds for $k=a$. We must prove that Proposition 11 holds for $k=a+1$.

We have assumed that Proposition 11 holds for $k=a$. In other words, $\BB_{a}=\prod_{i=0}^{a-1}\left( \AA-i\right) $.

But Theorem 2 yields $\BB_{a}\AA=a\BB_{a}+\BB_{a+1}$. Thus, \begin{align*} \BB_{a+1} & =\BB_{a}\AA-a\BB_{a} =\underbrace{\BB_a}_{=\prod_{i=0}^{a-1}\left( \AA-i\right) }\left( \AA-a\right) =\left( \prod_{i=0}^{a-1}\left( \AA -i\right) \right) \left( \AA-a\right) \\ & =\prod_{i=0}^{a}\left( \AA-i\right) =\prod_{i=0}^{\left( a+1\right) -1}\left( \AA-i\right) . \end{align*} In other words, Proposition 11 holds for $k=a+1$. This completes the induction step. Thus, Proposition 11 is proven by induction. $\blacksquare$

Before we continue with the proof of Theorem 3, let us take a quick detour to deal with Corollaries 5 and 6 first:

Proof of Corollary 5. We must prove that $\BB_k$ is a polynomial (with integer coefficients) in $\AA$ for each $k \in \left\{ 0, 1, \ldots, n \right\}$.

So let us fix $k \in \left\{ 0, 1, \ldots, n \right\}$. Then, Proposition 11 yields $\BB_k = \prod_{i=0}^{k-1}\left( \AA-i\right) $. Hence, $\BB_k$ is a polynomial (with integer coefficients) in $\AA$. This proves Corollary 5. $\blacksquare$

Proof of Corollary 6. Let $a\in \left\{ 0, 1, \ldots, n \right\}$. Then, $\BB_a$ is a polynomial (with integer coefficients) in $\AA$ (by Corollary 5). Hence, $\BB_a$ commutes with $\AA$. Thus, $\AA \BB_a = \BB_a \AA = a\BB_a + \BB_{a+1}$ (by Theorem 2). This proves Corollary 6. $\blacksquare$

I'm just realizing that Theorem 1 also follows from Proposition 11, so our above "warm-up" was unnecessary:

Second proof of Theorem 1. Proposition 11 (applied to $k=1$) yields $\BB_1 = \prod_{i=0}^{1-1}\left( \AA-i\right) =\AA -0=\AA$. This proves Theorem 1. $\blacksquare$

Now, we recall a general property of finite groups:

Proposition 12. Let $G$ be a finite group. Let $\ww$ be the element $\sum_{\sigma\in G}\sigma$ of the group ring $\kk G$. Let $g\in G$. Then, $g\ww=\ww$.

Proof of Proposition 12. The map $G\to G,\ \sigma\mapsto g\sigma$ is a bijection (since $g$ is an element of the group $G$). Hence, we can substitute $g\sigma$ for $\sigma$ in the sum $\sum_{\sigma\in G}\sigma$. Thus we obtain \begin{equation} \sum_{\sigma\in G}\sigma=\sum_{\sigma\in G}g\sigma=g\sum_{\sigma\in G}\sigma. \end{equation} In view of $\ww=\sum_{\sigma\in G}\sigma$, this equality rewrites as $\ww=g\ww$. This proves Proposition 12. $\blacksquare$

Proof of Theorem 3. Theorem 3 is easily checked by hand in the case $n=0$. Thus, we WLOG assume that we are not in this case. Hence, $n\geq1$. Thus, $n-1\in\left\{ 0,1,\ldots,n\right\} $. Therefore, Proposition 11 (applied to $k=n-1$) yields \begin{equation} \BB_{n-1}=\prod_{i=0}^{\left( n-1\right) -1}\left( \AA -i\right) =\prod_{i=0}^{n-2}\left( \AA-i\right) . \label{pf.t3.1} \tag{4.1} \end{equation}

Let $\ww$ be the element $\sum_{\sigma\in S_n}\sigma$ of the group ring $\kk S_n$.

But \eqref{eq.Bk=Sn} (applied to $k=n-1$) yields $B_{n-1}=S_n$. Now, the definition of $\BB_{n-1}$ yields \begin{align*} \BB_{n-1} & =\sum_{\sigma\in B_{n-1}}\sigma=\sum_{\sigma\in S_n} \sigma\qquad\left( \text{since }B_{n-1}= S_n \right) \\ & =\ww. \end{align*} Hence, \begin{align*} \AA \BB_{n-1} & =\underbrace{\AA}_{=\sum_{i=1}^{n} \cyc_{1,2,\ldots,i}}\ww=\left( \sum_{i=1} ^{n}\cyc_{1,2,\ldots,i}\right) \ww\\ & =\sum_{i=1}^{n}\underbrace{\cyc_{1,2,\ldots ,i}\ww}_{\substack{=\ww\\\text{(by Proposition 12, applied to }G= S_n \\\text{and }g=\cyc_{1,2,\ldots,i}\text{)} }}=\sum_{i=1}^{n}\ww=n\underbrace{\ww}_{=\BB_{n-1} }=n\BB_{n-1}. \end{align*} Hence, \begin{align*} 0 & = \AA \BB_{n-1}-n\BB_{n-1}=\left( \AA-n\right) \BB_{n-1}\\ & =\left( \AA-n\right) \prod_{i=0}^{n-2}\left( \AA-i\right) \qquad\left( \text{by \eqref{pf.t3.1}}\right) \\ & =\prod_{i\in\left\{ 0,1,\ldots,n-2,n\right\} }\left( \AA-i\right) . \end{align*} This proves Theorem 3. $\blacksquare$

5. Proof of Corollary 4

Proof of Corollary 4. Assume that the numbers $1,2,\ldots,n-1,n+1$ are invertible in $\kk $.

Let $\xi$ be the element $\id +\AA=1+\AA$ of $\kk S_n$. We must show that $\xi$ is invertible.

Let $P$ be the polynomial \begin{equation} \prod_{i\in\left\{ 0,1,\ldots,n-2,n\right\} }\left( X-\left( i+1\right) \right) \end{equation} in the polynomial ring $\kk \left[ X\right] $. Let $c$ be the constant term $\prod_{i\in\left\{ 0,1,\ldots,n-2,n\right\} }\left( -\left( i+1\right) \right) $ of this polynomial $P$. Then, we can write $P$ in the form $P=XQ+c$ for some $Q\in\kk \left[ X\right] $ (since $c$ is the constant term of $P$). Consider this $Q$.

We have \begin{align*} c & =\prod_{i\in\left\{ 0,1,\ldots,n-2,n\right\} }\left( -\left( i+1\right) \right) =\pm\prod_{i\in\left\{ 0,1,\ldots,n-2,n\right\} }\left( i+1\right) \\ & =\pm1\cdot2\cdot\cdots\cdot\left( n-1\right) \cdot\left( n+1\right) ; \end{align*} this is an invertible element of $\kk $ (since the numbers $1,2,\ldots,n-1,n+1$ are invertible in $\kk $). Thus, $c^{-1} \in\kk $ is well-defined.

But the definition of $P$ yields \begin{align*} P\left( \xi\right) & =\prod_{i\in\left\{ 0,1,\ldots,n-2,n\right\} }\left( \underbrace{\xi}_{=1+\AA}-\left( i+1\right) \right) =\prod_{i\in\left\{ 0,1,\ldots,n-2,n\right\} }\underbrace{\left( \left( 1+\AA\right) -\left( i+1\right) \right) }_{=\AA-i}\\ & =\prod_{i\in\left\{ 0,1,\ldots,n-2,n\right\} }\left( \AA-i\right) =0 \end{align*} (by Theorem 2). But $P=XQ+c$ yields $P\left( \xi\right) =\xi Q\left( \xi\right) +c$. Hence, $\xi Q\left( \xi\right) +c=P\left( \xi\right) =0$, so that $\xi Q\left( \xi\right) =-c$. Multiplying this equality by $-c^{-1} $, we find $-c^{-1}\xi Q\left( \xi\right) =1$. Hence, $\xi\cdot\left( -c^{-1}Q\left( \xi\right) \right) =-c^{-1}\xi Q\left( \xi\right) =1$. Thus, $-c^{-1}Q\left( \xi\right) $ is a right inverse of $\xi$ in the ring $\kk S_n$. Similarly, $-c^{-1}Q\left( \xi\right) $ is a left inverse of $\xi$ in the ring $\kk S_n$ as well (since the equality $P=XQ+c$ can also be rewritten as $P=QX+c$). Therefore, $-c^{-1}Q\left( \xi\right) $ is a two-sided inverse of $\xi$ in the ring $\kk S_n$. Thus, $\xi$ is invertible. This proves Corollary 4. $\blacksquare$

6. A few remarks

I have only scratched the surface of the theory of the Tsetlin library. For further results and ramifications, I suggest first reading Garsia's preprint and then exploring the references in Section 1 above. I shall just make two remarks.

First, let $\mathbb{N}=\left\{ 0,1,2,\ldots\right\} $.

Theorem 1 and Corollary 6 are particular cases of the following fact (Theorem 1.2 in Garsia's preprint):

Theorem 13. Set $\BB_{r}=0$ for all $r>n$. Then, for each $a,b\in\mathbb{N}$, we have \begin{equation} \BB_{a}\BB_{b}=\sum_{r=\max\left\{ a,b\right\} }^{a+b} \dfrac{a!b!}{\left( r-a\right) !\left( r-b\right) !\left( a+b-r\right) !}\BB_{r}. \end{equation} (The fraction $\dfrac{a!b!}{\left( r-a\right) !\left( r-b\right) !\left( a+b-r\right) !}$ on the right hand side of this is an integer, because it equals $\dbinom{a}{r-b}\dbinom{b}{r-a}\left( a+b-r\right) !$.)

Theorem 13 is actually easily derived from Propositions 11 and 12 using the following fact:

Proposition 14. For each $k\in\mathbb{N}$, let $X^{\underline{k}}$ denote the polynomial $X\left( X-1\right) \cdots\left( X-k+1\right) $ in the polynomial ring $\kk \left[ X\right] $. Then, for each $a,b\in \mathbb{N}$, we have \begin{equation} X^{\underline{a}}X^{\underline{b}}=\sum_{r=\max\left\{ a,b\right\} } ^{a+b}\dfrac{a!b!}{\left( r-a\right) !\left( r-b\right) !\left( a+b-r\right) !}X^{\underline{r}}. \label{eq.p13.claim} \tag{6.1} \end{equation}

Note that Garsia uses the notation $\left( X\right) \downarrow_{k}$ instead of $X^{\underline{k}}$.

Proposition 14 is a standard exercise on induction. Its inductive proof is found in the solution of Exercise 7 in:

• Darij Grinberg, UMN Math 5705: Enumerative Combinatorics, Fall 2018: Homework 1

(where I also show (in Claim 3 (a)) that the coefficients $\dfrac{a!b!}{\left( r-a\right) !\left( r-b\right) !\left( a+b-r\right) !}$ are integers). Note that I state it for a real number $x$ instead of the indeterminate $X$, but the computation does not depend on what $X$ is.

Proposition 14 can also be derived from a standard combinatorial identity:

Lemma 15. If $a,b\in\mathbb{N}$ and $x\in\mathbb{N}$, then \begin{equation} \dbinom{x}{a}\dbinom{x}{b}=\sum_{r=\max\left\{ a,b\right\} }^{a+b}\dbinom {r}{a}\dbinom{a}{r-b}\dbinom{x}{r}. \end{equation}

Proof of Lemma 15 (sketched). Fix an $x$-element set $X$. Let us count all pairs $\left( A,B\right) $ consisting of an $a$-element subset $A$ of $X$ and a $b$-element subset $B$ of $X$.

There are two ways to count these pairs:

• The first way is, we choose $A$ first and then choose $B$. This clearly gives us $\dbinom{x}{a}\dbinom{x}{b}$ many options.

• The second way is, we first choose the size $r$ of the union $U:=A\cup B$; then, we choose this $U$ itself (there are $\dbinom{x}{r}$ many choices here); then we choose $A$ as a subset of $U$ (there are $\dbinom{r}{a}$ many choices here), and finally we choose $B$ as a $b$-element subset of $U$ that must contain $U\setminus A$ as a subset (because otherwise, $A\cup B$ would not be $U$) (there are $\dbinom{a}{r-b}$ many choices here, since choosing such a $B$ is tantamount to choosing its complement $U\setminus B$, which is merely required to be an $\left( r-b\right) $-element subset of $A$). This gives us $\sum_{r=\max\left\{ a,b\right\} }^{a+b}\dbinom{r}{a}\dbinom{a}{r-b} \dbinom{x}{r}$ many options.

Comparing the two results, we obtain Lemma 15. $\blacksquare$

Proof of Proposition 14 (sketched). Fix $a,b\in\mathbb{N}$. Both sides of \eqref{eq.p13.claim} are polynomials with integer coefficients. Hence, we WLOG assume that $\kk =\mathbb{Z}$.

Now, let $x\in\mathbb{N}$. For each $k\in\mathbb{N}$, set $x^{\underline{k} }=x\left( x-1\right) \cdots\left( x-k+1\right) $; this is of course the result of substituting $x$ for $X$ in the polynomial $X^{\underline{k}}$. Note that \begin{equation} k!\cdot\dbinom{x}{k}=x^{\underline{k}}\qquad\text{for each }k\in \mathbb{N}. \label{p13.pf.xk} \tag{6.2} \end{equation}

Lemma 15 yields \begin{equation} \dbinom{x}{a}\dbinom{x}{b}=\sum_{r=\max\left\{ a,b\right\} }^{a+b}\dbinom {r}{a}\dbinom{a}{r-b}\dbinom{x}{r}. \end{equation} Multiplying both sides of this equality by $a!b!$, we obtain \begin{align*} a!b!\dbinom{x}{a}\dbinom{x}{b} & =a!b!\sum_{r=\max\left\{ a,b\right\} }^{a+b}\dbinom{r}{a}\dbinom{a}{r-b}\dbinom{x}{r}\\ & =\sum_{r=\max\left\{ a,b\right\} }^{a+b}\underbrace{a!b!\dbinom{r} {a}\dbinom{a}{r-b}}_{=\dfrac{1}{\left( r-a\right) !\left( r-b\right) !\left( a+b-r\right) !}\cdot r!}\dbinom{x}{r}\\ & =\sum_{r=\max\left\{ a,b\right\} }^{a+b}\dfrac{1}{\left( r-a\right) !\left( r-b\right) !\left( a+b-r\right) !}\cdot\underbrace{r!\dbinom{x} {r}}_{\substack{=x^{\underline{r}}\\\text{(by \eqref{p13.pf.xk})}}}\\ & =\sum_{r=\max\left\{ a,b\right\} }^{a+b}\dfrac{1}{\left( r-a\right) !\left( r-b\right) !\left( a+b-r\right) !}x^{\underline{r}}. \end{align*} Comparing this with \begin{equation} a!b!\dbinom{x}{a}\dbinom{x}{b}=\underbrace{a!\dbinom{x}{a}} _{\substack{=x^{\underline{a}}\\\text{(by \eqref{p13.pf.xk})}} }\underbrace{b!\dbinom{x}{b}}_{\substack{=x^{\underline{b}}\\\text{(by \eqref{p13.pf.xk})}}}=x^{\underline{a}}x^{\underline{b}}, \end{equation} we obtain \begin{equation} x^{\underline{a}}x^{\underline{b}}=\sum_{r=\max\left\{ a,b\right\} } ^{a+b}\dfrac{a!b!}{\left( r-a\right) !\left( r-b\right) !\left( a+b-r\right) !}x^{\underline{r}}. \label{pf.p13.1} \tag{6.3} \end{equation}

Forget that we fixed $x$. Thus, we have proven \eqref{pf.p13.1} for each $x\in\mathbb{N}$. But it is known that if two polynomials $P,Q\in \mathbb{Z}\left[ X\right] $ satisfy $P\left( x\right) =Q\left( x\right) $ for each $x\in\mathbb{N}$, then they satisfy $P=Q$. Applying this to $P=X^{\underline{a}}X^{\underline{b}}$ and $Q=\sum_{r=\max\left\{ a,b\right\} }^{a+b}\dfrac{a!b!}{\left( r-a\right) !\left( r-b\right) !\left( a+b-r\right) !}X^{\underline{r}}$, we conclude that \begin{equation} X^{\underline{a}}X^{\underline{b}}=\sum_{r=\max\left\{ a,b\right\} } ^{a+b}\dfrac{a!b!}{\left( r-a\right) !\left( r-b\right) !\left( a+b-r\right) !}X^{\underline{r}} \end{equation} (because \eqref{pf.p13.1} shows that these $P$ and $Q$ satisfy $P\left( x\right) =Q\left( x\right) $ for each $x\in\mathbb{N}$). This proves Proposition 14. $\blacksquare$

Now for the second remark. The first proof Garsia gives for his Theorem 1.2 (our Theorem 13) uses the so-called Solomon's Mackey formula (his Theorem 1.1). While he cites Solomon's original paper for its proof, we have by now some better sources (better because Solomon's paper works in the general setting of Coxeter groups, which requires some work before it can be translated back into the language of permutations):

• Corollary 2.4 in Franco V. Saliola, Hyperplane arrangements and descent algebras (errata).

• Theorem 1 in Mark Wildon, On Bidigare's proof of Solomon's theorem (errata).