The remaining exercises in this section develop another algorithm for generating the permutations of $\{1, 2, 3,\dots,n\}.$ This algorithm is based on Cantor expansions of integers. Every nonnegative integer less than $n!$ has a unique Cantor expansion $a_{11!} + a_{22!}+\dots+ a_{n−1(n − 1)!}$ where ai is a nonnegative integer not exceeding $i,$ for $i = 1, 2,\dots n − 1.$ The integers $a_{1}, a_{2},\dots,a_{n−1}$ are called the Cantor digits of this integer. Given a permutation of $\{1, 2,\dots,n\},$ let $a_{k−1}, k = 2, 3,\dots n,$ be the number of integers less than $k$ that follow $k$ in the permutation. For instance, in the permutation $43215, a_{1}$ is the number of integers less than $2$ that follow $2,$ so $a_{1} = 1.$ Similarly, for this example $a_{2} = 2, a_{3} = 3, \:\text{and}\: a_{4} = 0.$ Consider the function from the set of permutations of $\{1, 2, 3,\dots,n\}$ to the set of nonnegative integers less than $n!$ that sends a permutation to the integer that has $a_{1}, a_{2},\dots,a_{n−1},$ defined in this way, as its Cantor digits.
Find the Cantor digits $a_{1}, a_{2},\dots,a_{n−1}$ that correspond to these permutations.
- $246531$
- $12345$
- $654321$
