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

Chapter 9, Problem 13E

(choose chapter or problem)

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, \ldots, \mathrm{n}\}\). This algorithm is based on Cantor expansions of integers. Every nonnegative integer less than \(\mathrm{n} !\) has a unique Cantor expansion

                                     \(a_{1} 1 !+a_{2} 2 !+\cdots+a_{n-1}(n-1) !\)

where ai is a nonnegative integer not exceeding \(\mathrm{i}\), for \(\mathrm{i}=1,2, \ldots, \mathrm{n}-1\). The integers \(\mathrm{a}_{1}, \mathrm{a}_{2}, \ldots, \mathrm{a}_{\mathrm{n}-1}\) are called the Cantor digits of this integer.

Given a permutation of \(\{1,2, \ldots, \mathrm{n}\}\), let \(\mathrm{a}_{\mathrm{k}-1}, \mathrm{k}=2,3, \ldots, \mathrm{n}\), be the number of integers less than \(\mathrm{k}\) that follow \(\mathrm{k}\) in the permutation. For instance, in the permutation \(43215, \mathrm{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\), and \(a_{4}=0\). Consider the function from the set of permutations of \(\{1,2,3, \ldots, \mathrm{n}\}\) to the set of nonnegative integers less than \(n !\) that sends a permutation to the integer that has \(a_{1}, a_{2}, \ldots, a_{n-1}\), defined in this way, as its Cantor digits.

Equation Transcription:

{1, 2, 3, 4, 5}

{1, 2, 3,...,n}

i = 1, 2,...,n − 1

a1, a2,...,an-1

2,...,n}, let ak-1, k = 2, 3,...,n

Text Transcription:

{1, 2, 3, 4, 5}

{1, 2, 3,...,n}

i = 1, 2,...,n − 1

a_1, a_2,...,a_n-1

2,...,n},  

a_k-1, k = 2, 3,...,n