Find number of permutations with 3 inversions

abstract-algebracombinationscombinatoricsgenerating-functionspermutations

Let $I(n, k)$ be the number of $n$-permutations that have $k$ inversions.

Here is a post that explains how to find $I(n,2)$: Find number of permutations with 2 inversions

I am interested in $I(n,3)$.

There are three ways to end up with exactly three inversions.

There must have been three steps which created one inversion each. Hence, we simply need to choose which three steps created the three single inversions which can be chosen in $\binom{n-1}{3}$ ways.
There must have been a step which created three inversions. Hence, we simply need to choose which step created the three inversions which can be chosen in $\binom{n-3}{1}$ ways.
There must have been a step which created one inversion and a step which created two inversions.

I am stuck on (3). At first glance, I thought we can simply choose a step to create one inversion and a step to create two inversions in $\binom{n-1}{1}\binom{n-2}{1}$ ways. But this over-counts and I am not fully sure of the reason why. Is it because after we pick a step to create a single inversion in $\binom{n-1}{1}$ ways we don't actually have $\binom{n-2}{1}$ ways to pick a step to create two inversions? We should have less steps, correct?

Can someone help me finish this last case?

For reference $I(4,3)=6$ and $I(5,3)=15$ I believe which we can use as sanity checks.

Also, I was just playing around with numbers and I found this formula:
$I(n,3)=\binom{n-1}{3}+\binom{n-3}{1}+(n-2)^2$
which works satisfies $I(4,3)=6$ and $I(5,3)=15$ so it might be the answer. But I have no clue how to interpret $(n-2)^2$.

(Maybe first pick a step that creates two inversions in $\binom{n-2}{1}$ ways and then for each of those choices, I'm guessing, we have $\binom{n-2}{1}$ ways to pick a step that creates one inversion. Hence we get $(n-2)(n-2)$? But then shouldn't we also be able to pick first the step that creates one inversion in $\binom{n-1}{1}$ ways and then for each of those choices, we have $\binom{n-3}{1}$ ways to pick a step that creates two inversions. Hence $(n-1)(n-3)$?)

Best Answer

You calculated it incorrectly.

A way to enumerate the steps is to use ordered pairs $(a, b)$, where

$ 1\leq a \leq n$, $ 1 \leq b \leq n$,
$a \neq b$,
$ a \neq 1, b \neq 1, 2$ (why?).

How many such ordered pairs are there?
It is not just $n-1$ possibilities for $a$ and $n-3$ possibilities for $b$. EG If $ a= 2$, how many possibilities are there for $b$?

There are $(n-2)^2$ such ordered pairs.
First pick $b$ in $n-2$ ways (not $1, 2$).
Then pick $a$ in $n-2$ ways (not $1, b$).

Related Solutions

[Math] How many 6 digit numbers are possible with no digit appearing more than thrice

A start: Here it is easier to count the complementary number: the number of 6 digit positive integers with four or more of one digit repeated.

This reduces to only four cases: (4, 1, 1), (4, 2), (5, 1), (6).

The rest:

(6) is simply $9$. These are $(111111, 222222, \dots, 999999)$.

(5, 1) is a little trickier. First there are $9 * 8$ ways to choose two distinct digits that aren't either zero and assign each to $5$ or $1$. Then there are ${6 \choose 1}$ ways to permute the order.

Now there's case where one is zero. There are $9$ ways to choose the other digit (it can't be zero or else the entire number is zero). For each combination, there are similarly ${6 \choose 1}$ ways to permute the order. In particular, there are ${6 \choose 1}$ ways to permute five zeros and one of the other digit and another ${6 \choose 1}$ ways to permute one zero and five of the other digit. Exactly half of these are valid by symmetry.

Indeed, the bijection that flips each digit demonstrates this property: if we map, e.g., $aaaa0a \mapsto 0000a0$, exactly one of these will be valid for each pair. In this case, we have $a00000, a0aaaa, aa0aaa, aaa0aa, aaaaa0a, aaaaa0$ as valid strings. In total this gives

