Permutations of a given set with exact inversions

[lillyRosetta]

Homework Statement

How many permutations of S = {1,2,3,4,5,6} have exactly 15 inversions, 14 inversions, and 13 inversions? I think I got the first one, but not sure how to go about finding the rest

Homework Equations

There are 6 digits so we'll name them: a1 a2 a3 a4 a5 a6 after 1 2 3 4 5 6 from the problem.

The Attempt at a Solution

Make a table:a1 a2 a3 a4 a5 a6
0 0 0 0 0 0
1 1 1 1 1
2 2 2 2
3 3 3
4 4
5

The first column of the table is derived from the first digit a1 = 1, since there is no integer larger than 1 to the left of it, so 0 is the null space...However, if a6 = 1 then there would be 5 integers to the left of 1 that would be larger than it. The rest of this logic is used to complete the table.

The last digits in the table are 543210, and they add up to 15. So, (ai + 1) to each digit to get 654321, which has exactly 15 inversions. I think it's the only one, but I'm not sure how to prove that. Also, I'm not sure how to figure out how many permutations have exactly 13 and 14 inversions.

 

[mighty2000]

To find the number of permutations with exactly 13, 14, or 15 inversions, we can use the concept of parity. Inversions are pairs of numbers where the first number is larger than the second number but appears to the right of it. For example, in the permutation 654321, there are 5 inversions: (6,5), (6,4), (6,3), (6,2), and (6,1).

We can represent each permutation as a sequence of numbers, where the first number represents the position of 1, the second number represents the position of 2, and so on. For example, in the permutation 654321, the sequence would be 654321.

Now, let's focus on the number of inversions in each sequence. We can see that for every digit in the sequence, there are a certain number of inversions that are already "counted" in the previous digits. For example, in the sequence 654321, the first digit (6) has 5 inversions, but 4 of those inversions are already counted in the second digit (5). Similarly, the second digit (5) has 4 inversions, but 3 of those inversions are already counted in the third digit (4), and so on.

Using this concept, we can determine the number of inversions in each sequence. For example, in the sequence 654321, the number of inversions would be: 5 (for the first digit) + 4 (for the second digit) + 3 (for the third digit) + 2 (for the fourth digit) + 1 (for the fifth digit) + 0 (for the sixth digit) = 15 inversions.

Now, let's look at the number of inversions in each sequence for permutations with 14 and 13 inversions. For 14 inversions, we can have sequences with the following number of inversions: 5+4+3+2+0+0 = 14, 5+4+2+1+1+0 = 14, 5+3+2+2+1+1 = 14, 4+3+3+2+1+1 = 14. For 13 inversions, we can have sequences with the following number of inversions: 5+4+3+2+0+