Find bijection $\phi:[n]\times S_{n-1}\to S_n$ and conclude that $\vert S_n\vert = n!$

Question

$[n] = \{1,...,n\}$
I am struggling with finding the bijection.

$\underline{\text{Assume } \mathbf{n=3:}}$

Than we have $A:=[n]\times S_{n-1} = \{(1,\pi_1), (2,\pi_1),(3,\pi_1),(1,\pi_2), (2,\pi_2),(3,\pi_2)\}$,
with $\pi_1 = id$ and $\pi_2 = (12)$

$S_3 = \{(123), (12)(3), (13)(2), (23)(1), (132), id\}$

So we are looking for some $\phi:A\to S_3$. The mapping for $a\in A \mapsto \sigma\in S_3$ is not obvious to me.

Has someone a hint?

The conclusion should be easy if the bijection is found.

Edit:
Due to your hints and further research I found
$\phi:[n]\times S_{n-1}\to S_n, (i,\pi_j)\mapsto \pi_j\circ (in)$, $i\in[n], j\in [n-1]$

My current status on $\phi^{-1}$ is:
$\phi^{-1}:S_n\to [n]\times S_{n-1}, \pi \mapsto (\pi^{-1}(n), ???)$

I am still struggling with $\phi^{-1}$. Does someone has a hint?

Answer 1

A permutation $\pi$ of $S_n$, which is a bijective map from $[n]$ to $[n]$, is completely characterized by specifying $\pi(i)$ for all $i\in[n]$. The idea is that we can break this into two parts, (1) the specification of $\pi(n)$, and (2) the specification of $\pi(i)$ for $i\in[n-1]$. If $\pi(n)=n$ then $\pi$ restricted to $[n-1]$ is just an element of $S_{n-1}$. On the other hand if $\pi(n)=j\ne n$, then $\pi(i)\ne j$ for any $i\in[n-1]$ but $\pi(k)=n$ for some $k\in[n-1]$. So $\pi$ restricted to $[n-1]$ is a bijective map from $[n-1]$ to $[n]\setminus\{j\}$, which is not so different from a bijective map from $[n-1]$ to $[n-1]$, that is, from an element of $S_{n-1}$. (Both are bijective maps between sets of size $n-1$.)

To realize a concrete bijection between these two kinds of bijective map, we send the map $\pi$, restricted to $[n-1]$, to an element of $S_{n-1}$ by composing $\pi$ with the swap $(jn)$. Note that composition with $(jn)$ is an involution: composing $\pi$ with $(jn)$ twice in succession gives $\pi$.

So for $\pi\in S_n$ use the map $\pi\mapsto(j,\pi\circ(jn))$, where $j=\pi(n)$ and $\pi\circ(jn)$ means the permutation $\pi$ is followed by the swap $(jn)$. The map $\pi\circ(jn)$ is here understood, by restricting to $[n-1]$, as an element of $S_{n-1}$, which is possible since it maps $n$ to itself. The definition of this map applies even when $j=n$ since then $(jn)$ is the identity permutation.

For the inverse, just use the fact that composition with $(jn)$ is an involution. Let $\rho\in S_{n-1}$. Then use the map $(j,\rho)\mapsto\rho\circ(jn)$. In this definition $\rho$ is understood as an element of $S_n$ that sends $n$ to itself.

Answer 2

Well, we have $\pi_1 = \pmatrix{1 & 2\\ 1&2}$ and $\pi_2 = \pmatrix{1 & 2 \\ 2 & 1}$ or as sequences of the images $\pi_1 = 12$ and $\pi_2=21$ without delimiters.

Rule: in $(i,\pi)$ write $n$ in the $i$th position of $\pi$. Here:

$(1,p_1) = 312$, $(2,p_1)=132$ and $(3,\pi_1)= 123$ or $(1,\pi_1) = \pmatrix{1 & 2 & 3\\ 3&1&2}$, $(2,\pi_1) = \pmatrix{1 & 2 & 3\\ 1&3&2}$ and $(3,\pi_1) = \pmatrix{1 & 2 & 3\\ 1&2&3}$. This demonstrates also the general situation.

Answer 3

This is not a very elegant way of recursively deriving the factorial expression for the order of the finite symmetric groups, but nevertheless let us attempt a suggestion.

Fix $n \in \mathbb{N}$ and consider the map: $$\begin{align*} \Phi \colon \Sigma_{n+1} &\to [1, n+1] \times \Gamma\\ \Phi(\sigma)&=\left(\sigma(n+1), (n+1\ \sigma(n+1)) \circ \sigma\right), \end{align*}$$ where $\Gamma=\mathrm{Stab}_{\Sigma_{n+1}}(n+1)$ is the subset (subgroup actually) of permutations of the natural interval $[1, n+1]$ which fix $n+1$, subset which is clearly isomorphic (as a group, even!) to $\Sigma_n$.

The map $\Phi$ is the bijection you are looking for.