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

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

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
  • Проголосовать: не нравится

»
4 года назад, скрыть # |
← 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 \lt t_2 \lt ... \lt 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 $$$ \gt t_i$$$ would contribute, and there are $$$n-k-t_i+i$$$ elements $$$ \gt 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 \lt t_1 \lt t_2 ... \lt 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.

»
4 года назад, скрыть # |
← 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.