[step:Identify the composition $\tau \circ \rho$ as a $(p, q, r)$-shuffle and check the sign matches]Define
\begin{align*}
\mathrm{Sh}(p, q, r) := \{ \sigma \in S_n : \sigma(1) < \dots < \sigma(p),\; \sigma(p+1) < \dots < \sigma(p+q),\; \sigma(p+q+1) < \dots < \sigma(n)\},
\end{align*}
the set of $(p, q, r)$-shuffles — permutations of $\{1, \dots, n\}$ that are strictly increasing on each of the three blocks $B_1 = \{1, \dots, p\}$, $B_2 = \{p+1, \dots, p+q\}$, $B_3 = \{p+q+1, \dots, n\}$.
For each $\rho \in \mathrm{Sh}(p, q)$, extend it to $\tilde\rho \in S_n$ by $\tilde\rho(j) = j$ for $j \in B_3$ (so $\tilde\rho$ fixes the last $r$ positions). With this extension, $\mathrm{sgn}(\tilde\rho) = \mathrm{sgn}(\rho)$, since adjoining $r$ fixed points contributes no inversions. We claim the map
\begin{align*}
\Phi: \mathrm{Sh}(p+q, r) \times \mathrm{Sh}(p, q) &\to \mathrm{Sh}(p, q, r) \\
(\tau, \rho) &\mapsto \tau \circ \tilde\rho
\end{align*}
is a bijection, and $\mathrm{sgn}(\tau \circ \tilde\rho) = \mathrm{sgn}(\tau)\, \mathrm{sgn}(\rho)$.
We prove these in two sub-claims.
[claim:$\tau \circ \tilde\rho \in \mathrm{Sh}(p, q, r)$ for every $(\tau, \rho) \in \mathrm{Sh}(p+q, r) \times \mathrm{Sh}(p, q)$]
[proof]
Let $\sigma := \tau \circ \tilde\rho$. We verify the three monotonicity conditions.
On $B_1 = \{1, \dots, p\}$: by definition of $\rho \in \mathrm{Sh}(p, q)$, $\rho(1) < \rho(2) < \dots < \rho(p)$, and these values all lie in $\{1, \dots, p+q\}$. Since $\tau$ restricted to $\{1, \dots, p+q\}$ is strictly increasing (the first half of being a $(p+q, r)$-shuffle), the composition $\tau \circ \tilde\rho$ is strictly increasing on $B_1$: $\sigma(1) < \dots < \sigma(p)$.
On $B_2 = \{p+1, \dots, p+q\}$: by definition of $\rho$, $\rho(p+1) < \dots < \rho(p+q)$, with values in $\{1, \dots, p+q\}$. By the same monotonicity of $\tau$ on $\{1, \dots, p+q\}$, $\sigma(p+1) < \dots < \sigma(p+q)$.
On $B_3 = \{p+q+1, \dots, n\}$: $\tilde\rho$ fixes $B_3$ by construction, so $\sigma(j) = \tau(j)$ for $j \in B_3$. Since $\tau \in \mathrm{Sh}(p+q, r)$ is strictly increasing on $B_3$ by definition, so is $\sigma$.
Hence $\sigma \in \mathrm{Sh}(p, q, r)$.
[/proof]
[/claim]
[claim:Every $\sigma \in \mathrm{Sh}(p, q, r)$ has a unique preimage under $\Phi$]
[proof]
Fix $\sigma \in \mathrm{Sh}(p, q, r)$. We construct the unique $(\tau, \rho)$ with $\tau \circ \tilde\rho = \sigma$.
Let $A := \sigma(B_1 \cup B_2) = \{\sigma(1), \dots, \sigma(p+q)\} \subseteq \{1, \dots, n\}$, a subset of cardinality $p+q$, and let $A^c := \{1, \dots, n\} \setminus A = \sigma(B_3)$.
**Construction of $\tau$.** Define $\tau \in S_n$ as follows: $\tau$ maps $\{1, \dots, p+q\}$ bijectively and increasingly onto $A$, and maps $\{p+q+1, \dots, n\}$ bijectively and increasingly onto $A^c$. Explicitly, if we list $A = \{a_1 < a_2 < \dots < a_{p+q}\}$ and $A^c = \{b_1 < b_2 < \dots < b_r\}$, set $\tau(j) = a_j$ for $1 \le j \le p+q$ and $\tau(p+q+k) = b_k$ for $1 \le k \le r$. By construction $\tau \in \mathrm{Sh}(p+q, r)$, and the choice of $\tau$ is forced once $A$ is known (the increasing enumeration of $A$ is unique). Also $\sigma(B_3) = A^c$ is the increasing enumeration of $A^c$ (because $\sigma$ is increasing on $B_3$), which coincides with $\tau(B_3)$, so $\sigma|_{B_3} = \tau|_{B_3}$.
**Construction of $\rho$.** Define $\tilde\rho := \tau^{-1} \circ \sigma$. Since $\sigma(B_3) = \tau(B_3) = A^c$ and both $\sigma|_{B_3}$ and $\tau|_{B_3}$ enumerate $A^c$ increasingly, $\sigma|_{B_3} = \tau|_{B_3}$, hence $\tilde\rho|_{B_3} = \mathrm{id}|_{B_3}$. So $\tilde\rho$ is the extension by identity of its restriction $\rho := \tilde\rho|_{\{1, \dots, p+q\}}$.
It remains to check $\rho \in \mathrm{Sh}(p, q)$. By definition of $\tau$, $\tau^{-1}$ maps $A$ bijectively and increasingly onto $\{1, \dots, p+q\}$. Since $\sigma$ is increasing on $B_1$ with image inside $A$, the composition $\rho = \tau^{-1} \circ \sigma$ is increasing on $B_1$. Similarly increasing on $B_2$. So $\rho \in \mathrm{Sh}(p, q)$.
**Uniqueness.** Conversely, if $\tau \circ \tilde\rho = \sigma$, then $\sigma(B_1 \cup B_2) = \tau(\tilde\rho(B_1 \cup B_2)) = \tau(\{1, \dots, p+q\}) = A$ (since $\tilde\rho$ permutes $\{1, \dots, p+q\}$ and fixes $B_3$), which determines $A$ from $\sigma$, hence determines $\tau$ uniquely (as the unique $(p+q, r)$-shuffle with $\tau(\{1, \dots, p+q\}) = A$), and then $\tilde\rho = \tau^{-1} \circ \sigma$ is determined.
Hence $\Phi$ is a bijection.
[/proof]
[/claim]
The sign identity $\mathrm{sgn}(\tau \circ \tilde\rho) = \mathrm{sgn}(\tau)\, \mathrm{sgn}(\tilde\rho) = \mathrm{sgn}(\tau)\, \mathrm{sgn}(\rho)$ follows from the [Sign Homomorphism](/theorems/778) being a group homomorphism $\mathrm{sgn}: S_n \to \{\pm 1\}$ together with $\mathrm{sgn}(\tilde\rho) = \mathrm{sgn}(\rho)$.[/step]