Bijection from permutations to restricted n-tuples

126 Views Asked by At

Let $A_n$ be the set of permutations of $1,\dots,n$. Let $B_n$ be the set of $n$-tuples $(b_1,\dots,b_n)$ such that $1\le b_i\le i$ for each $i\in 1,\dots, n$. Construct a bijection from $A_n$ to $B_n$. (Hint: Use induction on $n$, employing a bijection from $A_{n-1}$ to $B_{n-1}$ to construct a bijection from $A_n$ to $B_n$. Below we illustrate this process for $n=3$.)

$\begin{matrix} A_3 & 321 & 231 & 213 & 312 & 132 & 123 \\ B_3 & 111 & 112 & 113 & 121 & 122 & 123 \end{matrix}$

Since the size of $B_n$ is $n!$ a bijection from $A_n$ to $B_n$ trivially exists. But presumably the example given is an illustration of some kind of canonical bijection that is meaningful. However, I don't see what the meaningful idea is.