Python for Bioinformatics: Pascal's Triangle

Thursday, November 11, 2010

Pascal's Triangle

I'm sure you already know about Pascal's triangle. The screenshot above is from an animation in the wikipedia article.

Among other things, Pascal's triangle provides the coefficients for the binomial expansion (p + q)ⁿ. And of course, today we would generate any particular coefficient using the formula for combinations:

C(n,k) = n! / [(n-k)! k!]

So, for example, the 4th element in the expansion for (p + q)⁹ is:

9! / (5! * 4!) =

>>> 9 * 8 * 7 * 6 / (4 * 3 * 2)
126

(0-based indexing).

I'm working my way (slowly) through a wonderful book called Journey Through Genius, and I want to explore one of the chapters which involves Newton, his form of the expansion, and the connection to infinite series and finally an approximation for π.

But, let's start by simply generating the numbers as one would fill out the triangle, but using Python to do the arithmetic.

output:

                             1 
                          1     1 
                       1     2     1 
                    1     3     3     1 
                 1     4     6     4     1 
              1     5     10    10    5     1 
           1     6     15    20    15    6     1 
        1     7     21    35    35    21    7     1 
     1     8     28    56    70    56    28    8     1 
  1     9     36    84   126   126    84    36    9     1

code listing:

N = 10
L = [[1]]
for i in range(1,N): 
    sL = L[-1]
    R = range(len(sL)-1)
    pL = [sum(sL[i:i+2]) for i in R]
    L.append([1] + pL + [1])

sp = ' '
j = len(str(max(L[-1])))
for i,sL in enumerate(L):
    print sp*(N-i-1)*j,
    sL = [str(e).center(j) for e in sL]
    print (sp*j).join(sL)
print