4
$\begingroup$

It's easy to deduce the formula for $n$-permutations with exactly $k$ fixed points. The result is similar to $n$-derangement formula and it's equal to $ D_{n,k}= \frac{n!}{k!}\sum_{i=0}^{n-k}\frac{(-1)^i}{i!}$. But I think it is not convenient. Last time I saw the problem in which you had to write a program that for a given $n,k$ (with even eighteen digits!) count $D_{n,k}$. So I'm wondering is there any better formula for this? Maybe recursive formula, like for $n$-derangements $D_n=n\cdot (D_{n-1}+D_{n-2})$?

  • 0
    I guess the key issue remaining now is to find $D_{n,0} \mod p$ efficiently. $D_n= \sum_{i=0}^n (-1)^i \frac{n!}{i!}$. Note that if $n\geq i+p$ then $n!/i!$ contains at least $p$ consecutive integers and therefore is equal to $0$ modulo $p$. $D_n = \sum_{i=n-p+1}^{n} (-1)^i \frac{n!}{i!}$ which should be easy to calculate since $p$ is so small. :)2012-04-18

2 Answers 2

2

Use the fact that $D_{n,k} = ^nC_k.D_{n-k,0}$ and $D_{n,0} = round (\frac{n!}{e})$.

So $D_{n,k} = {n\choose k} \times round (\frac{(n-k)!}{e})$

  • 0
    unfortunately $D_{n,0}=(n-1)(D_{n-1,0} + D_{n-2,0})$ appears to be too slow. To compute $D_{n-k,0}$ I need $n-k$ operations (iterated algorithm). What if $n=10^{17}$ and $k=100$? It will not finish in finite time.2012-04-17
2

The answer is already in the comments. I am just putting together the parts here.

We need to calculate $D_{n,k}$ modulo $p$ for some prime $p$ with the constraints $0\leq k\leq n \leq 2. 10^{18}$ and p<1000.

First thing to notice is that $D_{n,k}= {n \choose k} D_{n-k} $. Also, ${n \choose k}$ is easy to calculate using Lucas' theorem. This can be done with $O(p^2)$ operations modulo $p$.

To calculate $D_n = \sum_{i=0}^n (-1)^i \frac{n!}{i!}$ modulo $p$, we note that if $n\geq i+p$, then $\frac{n!}{i!}=0$ modulo $p$ as there are at least p consecutive numbers in the product. Hence, $D_n = \sum_{i=n-p+1}^n(-1)^i \frac{n!}{i!}= \sum_{i=0}^{p-1}(-1)^{n-i}. \frac{n!}{(n-i)!}$. This sum can be calculated with $O(p)$ operations modulo $p$.

  • 0
    thank$ $you$ $very$ $much Shitikanth :-)2012-04-18