The only way so solve it that I've found is to use https://en.wikipedia.org/wiki/Rencontres_numbers and calcuate , but I don't like that. Is there other way? Can we use inclusion-exclusion formula to calculate it?
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 165 |
2 | maomao90 | 163 |
2 | Um_nik | 163 |
4 | atcoder_official | 161 |
5 | adamant | 160 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
9 | nor | 153 |
9 | Dominater069 | 153 |
The only way so solve it that I've found is to use https://en.wikipedia.org/wiki/Rencontres_numbers and calcuate , but I don't like that. Is there other way? Can we use inclusion-exclusion formula to calculate it?
Name |
---|
Why don't you like that?
because I don't understand that
What exactly don't you understand?
Obvious formula, he just troll
Yes we can. Notice that D(N, k) = C(N, k)·!(N - k), and derangement of (N - k) can be calculated this way
Please elaborate
What does "fixed points" mean?
ai = i
There is another solution involving dynamic programming and constructing permutations.
First, consider the following way of constructing all permutations of length n from all permutations of length (n - 1). Suppose we have a permutation of length (n - 1), for example, n = 6 and the permutation is
a b c d e
. Put the new element n at the back of the permutation. Then, swap the new last element with one of the elements, including itself. We get n different permutations:Note that different permutations
a b c d e
produce different permutations of length 6. So, this process allows to construct all permutations of length n from all permutations of length (n - 1).Now, look what happens with the fixed points during this process. Let there be k fixed points in the permutation
a b c d e
. Clearly, 0 ≤ k ≤ (n - 1).If we swap n with n, the number of fixed points increases by 1 (all the fixed points from
a b c d e
plus the new element n).If we swap n with a fixed point (k possibilities), the number of fixed points decreases by 1.
If we swap n with an element which is already not in its place ((n - 1) - k possibilities), the number of fixed points stays constant.
We can now formulate a “forward” dynamic programming approach. If we know D(n - 1, k) = x, it contributes:
x to D(n, k + 1),
x·k to D(n, k - 1) and
x·((n - 1) - k) to D(n, k).
The “backward” dynamic programming solution (of the form D(n, k) = ...) can also be formulated.
The problem of counting permutations with k fixed point is addressed in the book generatingfunctionology, as an example of the interpretation of the inclusion-exclusion principle in terms of generating functions.
The approach yields the result that for a given n, if ak is the number of permutations of size n with exactly k fixed points, then its ordinary power series generating function is .
This gives the formula
, so we can compute the result in .