How to efficiently calculate a row in pascal's triangle?

Question

I'm interested in finding the nth row of pascal triangle (not a specific element but the whole row itself). What would be the most efficient way to do it?

I thought about the conventional way to construct the triangle by summing up the corresponding elements in the row above which would take:

1 + 2 + .. + n = O(n^2) 

Another way could be using the combination formula of a specific element:

c(n, k) = n! / (k!(n-k)!) 

for each element in the row which I guess would take more time the the former method depending on the way to calculate the combination. Any ideas?

Answer 1

>>> def pascal(n): ...   line = [1] ...   for k in range(n): ...     line.append(line[k] * (n-k) / (k+1)) ...   return line ...  >>> pascal(9) [1, 9, 36, 84, 126, 126, 84, 36, 9, 1] 

This uses the following identity:

C(n,k+1) = C(n,k) * (n-k) / (k+1) 

So you can start with C(n,0) = 1 and then calculate the rest of the line using this identity, each time multiplying the previous element by (n-k) / (k+1).

Answer 2

A single row can be calculated as follows:

First compute 1.               -> N choose 0 Then N/1                       -> N choose 1 Then N*(N-1)/1*2               -> N choose 2 Then N*(N-1)*(N-2)/1*2*3       -> N choose 3 ..... 

Notice that you can compute the next value from the previous value, by just multipyling by a single number and then dividing by another number.

This can be done in a single loop. Sample python.

def comb_row(n):    r = 0    num = n    cur = 1    yield cur    while r <= n:       r += 1         cur = (cur* num)/r       yield cur       num -= 1