mersenneforum.org > Math Fast calculation of binomial coefficients
 Register FAQ Search Today's Posts Mark Forums Read

 2016-08-15, 09:31 #1 mickfrancis   Apr 2014 Marlow, UK 23×7 Posts Fast calculation of binomial coefficients If I know ${n} \choose {p}$ (mod m), is there a way of calculating ${n+p} \choose {2p}$ (mod m) with time complexity better than $\mathcal{O}(p)$? m <= n p <= n/2 Last fiddled with by mickfrancis on 2016-08-15 at 09:44 Reason: (mod n) should be (mod m), also added constraints
2016-08-15, 12:05   #2
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

838410 Posts

Quote:
 Originally Posted by mickfrancis If I know ${n} \choose {p}$ (mod m), is there a way of calculating ${n+p} \choose {2p}$ (mod m) with time complexity better than $\mathcal{O}(p)$? m <= n p <= n/2
I don't know but is their ratio ((n+p)!*(2p)!)/(n!*p!) easily calculated mod m ? if so it's a modular multiply away. doh that ratio ( if I've done the math correctly to get it is (2p)! * (n+p choose p) ) okay I see an error I did I forgot to flip one of the fractions in their ratio when multiplying. (n+p)!/(((n+p)-(2p))!2p!) /( n!/((n-p)!p!)) = (n+p)!/(((n-p)!2p!) /( n!/((n-p)!p!)) =((n+p)!/(2p!)) /( n!/(p!)) = ((n+p)!p!)/((2p)!n!) doh!!!

Last fiddled with by science_man_88 on 2016-08-15 at 12:18

2016-08-15, 12:23   #3
mickfrancis

Apr 2014
Marlow, UK

23×7 Posts

Quote:
 Originally Posted by science_man_88 I don't know but is their ratio ((n+p)!*(2p)!)/(n!*p!) easily calculated mod m ? if so it's a modular multiply away. doh that ratio ( if I've done the math correctly to get it is (2p)! * (n+p choose p)
Good thought. I think the p and 2p are transposed in that ratio? I get: ((n+p)! * p!)/((2p)! * n!), which can be written as $\frac{\displaystyle\prod_{i=1}^{p} {(n+i)}} {\displaystyle\prod_{i=1}^{p} {(p+i)}}$, and I can't see how to calculate this in better than $\mathcal{O}(p)$ - maybe there is a closed form for this?

2016-08-15, 12:31   #4
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by mickfrancis Good thought. I think the p and 2p are transposed in that ratio? I get: ((n+p)! * p!)/((2p)! * n!), which can be written as $\frac{\displaystyle\prod_{i=1}^{p} {(n+i)}} {\displaystyle\prod_{i=1}^{p} {(p+i)}}$, and I can't see how to calculate this in better than $\mathcal{O}(p)$ - maybe there is a closed form for this?

I think there's a simpler form of that product division as in each case of i there's n/(p+i) +(1/(p/i+1)) no ? and this can be put into fractional form of ((n+1)*(p+i))/((p^2+p*i)/i+(p+i)) I think. doh I'm an idiot not sure why I thought it could be done like that for some reason.

Last fiddled with by science_man_88 on 2016-08-15 at 12:43

2016-08-15, 13:08   #5
mickfrancis

Apr 2014
Marlow, UK

23×7 Posts

Quote:
 Originally Posted by science_man_88 I think there's a simpler form of that product division as in each case of i there's n/(p+i) +(1/(p/i+1)) no ? and this can be put into fractional form of ((n+1)*(p+i))/((p^2+p*i)/i+(p+i)) I think. doh I'm an idiot not sure why I thought it could be done like that for some reason.
It can be rewritten as $\displaystyle\prod_{i=1}^{p} {(1 + \frac{n-p}{i+p})}$, I think, but I'm not sure this helps...

 Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool carpetpool 1 2017-02-22 08:37 jasong jasong 35 2016-12-11 00:57 Lee Yiyuan Miscellaneous Math 31 2012-05-06 17:44 Robert Holmes Math 2 2010-09-22 22:10 Vijay Miscellaneous Math 5 2005-04-09 20:36

All times are UTC. The time now is 14:55.

Tue Dec 1 14:55:33 UTC 2020 up 82 days, 12:06, 2 users, load averages: 1.69, 1.89, 1.94

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.