# Prove the bijections between the following $(p,q,r)$-shuffles

I am reading the book "From Calculus to Cohomology: De Rham cohomology and characteristic classes"

Let $p, q, r$ be nonnegative integers.

It says, (for those who own the book, on pg 10) without justification that there are bijections $$S\left(p,q+r\right)\times S\left(\bar{p},q,r\right) \overset{\cong}{\longrightarrow} S\left(p,q,r\right),\ \left(\sigma,\tau\right)\mapsto \sigma \circ \tau$$ and $$S\left(p+q,r\right)\times S\left(p,q,\bar{r}\right) \overset{\cong}{\longrightarrow} S\left(p,q,r\right),\ \left(\sigma,\tau\right)\mapsto \sigma \circ \tau .$$

Here, the following notations are being used:

• For any $n$, we let $S\left(n\right)$ denote the group of all permutations of $\left\{1,2,\ldots,n\right\}$.

• For any $n$ and $m$, we let $S\left(n,m\right)$ denote the set of all permutations $\sigma\in S\left(n+m\right)$ with $$\sigma\left(1\right) < \sigma\left(2\right) < \cdots < \sigma\left(n\right) \qquad \text{and}$$ $$\sigma\left(n+1\right) < \sigma\left(n+2\right) < \cdots < \sigma\left(n+m\right) .$$

• We let $S\left(p,q,r\right)$ be the set of all permutations $\sigma \in S\left(p+q+r\right)$ with

$$\sigma\left(1\right)<\sigma\left(2\right)<\cdots<\sigma\left(p\right) ,$$

$$\sigma\left(p+1\right)<\sigma\left(p+2\right)<\cdots<\sigma\left(p+q\right),$$

$$\sigma\left(p+q+1\right)<\sigma\left(p+q+2\right)<\cdots<\sigma\left(p+q+r\right) .$$

• We let $S\left(\bar{p},q,r\right)$ be the set of all $\sigma \in S\left(p,q,r\right)$ such that $\sigma$ is the identity on $\left\{1,2,...,p\right\}$.

• We let $S\left(p,q,\bar{r}\right)$ be the set of all $\sigma \in S\left(p,q,r\right)$ such that $\sigma$ is the identity on $\left\{p+q+1,p+q+2,...,p+q+r\right\}$.

I cant seem to get this, I am really stuck, I tried doing an example and breaking it down into transpositions but it shed no light on the situation.

Would rather a hint than an answer, although any help is greatly appreciated.

## 1 Answer

Define $n = p+q+r.$ First notice that $$|S(p,q,r)|=\binom{n}{p}\binom{n-p}{q}=\binom{n}{p,q,r},$$ and $|S(p,q+r)|=\binom{n}{p}$ and $|S(\overline{p},q,r)|=\binom{n-p}{q},$ so by multiplication rule $$|S(p,q+r)\times S(\overline{p},q,r)|=|S(p,q,r)|,$$ So if we prove just 1-1 or onto we are done.
Doing 1-1 is kind of painful, so let's see that the map is onto:r

Consider $\alpha \in S(p,q,r),$ we want to find $\sigma \in S(p,q+r),\tau \in S(\overline{p},q,r)$ such that $\sigma \tau = \alpha.$

From there is clear that $\sigma (i)=\alpha (i)$ for $i\leq p$ because if $\tau \in S(\overline{p},q,r),$ then $\tau (i)=i$ for $i\leq p$ but also, as $\sigma\in S(p,q+r)$, then we can uniquely determine $\sigma (j)$ for $j \geq p+1$ by a greedy approach, setting it to be the smallest element in the codomain that doesn't already appear among $\sigma(1), \sigma(2), \ldots, \sigma(j-1)$. In other words: $$\sigma (i) = \left\{ \begin{array}{ll} \alpha (i) & i\leq p \\ \min \{[n]\setminus \sigma ([i-1])\} & p+1\leq i \end{array} \right.$$ where $[n]=\{1,\cdots , n\}.$ From the definition of $\sigma$ is clear that $\sigma$ is in $S(p,q+r).$

Now that we have determined $\sigma,$ $\tau$ can be determined as $$\tau (i) = \left\{ \begin{array}{ll} i & i\leq p \\ \sigma ^{-1}(\alpha (i)) & p+1\leq i \end{array} \right.$$ So the only thing remaining is to show that $\tau \in S(\overline p,q,r),$ so you know that $\tau(i)=i$ for $i\leq p$ by definition. So take $p<i<j\leq p+q,$ so $\tau (i)=\sigma ^{-1}(\alpha (i))$ and $\tau (j)=\sigma ^{-1}(\alpha (j)),$ by definition of $\alpha$ we know that $\alpha (i)<\alpha (j)$ but by construction of $\sigma$ we are taking minimums so if $\sigma (k_1)=\alpha (i)$ and $\sigma (k_2)=\alpha (j)$ then $k_1<k_2$ which means $\sigma ^ {-1}(\alpha (i))<\sigma ^{-1}(\alpha (j))$ so $\tau (i)<\tau (j).$ Apply the same argument when $p+q<i<j\leq n$ and the result follows.

Hope it helps
Edit: An example when $p=q=r=3$,the $\color{red}{red}$ and the black lines to determine $\sigma$: 