Reference no: EM131571740

Question: 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 ai is a nonnegative integer not exceeding i, for i = 1, 2,...,n - 1. The integers a1, a2,...,an-1 are called the Cantor digits of this integer.

Given a permutation of {1, 2,...,n}, let ak-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, a1 is the number of integers less than 2 that follow 2, so a1 = 1. Similarly, for this example a2 = 2, a3 = 3, and a4 = 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 a1, a2,...,an-1, defined in this way, as its Cantor digits.