Chapter 6.6, Problem 13E

List all 3-permutations of {1,2,3,4,5}.

The remaining exercises in this section develop another algorithm for generating the permutations of {1,2,3,n}. This algorithm is based on Cantor expansions of integers. Every nonnegative integer less than n! has a unique Cantor expansion

where a,- is a nonnegative integer not exceeding i, for i = 1,2,n -1. The integers a_1; a₂, a_n__t are called the Cantor digits of this integer.

Given a permutation of {1,2,..., n}, let fl^_1;k =2,3,..., n, be the number of integers less than k that follow k in the permutation. For instance, in the

permutation 43215, a_t is the number of integers less than 2 that follow 2, so a_t = 1. Similarly, for this examplea₂= 2, a₃=3, and a₄ = 0. Consider the function from the set of permutations of {1,2,3,..., n} to the set of nonnegative integers less than n! that sends a permutation to the integer that has a„ a₂,a_n_„ defined in this way, as its Cantor digits.