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.

I am working on a programming problem where I need to calculate 'n choose k'. I am using the relation formula $$ {n\choose k} = {n\choose k-1} \frac{n-k+1}{k} $$ so I don't have to calculate huge factorials. Is there any way to use this formula and just keep track of the last 6 digits. Could you compute the next k, with only knowing the some of the last digits.
I understand this is a lot to ask, so all I ask is a point in the right direction. Maths is by far not my strongest subject.
Thanks in advance.

share|improve this question
    
Can you give us an idea of the scale of $n$ or $k$? –  Henry Oct 5 '11 at 18:40
    
0 <= n, k <= 100. –  ricola86 Oct 5 '11 at 18:43

4 Answers 4

up vote 6 down vote accepted

You might also want to use $\binom{n}{k}=\binom{n}{n-k}$ to reduce the case where $k>n/2$.

Using $\binom{n}{k} = \binom{n}{k-1} \frac{n-k+1}{k}$ mod one million has a problem when $(k,10)\not=1$. Such $k$ are zero divisors mod one million, so you cannot divide by $k$ mod one million and get a meaningful result.

However, you can count the number of factors of $p$ that are in $\binom{n}{k}$ for prime $p$. Let $s_p(n)$ be the sum of the base $p$ digits of $n$. Then, the number of factors of $p$ in $\binom{n}{k}$ is $(s_p(k)+s_p(n-k)-s_p(n))/(p-1)$. Thus, instead of multiplying by $n-k+1$ and dividing by $k$, multiply by $n-k+1$ with all factors of $2$ and $5$ removed and divide by $k$ with all factors of $2$ and $5$ removed. At the end, multiply by the number of factors of $2$ and $5$ computed above.

For example, let's compute $\binom{97}{89}=\binom{97}{8}$.

Here are $97$, $8$, and $89$ in base $2$ and $5$ followed by their sum of digits: $$ 97=1100001_2(3)=342_5(9) $$ $$ 8=1000_2(1)=13_5(4) $$ $$ 89=1011001_2(4)=324_5(9) $$ Therefore, the number of factors of $2$ in $\binom{97}{89}$ is $(1+4-3)/(2-1)=2$, and the number of factors of $5$ is $(4+9-9)/(5-1)=1$. Therefore, mod one million,

$$ \begin{align} \binom{97}{8} &=\frac{97}{1}\frac{96/32}{2/2}\frac{95/5}{3}\frac{94/2}{4/4}\frac{93}{5/5}\frac{92/4}{6/2}\frac{91}{7}\frac{90/10}{8/8}\times2^2\times5^1\\ &=\frac{97}{1}\frac{3}{1}\frac{19}{3}\frac{47}{1}\frac{93}{1}\frac{23}{3}\frac{91}{7}\frac{9}{1}\times4\times5\\ &=010441\times20\\ &=208820 \end{align} $$ Everything is good above since we can divide by $3$ and $7$ mod one million.

Caveat: Remember that modular division is quite different than standard division of integers, rationals, and reals. It requires solving a Diophantine equation which usually involves the Euclidean algorithm. For example, $1/7=3\pmod{10}$ because $3\times7=1\pmod{10}$.

share|improve this answer
    
I see after finally posting that most of what I say is covered in the links supplied by Sasha. I hope the example gives it some added value. –  robjohn Oct 5 '11 at 21:46
    
this is good stuff thanks. It's well explained and I've surprised myself in being able to understand it. +1. –  ricola86 Oct 7 '11 at 15:14
1  
@ricola86: as long as you remember that division $\pmod{m}$ is quite different than normal division. It requires solving a diophantine equation and usually involves the Euclidean algorithm. E.g. $1/7=3\pmod{10}$. –  robjohn Oct 7 '11 at 15:38
1  
+1,Nice explanation,you may also like to add the final comment in the actual answer as well. –  Quixotic Oct 7 '11 at 18:20
    
@FoolForMath: Good idea. I have added a caveat to my answer. –  robjohn Oct 7 '11 at 19:40

You may find the following page of interest.

Much of the math behind it is also discussed in this post at math.SE

share|improve this answer
    
Nice link thanks, It seems I can't upvote with a low reputation :(. –  ricola86 Oct 5 '11 at 19:10
    
@ricola86: I upvoted for you. Oops, now I can't upvote for myself! :-) –  robjohn Oct 5 '11 at 22:22

I remember solving SPOJ MARBLES which is actually finding $\binom{n}{k}$,constraints there are also similar to this problem in hand.

Last January this same problem (with much more difficult constraints) features in Codechef's January cookfoff.You may like to check the editorial which explains the algorithm along with the implementation.

share|improve this answer
    
This is exactly what I was looking for, thanks alot. Funnily enough, it's a codechef problem I'm working on. –  ricola86 Oct 5 '11 at 19:11
    
@ricola86:Aha,glad to help!:-)I didn't practise in codechef anymore,but I guess you are not asking help for any current problem-set?! ;-) –  Quixotic Oct 5 '11 at 19:16
    
errmm no, I wouldnt dream of it. –  ricola86 Oct 5 '11 at 19:24
    
@ricola86:Alright! :) –  Quixotic Oct 5 '11 at 19:27

In terms of factorials, probably not.

Use the recurrence ${n \choose k} = {n \choose k-1} + {n-1 \choose k-1}$ and just work mod $10^6$.

Alternatively you can work mod $2^6$ and mod $5^6$ and combine the two results using the Chinese Remainder Theorem. There seem to be interesting patterns in the binomial coefficients mod prime powers but I don't know if there are actually formulas. This is probably more trouble than it's worth, though.

share|improve this answer

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.