$$(9 * 8 + 9) * {6 \choose 1} = 486.$$

(4, 2) is similar. There are $9*8$ ways to initially choose and then ${6 \choose 2}$ ways to permute the order.

If one is zero, again there are $9$ ways to choose the other digit and for each combination the number of ways to permute the order is ${6 \choose 2}$. This is

$$(9 * 8 + 9) {6 \choose 2} = 1215.$$

Finally (4, 1, 1). There are $9 * {8 \choose 2}$ ways to choose non-zero digits and assign them to a frequency. There are then $6! / 4!$ permutations. This gives

$$9 * {8 \choose 2} * 6! / 4! = 7560.$$

Now choose a triplet of unique digits $(a, b, c)$ where one is zero. There are ${9 \choose 2}$ ways of doing so. Now, consider the ${6 \choose 4}$ ways to make a string from four $r$'s (r for repeated) and two $s$'s (s for single). If we are given $rsrrrs$, for example, there are now $3!$ ways to choose one of the digits as the repeated and the other two each into one $s$ spot. Of these, two are invalid, namely when we choose the repeated digit to be zero. You can convince yourself this holds for any string. Thus, this gives

$$4{9 \choose 2}{6 \choose 4} = 2160$$

The grand total is $11430$. There are $900000$ six digit numbers in total, so the desired number is $\boxed{888570}$.

Verified solution on computer in Python:

def get_frequencies(cycle):
    result = 0
    for num in range(10**5, 10**6):
        digit_freq = [0]*10
        for digit in get_digits(num):
            digit_freq[digit] += 1
        digit_cycle = sorted([x for x in digit_freq if x != 0], reverse=True)
        if digit_cycle == cycle:
            result += 1
    return result

def get_digits(num):
    r = []
    while num > 0:
        r.append(num % 10)
        num /= 10
    return r

Running with the following main function:

def main():
    print get_frequencies([6], 6)
    print get_frequencies([5, 1], 6)
    print get_frequencies([4, 2], 6)
    print get_frequencies([4, 1, 1], 6)

Outputs the following lines:

Or, more directly, we can use this program:

def get_frequency_atmost(max_freq, n):
    result = 0
    for num in range(10**(n-1), 10**n):
        digit_freq = [0]*10
        for digit in get_digits(num):
            digit_freq[digit] += 1
        if max(digit_freq) > max_freq:
            result += 1
    return 10**n - 10**(n-1) - result

which prints $888570$ on input get_frequency_atmost(3, 6).

[Math] Number of ways to choose 3 items out of 8 if 2 items can not both be choosen

Tip: If you are counting selections of items from sets, go straight to binomial coefficients and do not pass confusion about "order not being important".

${}^n\mathrm C_r$ counts selections of $r$ items from $n$. Then you just need to puzzle out whatfore you are selecting from wherefore.

To count selections of three items from eight when two of the items are incompatible, you:

Count the selections of any three from all eight, minus selections of both incompatible and one from the other six.$$\require{cancel}{}^8\mathrm C_3-\bcancel{{}^2\mathrm C_2}{}^6\mathrm C_1 = \dfrac{8\cdot 7\cdot 6}{3\cdot 2\cdot 1}-\frac{6}{1}$$
Count the selection of any three from the other six, plus the selections of one from the incompatibles and two from the other six. $${}^6\mathrm C_3+{}^2\mathrm C_1{}^6\mathrm C_2~=~\frac{6\cdot 5\cdot 4}{3\cdot 2\cdot 1}+\frac{2}{1}\cdot\frac{6\cdot 5}{2\cdot 1}$$

Best Answer

Related Solutions

[Math] How many 6 digit numbers are possible with no digit appearing more than thrice

[Math] Number of ways to choose 3 items out of 8 if 2 items can not both be choosen

Related Question