Question

What is the 31 lth permutation of (1,2,3,4,5,6,7] relative to the lexicographical ordering? (Remember that the 311 th is numbered 310 , since the first element is numbered 0). What is the \(2374 \mathrm{th} ?\)

Short answer

The 31lth permutation is (1, 4, 2, 3, 5, 6, 7), and the 2374th permutation is (4, 1, 5, 2, 3, 7, 6).

Step-by-step solution

Understanding the Problem

We need to find the 310th and 2373rd permutations of the set \((1, 2, 3, 4, 5, 6, 7)\) when listed in lexicographical order. Recall that the first permutation in lexicographical order is indexed as 0, so we adjust the indices given by 1, making them 310 for the 31lth and 2373 for the 2374th in the lexicographical order.

Compute Factorials

To find permutations using lexicographical order, we utilize factorials to determine how many permutations start with a given number. Calculate the factorial of n-1, where n is the number of elements. Here \(n=7\), so calculate \(6! = 720\). This means each initial digit change represents a group of 720 permutations.

Locate the Starting Digit for 310th

Determine which group of 720 contains the 310th permutation. Since \(310 < 1 \times 720\), the permutation is in the first group (starting with 1).

Find Remaining Digits for 310th

Remove '1' and reindex to 310 to begin choosing among \( (2,3,4,5,6,7) \). Calculate \(5! = 120\). Now find which of these sections contains 310. 310th falls in the third group \((2 \text{groups skip, then third group})\) given by \((2\times 120 < 310 < 3 \times 120)\). Thus, permutation begins \((1,4,...)\). Use similar logic iteratively for finding each remaining digit.

Construct the 31lth Permutation

Repeat the steps as described for remaining 3! and 2! finding each digit. Using decreasing remainders, permutation is constructed as \((1,4,2,3,5,6,7)\).

Locate and Construct the 2374th Permutation

Repeat above logic starting with the number larger than \(3 \times 720 = 2160\). Hence fourth block (starts with 4). Continue breakdown using factorial divisions and compute until permutation is found: \((4,1,5,2,3,7,6)\).

Verify the Permutations

Recalc digits through step-by-step enumeration. Confirm that maps correspond to calculated steps and check permutation integrity consistent with lexicographical order.

Key concepts

Lexicographical Order

Lexicographical order is a method related to the dictionary order that ranks permutations. Imagine you are arranging words in a dictionary. Just like in the dictionary, this order arranges numbers from smallest to largest.
For example, consider arranging the numbers from a set like \( \{1, 2, 3, 4, 5, 6, 7\} \). You start by fixing the first element and then proceed to arrange the rest in order.
This method is particularly useful for solving permutation problems because it provides a consistent way to list all possible arrangements of a set.

• First, you fix the first element and then arrange remaining numbers.
• This continues by arranging subsequent numbers, treating each group as a smaller list.

Lexicographical order is powerful because it ensures each number appears previously before moving to a larger number which resembles dictionary rules.

Factorials

Factorials are crucial for calculating permutations because they tell us how many ways we can arrange a given set of numbers. A factorial is denoted by \( n! \), and it represents the product of all positive integers up to \( n \).

• For instance, \( 6! = 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 720 \).
• Factorials help us to determine how many sequences start with a particular digit in permutation problems.

In the context of lexicographical permutations, by knowing the size of a factorial, you can figure out the number of permutations starting with different numbers.
Once you know this, you can narrow down the exact permutation you are seeking, simplifying what could otherwise be very complex calculations.

Combinatorics

Combinatorics is the branch of mathematics that studies combinations and arrangements of objects. It is the foundation for understanding permutations as it equips students with tools to count and arrange elements effectively.
When you're dealing with permutations, you're primarily concerned with how many different ways you can arrange a set of elements, which is a core part of combinatorics.

• Permutations specifically deal with the arrangement of objects where the order does matter.
• Combinatorics teaches us not just to rearrange these objects but to do so in efficient and systematic ways.

This makes combinatorics indispensable for students tackling discrete tasks in mathematics, such as arranging a particular sequence or counting potential outcomes.

Discrete Mathematics

Discrete mathematics is a branch of mathematics dealing with distinct and separated values, unlike continuous mathematics which works with concepts that flow continuously.
Permutations belong to discrete mathematics as they involve discrete numbers and set values.

• It helps us understand concepts like permutations where we work with distinct arrangements of numbers.
• Discrete math offers tools and approaches for systematically calculating arrangements and sequences.

The beauty of discrete mathematics lies in its ability to solve real-world problems using theories tied to arrangements and order.
In our permutational problem-solving, comprehension of discrete mathematics allows students to break down complex sets into smaller, manageable pieces, making it easier to find solutions and understand outcomes.
Whether it's in computer science, cryptography, building algorithms, or solving permutation puzzles, discrete mathematics provides the foundational knowledge required.