Fastest way to generate binomial coefficients

Question

I need to calculate combinations for a number.

What is the fastest way to calculate nCp where n>>p?

I need a fast way to generate binomial coefficients for an polynomial equation and I need to get the coefficient of all the terms and store it in an array.

(a+b)^n = a^n + nC1 a^(n-1) * b + nC2 a^(n-2) * ............ +nC(n-1) a * b^(n-1) + b^n

What is the most efficient way to calculate nCp ??

Answer 1

You cau use dynamic programming in order to generate binomial coefficients

You can create an array and than use O(N^2) loop to fill it

C[n, k] = C[n-1, k-1] + C[n-1, k]; 

where

C[1, 1] = C[n, n] = 1 

After that in your program you can get the C(n, k) value just looking at your 2D array at [n, k] indices

UPDATE smth like that

for (int k = 1; k <= K; k++) C[0][k] = 0; for (int n = 0; n <= N; n++) C[n][0] = 1;  for (int n = 1; n <= N; n++)    for (int k = 1; k <= K; k++)       C[n][k] = C[n-1][k-1] + C[n-1][k]; 

where the N, K - maximum values of your n, k

Answer 2

If you need to compute them for all n, Ribtoks's answer is probably the best. For a single n, you're better off doing like this:

C[0] = 1 for (int k = 0; k < n; ++ k)     C[k+1] = (C[k] * (n-k)) / (k+1) 

The division is exact, if done after the multiplication.

And beware of overflowing with C[k] * (n-k) : use large enough integers.