Question

Show that the correspondence described in the preamble is a bijection between the set of permutations of \({\rm{\{ 1,2,3, \ldots ,n\} }}\)and the nonnegative integers less than n !.

Short answer

The assignment using cantor integers between set of permutation of \({\rm{\{ 1,2,3, \ldots \ldots }}..{\rm{n\} }}\)& the non-negative integers less than n ! is a bisection.

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 generalisation 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 of permutation of\({\rm{\{ 1,2,3, \ldots \ldots n\} }}\)& non negative integers less than n !.

Using the following concept:

There are n ! permutation of n symbols.

If \({{\rm{x}}_{\rm{1}}}{\rm{,}}{{\rm{x}}_{\rm{2}}}{\rm{, \ldots \ldots \ldots }}{{\rm{x}}_{\rm{x}}}\) is permutation then respective cantor digits are \({{\rm{a}}_{\rm{1}}}{\rm{,}}{{\rm{a}}_{\rm{2}}}{\rm{, \ldots \ldots \ldots }}{{\rm{a}}_{{\rm{a - 1}}}}{\rm{ }}\)&integer of cantor expansion is\({{\rm{a}}_{\rm{1}}}{\rm{(1!) + }}{{\rm{a}}_{\rm{2}}}{\rm{(2!) + \ldots \ldots \ldots }}..{\rm{ + }}{{\rm{a}}_{{\rm{n - 1}}}}{\rm{(n - 1)!}}\).

Using cantor expansion, we can show that assignment is bisection by sassing each permutation with an integer k such that\(1 \le k \le n\)!

Assume\({{\rm{x}}_{\rm{1}}}{\rm{,}}{{\rm{x}}_{\rm{2}}}{\rm{ \ldots \ldots }}..{{\rm{x}}_{\rm{n}}}\) is a permutation than respective canton digits are\({{\rm{a}}_{\rm{1}}}{\rm{,}}{{\rm{a}}_{\rm{2}}}{\rm{, \ldots \ldots \ldots }}{{\rm{a}}_{{\rm{n - 1}}}}\)and integer of enactor expansion is\({a_1}(1!) + {a_2}(2!) + \ldots \ldots \ldots .. + {a_{n - 1}}(n - 1)! = k \le n!\)It is clear that different permeation is assigned to different integers.

Using contra passive statement suppose \({\rm{k = m}}\) such that \({{\rm{a}}_{\rm{1}}}{\rm{(1!) + }}{{\rm{a}}_{\rm{2}}}{\rm{(2!) + 3(3!) + \ldots \ldots \ldots }}..{\rm{ + }}{{\rm{a}}_{{\rm{n - 1}}}}{\rm{(n - 1)! = }}{{\rm{b}}_{\rm{1}}}{\rm{(1!) + }}{{\rm{b}}_{\rm{2}}}{\rm{(2!) + \ldots }}\)than the only possibly is \({\rm{ + }}{{\rm{b}}_{{\rm{n - 1}}}}{\rm{(n - 1!)}}{{\rm{a}}_{\rm{1}}}{\rm{ = }}{{\rm{b}}_{\rm{1}}}{\rm{,}}{{\rm{a}}_{\rm{2}}}{\rm{ = }}{{\rm{b}}_{\rm{2}}}{\rm{, \ldots \ldots \ldots \ldots }}{\rm{.}}{{\rm{a}}_{{\rm{n - 1}}}}{\rm{ = }}{{\rm{b}}_{{\rm{n - 1}}}}{\rm{. = }}{{\rm{x}}_{\rm{1}}}{{\rm{x}}_{\rm{2}}}{\rm{ \ldots \ldots }}{{\rm{x}}_{\rm{n}}}{\rm{ = }}{{\rm{y}}_{\rm{1}}}{{\rm{y}}_{\rm{2}}}{\rm{ = }}{{\rm{y}}_{\rm{n}}}\)

Asaresult,theassignmentisaone-to-onemapping.

Inaddition,therearen!permutationston!numbers,andtheassignmentusingcantorintegerisabisection.

Therefore, assignment using cantor integers between a set of permutations of \({\rm{\{ 1,2,3,}}........{\rm{n\} }}\) & the non-negative integers less than n! is a bisection.