Fast calculation of binomial coefficients

mickfrancis · 2016-08-15, 09:31

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

science_man_88 · 2016-08-15, 12:05

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!!!

mickfrancis · 2016-08-15, 12:23

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?

science_man_88 · 2016-08-15, 12:31

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.

mickfrancis · 2016-08-15, 13:08

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

2016-08-15, 09:31	#1
mickfrancis Apr 2014 Marlow, UK 70₈ 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

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Polynomial Coefficients Integer Sets	carpetpool	carpetpool	1	2017-02-22 08:37
Do normal adults give themselves an allowance? (...to fast or not to fast - there is no question!)	jasong	jasong	35	2016-12-11 00:57
Binomial Primes	Lee Yiyuan	Miscellaneous Math	31	2012-05-06 17:44
Recovering Fourier coefficients of modular forms	Robert Holmes	Math	2	2010-09-22 22:10
No Notice- Binomial Coefficients, Pascal's triangle	Vijay	Miscellaneous Math	5	2005-04-09 20:36