Question

List all 3-permutations of\({\rm{\{ 1,2,3,4,5\} }}\).

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

\({{\rm{a}}_{\rm{1}}}{\rm{1! + }}{{\rm{a}}_{\rm{2}}}{\rm{2! + L + }}{{\rm{a}}_{{\rm{n - 1}}}}{\rm{(n - 1)!}}\)

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

Given a permutation of\({\rm{\{ 1,2, \ldots ,n\} }}\), let \({{\rm{a}}_{{\rm{k - 1}}}}{\rm{,k = 2,3, \ldots ,n}}\), be the number of integers less than k that follow k in the permutation. For instance, in the permutation \({\rm{43215,}}{{\rm{a}}_{\rm{1}}}\)is the number of integers less than 2 that follow 2 , so\({{\rm{a}}_{\rm{1}}}{\rm{ = 1}}\). Similarly, for this example\({{\rm{a}}_{\rm{2}}}{\rm{ = 2,}}{{\rm{a}}_{\rm{3}}}{\rm{ = 3}}\), and\({{\rm{a}}_{\rm{4}}}{\rm{ = 0}}\). Consider the function from the set of permutations of \({\rm{\{ 1,2,3, \ldots ,n\} }}\)to the set of nonnegative integers less than n! that sends a permutation to the integer that has\({{\rm{a}}_{\rm{1}}}{\rm{,}}{{\rm{a}}_{\rm{2}}}{\rm{, \ldots ,}}{{\rm{a}}_{{\rm{n - 1}}}}\), defined in this way, as its Cantor digits.

Short answer

The possible 3 - permutation list is as follows:

\(\left( {\begin{array}{*{20}{l}}{{\rm{123,124,125,132,134,135,142,143,145,152,153,154,213,}}}\\{{\rm{214,215,231,234,235,241,243,245,251,253,254,312,314,}}}\\{{\rm{315,321,324,325,341,342,345,351,352,354,412,413,415}}}\\{{\rm{421,423,425,431,432,435,451,452,453,512,513,514,521,}}}\\{{\rm{523,524,531,532,534,541,542,543}}}\end{array}} \right)\)

Step-by-step solution

Definition of Concept

Permutations: A permutation of a set is a loosely defined arrangement of its members into a sequence or linear order, or, if the set is already ordered, a rearrangement of its elements, in mathematics. The act of changing the linear order of an ordered set is also referred to as "permutation."

Lexicographic order: The lexicographic or lexicographical order (also known as lexical order or dictionary order) in mathematics is a generalization of the alphabetical order of dictionaries to sequences of ordered symbols or, more broadly, elements of a totally ordered set.

List all 3-permutations of given set

Considering the given information:

The set\({\rm{\{ 1,2,3,4,5\} }}\)

Using the following concept:

Permutation is the action of altering the arrangement of a set of items, particularly their linear order.

Consider the following set of numbers:\({\rm{\{ 1,2,3,4,5\} }}\)

3 - permutation of a given set denotes a three-digit number that can be generated from the given set.

So, the possibility of digits in one's place for a three-digit number formed from the digits in the above set is 5.

The total number of permutations can be calculated as follows:

\(\begin{array}{c}{\rm{5}}{{\rm{P}}_{\rm{3}}}{\rm{ = }}\frac{{{\rm{5!}}}}{{{\rm{(5 - 3)!}}}}\\{\rm{ = }}\frac{{{\rm{5!}}}}{{{\rm{2!}}}}\\{\rm{ = 60}}\end{array}\)

Therefore, the required possible 3 - permutation one listed as followed:

\(\left( {\begin{array}{*{20}{l}}{{\rm{123,124,125,132,134,135,142,143,145,152,153,154,213,}}}\\{{\rm{214,215,231,234,235,241,243,245,251,253,254,312,314,}}}\\{{\rm{315,321,324,325,341,342,345,351,352,354,412,413,415}}}\\{{\rm{421,423,425,431,432,435,451,452,453,512,513,514,521,}}}\\{{\rm{523,524,531,532,534,541,542,543}}}\end{array}} \right)\)

There are a total of 60 permutations.