How to efficiently calculate a row in pascal's triangle?
algorithm, binomial-coefficients, combinations, pascals-triangle
Solution
>>> 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)`.
Problem
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?