Блог пользователя EarthMessenger

Автор EarthMessenger, история, 20 месяцев назад, По-английски

You're given an integer n, answer the number of inversions in all the derangement permutations of length n. For example, if n = 3, there are two derangement premutations, 231 and 312, so the answer is 4.

There is such a sequence in OEIS. But I want to know how this is derived.

It's welcomed if you have other linear solution.

  • Проголосовать: нравится
  • +25
  • Проголосовать: не нравится

»
20 месяцев назад, # |
Rev. 20   Проголосовать: нравится +36 Проголосовать: не нравится

First, we use Principle of Inclusion-Exclusion (PIE). Let's fix at least $$$k$$$ places, we call them $$$t_1, t_2, ..., t_k$$$ ($$$t_1 < t_2 < ... < t_k$$$). $$$k \leq n-2$$$, because fixing $$$\geq n-1$$$ elements contributes nothing to the sum of inversion numbers. There are $$$n-k$$$ free places, the total inversion of these $$$n-k$$$ free places are:

$$$PART1 := \frac{(n-k)!(n-k)(n-k-1)}{4}$$$.

And there are $$$\binom{n}{k}$$$ choices of $$$t_1, t_2, ..., t_k$$$, so we need to multiply $$$PART1$$$ by $$$\binom{n}{k}$$$.

Now we calculate the inversion between the $$$n-k$$$ free places and $$$k$$$ chosen places. For each $$$t_i$$$, its contribution is $$$2(t_i - i)(n - k - t_i + i)(n-k-1)!$$$. Why? For place $$$t_i$$$, there are $$$t_i-i$$$ free places before $$$t_i$$$, we minus $$$i$$$ because $$$i$$$ places are occupied by $$$t$$$. And for each free place, only element $$$> t_i$$$ would contribute, and there are $$$n-k-t_i+i$$$ elements $$$>t_i$$$. We also need to consider the free places after $$$t_i$$$, that's where the $$$2$$$ comes from. Finally we need to multiply $$$(n-k-1)!$$$ as there are $$$(n-k-1)$$$ left place when we fix $$$k$$$ and another one place. Illustration could be found here:

https://ibb.co/F0Xt9tz

Now we need to calculate $$$PART2 := 2(n-k-1)!\sum\limits_{0 < t_1 < t_2 ... < t_k \leq n-k}(t_1 - 1)(n - k - t_1 + 1) + (t_2 - 2)(n - k - t_2 + 2) + ... + (t_k-k)(n - k - t_k + k)$$$. We notice that $$$t_i-i$$$ also form a non-decreasing sequence, and each $$$l (0 \leq l \leq n-k)$$$ occurs $$$\binom{n}{k-1}$$$ times. For example,

n=4, k=3, 000 001 011 111, 0 and 1 both 6 times.

n=5, k=3, 000 001 002 011 012 022 111 112 122 222, 0, 1, 2 all 10 times.

Each $$$l (0 \leq l \leq n-k)$$$ occurs $$$\binom{n}{k-1}$$$ times, and there are $$$\binom{n}{k}$$$ sequences. This could be proven using dynamic programming from the algorithmic perspective, or mathematical induction in a mathematical manner.

Therefore, $$$PART2 = 2(n-k-1)!\binom{n}{k-1}\sum\limits_{l=0}^{n-k}l(n-k-l) = 2(n-k-1)!\frac{n! \cdot k \cdot (n-k-1)}{6k!\cdot (n-k-1)!} = \frac{n! \cdot k \cdot (n-k-1)}{3k!}$$$

Finally, $$$tmpans(n, k) := \binom{n}{k}PART1 + PART2 = \frac{n!(n-k)(n-k-1)}{4k!} + \frac{n! \cdot k \cdot (n-k-1)}{3k!}= \frac{(3n+k)(n-k-1)n!}{12k!}$$$, for each $$$k$$$. To get the final ans, do PIE on $$$tmpans(n, k)$$$ please. $$$finalans := \sum\limits_{k=0}^{n-2}(-1)^k tmpans(n, k) = \sum\limits_{k=0}^{n-2}(-1)^k \frac{n!(3n+k)(n-k-1)}{12k!}$$$.

Upd: Sorry for forgetting $$$2(n-k-1)!$$$ in the $$$PART2=$$$ equation in my original answer. Now it is updated. It is a typo, I forgot to copy it to the latex sheet, instead of a critical calculation error.

  • »
    »
    20 месяцев назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

    Thank for your reply.

    But pay attention that you need to calculate the number of inversions in all the derangement permutation of length n, but not all the permutation of length n. A derangement permutation is a permutation $$$P$$$ such that for all $$$i$$$, $$$P_i \neq i$$$.

    • »
      »
      »
      20 месяцев назад, # ^ |
      Rev. 5   Проголосовать: нравится +10 Проголосовать: не нравится

      I am calculating all the derangement permutations of length $$$n$$$ using PIE. I fix $$$k$$$ places $$$t_1 < t_2 < ... < t_k$$$ where $$$p[t_i] = t_i$$$ for each $$$t_i(1 \leq i \leq k)$$$. Please read carefully and don't use bold, I have to downvote your comment!

      Let me say more in detail. When $$$k = 0$$$, it is a derangement, all right? Then minus $$$k=1$$$, add $$$k=2$$$, that's the procedure of PIE. The below comment is just an addition to my main comment.

»
20 месяцев назад, # |
Rev. 3   Проголосовать: нравится +26 Проголосовать: не нравится

The total inversion of permutations of length $$$n$$$ is $$$\frac{n!\cdot n \cdot (n-1)}{4}$$$. There are $$$\frac{n(n-1)}{2}$$$ pairs, and for each pair $$$\frac{n!}{2}$$$ permutations contribute $$$1$$$. Well, the above proof is incorrect for $$$n=1$$$, as $$$\frac{n!}{2}$$$ is invalid, but we can just judge the case where $$$n=1$$$ (answer is $$$0$$$) specially.