Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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})$?

share|improve this question
    
$D_{n,k} = \frac {n}{k} D_{n-1,k-1}$. Does that help? (At least it works if n-k is not too large.) –  Shitikanth Apr 17 '12 at 12:28
    
I do not know if it would work in mentioned programming task, but I like this recursion very much. I would just satisfy my curiosity and to know how you derived the recursion? What is combinatorial interpretation here? And somehow I can not make the boundary conditions. I thought $D_{n,0}=n\cdot(D_{n-1,0}+D_{n-2,0})$; for $n<0$ or $k<0$ we have $D_{n,k}=0$; for $n=0$ and $k=0$ we have $D_{n,k}=1$; and for other cases your recursion but this algorithm returns wrong answers (the fault is mine but I don't know what I forgot). –  xan Apr 17 '12 at 13:50
    
Well, the way i did it was to use the expression you had given for $D_{n,k}$ to express $D_{n,k+1}$ and $D_{n+1,k}$ in terms of $D_{n,k}$ and then notice that the expression for $D_{n+1,k+1}$ was really simple. In retrospect, I think that it would have been much easier to just write $D_{n,k}={n \choose k} D_{n-k,0}$ and use ${n \choose k} = \frac{n}{k} {{n-1} \choose {k-1}}$ –  Shitikanth Apr 18 '12 at 3:24
    
I don't see how you could have got a wrong answer except for making some programming error. (Been there, done that. They are hard to avoid.) Can you perhaps point me to the original question? –  Shitikanth Apr 18 '12 at 3:31
    
Thank you Shitikanth very much. The original question is in the comments under the answer to this question. For now the main problem is to construct formula which will need less operations. That could work for even $0\le k\le n\le 10^{18}$. We are interested in result mod prime $p$. ${n\choose k} \ mod \ p$ can be effectively count by Lucas theorem, but $D_{n-k,0}$ still need too many operations. –  xan Apr 18 '12 at 15:27

2 Answers 2

up vote 0 down vote accepted

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})$

share|improve this answer
    
It's very useful, thank you. But hard to compute for large $n,k$. –  xan Apr 17 '12 at 13:53
    
Could you point me to the programming question? Provided we compute factorials from 1 upwards and simply store the values for k! and (n-k)! in memory while doing this, this expression should only involve a small constant number of multiplication/division operations over the computation of n!, and I don't think we can really do away with the computation of n!. –  Wonder Apr 17 '12 at 13:57
    
This programming task is less important. Personally I think it is very weird. The task is to compute $D_{n,k} \ mod \ p$ for a given $0\le k\le n\le 2\cdot 10^{18}$ and $p<1000$. So the only way I think is to deduce recursive formula but not linear, it must be faster. I thought about relation between $D_{2n,2k}$ and $D_{n,k}$ but don't know if there exist one. More I was concerned about deducing some new formulas (how to do such things) different than mine, but maybe you know how to approach this task? –  xan Apr 17 '12 at 14:24
    
The key is that we have to act mod p. Is p given to be prime? –  Wonder Apr 17 '12 at 14:28
    
I would use the recurrence $D_{n,0} = (n-1)(D_{n-1,0} + D_{n-2,0})$ to efficiently compute $D_{n-k,0}$ mod p. Similarly for {n \choose k}, if p is prime we can even use inverses mod p. –  Wonder Apr 17 '12 at 14:37

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$.

share|improve this answer
    
thank you very much Shitikanth :-) –  xan Apr 18 '12 at 19:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.