# Bijection from permutations to restricted n-tuples

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.

• I'm not sure what 'construct a bijection' means. The example shows how you can set a $n!$-terms sequence $(a_i)_{1\le i\le n!}$ of permutations and $n!$-terms sequence $(b_i)_{1\le i\le n!}$ of tuples. Then we declare a bijection as the sequences' terms correspondence $a_i \leftrightarrow b_i$. Done. Shall we do something else? Say, define how to directly calculate $b_i$ when given $a_i$ and vice versa? – CiaPan Jul 22 '14 at 20:52