Coefficients of Binomial Expansion

Given a binomial of the form (x+y)ⁿ, where n >=1, write a function coefficients(int n) that prints out the coefficients of the binomial expansion in O(n) time. For example, calling coefficients(10) prints:

1 10 45 120 210 252 210 120 45 10 1

Solution

We start with the binomial theorem, which tells us that the coefficient for each term k (1 <= k <= n) is n!/(k!(n-k)!). Using coefficients(10) as an example, we can see that the term in position #1 has degree 10 and coefficient 1. The coefficient of the next term (#2 with degree 9) is:

  10!      10
------- = ----
 1!9!      1

The next term (#3 with degree 8) is:

  10!     10*9
------ = ------
 2!8!      1*2

And the next term (#4 with degree 7) is:

  10!     10*9*8
------ = --------
 3!7!      1*2*3

Notice the pattern unfolding: the coefficient for the term in position k is the ((coefficient*degree)/position) of the term in position k-1. So we can implement this quite efficiently:

public void coefficients(int n)
{
  int coeff = 1;
  int degree = n;
  int position = 1;
  do
  {
    System.out.print( coeff + " " );
    coeff = ( coeff * degree-- ) / position;
  } while ( position++ <= n );
  System.out.println();
}

Of course, this can be made even more efficient by exploiting the symmetry of the coefficients, but as it stands, this implementation runs in O(n) time.