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

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?

Solution 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).

Solution 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

Solution 3:

The most efficient approach would be:

std::vector<int> pascal_row(int n){
    std::vector<int> row(n+1);
    row[0] = 1; //First element is always 1
    for(int i=1; i<n/2+1; i++){ //Progress up, until reaching the middle value
        row[i] = row[i-1] * (n-i+1)/i;
    }
    for(int i=n/2+1; i<=n; i++){ //Copy the inverse of the first part
        row[i] = row[n-i];
    }
    return row;
}

Solution 4:

here is a fast example implemented in go-lang that calculates from the outer edges of a row and works it's way to the middle assigning two values with a single calculation...

package main

import "fmt"

func calcRow(n int) []int {
    // row always has n + 1 elements
    row := make( []int, n + 1, n + 1 )

    // set the edges
    row[0], row[n] = 1, 1

    // calculate values for the next n-1 columns
    for i := 0; i < int(n / 2) ; i++ {
        x := row[ i ] * (n - i) / (i + 1)

        row[ i + 1 ], row[ n - 1 - i ] = x, x
    }

    return row
}

func main() {
    for n := 0; n < 20; n++ {
        fmt.Printf("n = %d, row = %v\n", n, calcRow( n ))
    }
}

the output for 20 iterations takes about 1/4 millisecond to run...

n = 0, row = [1]
n = 1, row = [1 1]
n = 2, row = [1 2 1]
n = 3, row = [1 3 3 1]
n = 4, row = [1 4 6 4 1]
n = 5, row = [1 5 10 10 5 1]
n = 6, row = [1 6 15 20 15 6 1]
n = 7, row = [1 7 21 35 35 21 7 1]
n = 8, row = [1 8 28 56 70 56 28 8 1]
n = 9, row = [1 9 36 84 126 126 84 36 9 1]
n = 10, row = [1 10 45 120 210 252 210 120 45 10 1]
n = 11, row = [1 11 55 165 330 462 462 330 165 55 11 1]
n = 12, row = [1 12 66 220 495 792 924 792 495 220 66 12 1]
n = 13, row = [1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1]
n = 14, row = [1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1]
n = 15, row = [1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1]
n = 16, row = [1 16 120 560 1820 4368 8008 11440 12870 11440 8008 4368 1820 560 120 16 1]
n = 17, row = [1 17 136 680 2380 6188 12376 19448 24310 24310 19448 12376 6188 2380 680 136 17 1]
n = 18, row = [1 18 153 816 3060 8568 18564 31824 43758 48620 43758 31824 18564 8568 3060 816 153 18 1]
n = 19, row = [1 19 171 969 3876 11628 27132 50388 75582 92378 92378 75582 50388 27132 11628 3876 969 171 19 1]