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