How to calculate sum of binomial coefficients efficiently?

general
,
4

Clearly,

\sum_{i=0}^{k/2} \binom{n}{2i} = \sum_{i=0}^{k} \binom{n-1}{i}.

In addition, if n = q_1 p + r_1 and k = q_2 p + r_2 (0 \le r_1, r_2 < p), then by Lucas theorem we have

\begin{aligned} \sum_{i=0}^{k} \binom{n}{i} &= \sum_{j=0}^{q_2-1} \sum_{i=0}^{p-1} \binom{q_1 p + r_1}{jp+i} + \sum_{i=0}^{r_2} \binom{q_1 p +r_1}{q_2p+i} \\ &\equiv \sum_{j=0}^{q_2-1} \binom{q_1}{j} \sum_{i=0}^{p-1} \binom{r_1}{i} + \binom{q_1}{q_2} \sum_{i=0}^{r_2} \binom{r_1}{i} \\ &\equiv 2^{r_1} \sum_{j=0}^{q_2-1} \binom{q_1}{j} + \binom{q_1}{q_2} \sum_{i=0}^{r_2} \binom{r_1}{i} \pmod{p}. \\ \end{aligned}

So, we only need to compute the sum

\sum_{i=0}^{k} \binom{n}{i} \pmod{p},

where 0 \le k \le n < p.

In fact, this summation can be computed in O(\sqrt{p} \log p) time by using FFT/NTT.

Let v := \lfloor\sqrt{k}\rfloor, f_m(x) := \prod_{i=1}^{m}(x+i) and g_m(x) := \sum_{i=1}^{m} \left(\prod_{j=1}^{i-1}(n+1-j-x) \cdot \prod_{j=i}^{m} (x+j)\right). Then,

\sum_{i=0}^{k} \binom{n}{i} = \frac{1}{f_v(0)} \left(g_v(0) + \frac{f_v(n-v)}{f_v(v)} \cdot \left(g_v(v) + \frac{f_v(n-2v)}{f_v(2v)}\cdot\left(g_v(2v) + \cdots \right) \right) \right) + \sum_{i=v^2}^{k} \binom{n}{i}.

So, it suffices to evaluate f_v(iv), f_v(n-(i+1)v) and g_v(iv) for 0 \le i < v in O(\sqrt{k} \log{k}) time. (The last binomial sum can be computed in O(\sqrt{k} + \log{p}) time with those values.)

Firstly, the polynomials f_m(x) and g_m(x) satisfies the following recurrences

\begin{aligned} f_{2m}(x) &= f_m(x) \cdot f_m(x+m)\\ g_{2m}(x) &= g_m(x) \cdot f_m(x+m) + g_m(x+m) \cdot f_m(n-m-x). \\ \end{aligned}

Secondly, by Lagrange interpolation and FFT, we can compute the values f(ai+c) (0 \le i \le \deg{f}) from f(ai+b) (0 \le i \le \deg{f}) in O(\textrm{M}(\deg{f})) time. (see https://specfun.inria.fr/bostan/publications/BoGaSc07.pdf.)

Therefore, we can compute the values f_{2m}(0), \ldots, f_{2m}(2mv) and g_{2m}(0), \cdots, g_{2m}(2mv) from f_{m}(0), \ldots, f_{m}(mv) and g_m(0), \ldots, g_m(mv) in O(m \log m) time. In addition, f_{2m+1}(*) and g_{2m+1}(*) can be computed from f_{2m}(*) and g_{2m}(*) in O(m + \log{p}) time. Thus, we can compute the binomial sum modulo prime in O(\sqrt{p} \log{p}) time.

[Updated]

It takes about 0.13 seconds on ideone to compute

\sum_{i=0}^{10^9} \binom{2 \cdot 10^9}{i} \equiv 1236371654 \pmod{2^{31} - 1}.

(C++ implementation: https://ideone.com/Q3e3Wo)

8 Likes