I don\'t understand. Please help me with my question. the following solution pro

Question

I don't understand. Please help me with my question. the following solution provided is unclear perhaps because I don't understand the formula going from an inversion to a permutation.

PTER 4. GENERATING PERMUTATIONS AND COME NAT inversion sequence of the permutation 31524 is The Example 1, 2, 0, 1,0. The inversion sequence al, a 2, permutation iii2 ...in satisfies 0 an-1 1, an-0 n-k integers in the set (1,2, This is so because for each k=1,2, which are greater than k. Using the n of sequences of intom My question is based on this example: Using the inversion 12010 to construct the following permutation. please explain. trying to learn this in order to be able to apply this to others. princinle u

Explanation / Answer

Observe the permutation 31524

Before 1, the numbers are 3, is it greater than 1? Yes. It is a single number so for the first position number of inversion is 1.

Before 2, the numbers are 3, 1, 5, how many are greater than 2? Namely 3,5. These are two numbers so for the second position number of inversions is 2.

Before 3, no numbers; how many are greater than 3? None. so for the third position number of inversions is 0.

Before 4, the numbers are 3, 1, 5, 2; how many are greater than 4? Namely 5. It is a single number so for the fourth position number of inversion is 1.

Before 5, the numbers are 3, 1; how many are greater than 5? None. so for the fifth position number of inversions is 0.

Thus we got the inversion 1, 2, 0, 1, 0

Now we want to go backward to construct the permutation given the inversion 1, 2, 0, 1, 0.

Observe that since there are 5 places in the permutation so bigest number is 5. Now if 5 is the first number than 0 in the 3rd place in the inversion, tells that before 3 no larger number present. That is both 4 and 5 will be somewhere after 3.

The fourth inversion number1, says that 5 must be before 4.

Thus we have the order 3,…,5,…,4

The second inversion number 2, says that before 2 minimum two numbers are there and that exactly two larger numbers. So the position of 2 is after 3, 5 and before 4. Thus we have the ordering

3,…,5,…2,…,4.

The first inversion number 1, says that before 1 minimum two numbers are there and that exactly one larger number. So the position of 1 is after 3, and before 5. Thus we have the ordering

3,1,5,2,4.

Hence the permution is recovered as 3, 1, 5, 2, 4.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.