"""
 choose.py

 Calculate C(n,k) = the number of ways to choose n things k at a time.

 This is a famous combinatorics quantity.

 I) It shows up in the binomial expansion:

    (x + y)**n

    sum over i   [ C(n,i) x**i y**(n-i) ]

    i.e. (x+y)**10 = 1 x**10 + 10 x**9 y + 45 x**8 x**2 + ...
                     C(10,0)   C(10,1)     C(10,2)
 

 II) There is a famous explicit formula:

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

 III) The numbers fit into pascal's triangle

              1               C(0,0)
            1   1             C(1,0)  C(1,1)
          1   2   1           C(2,0)  C(2,1)  C(2,2)
        1   3   3   1         C(3,0)  C(3,1)  C(3,2)  C(3,3)
      1   4   6   4   1       

     ... which means there's a recursion relation :

      C(n, 0) = C(n, n) = 1                 
      C(n, k) = C(n-1, k) + C(n-1, k-1)

 So ... write function to calculuate this.

 Idea:

   "dynamic programming"

     If we have a way to do smaller versions,
     then use recursion to make the problem smaller
     but don't calculate anything twice.

     Equivalently, if we can see the order to evaluate,
     can use an explicit loop.

 $ time python choose.py 
 C(100, 80) = 535983370403809682970 
 len(saved_c) = 1600 

 real	0m0.036s
 user	0m0.023s
 sys	0m0.010s

 Jim Mahoney | 
"""

# Saved values of c[(n,k)]
saved_c = {}

def c(n,k):
    if saved_c.has_key((n,k)):            # memoization
        return saved_c[(n,k)]
    elif k == 0 or k == n:                # boundary condition
        return 1
    else:
        result = c(n-1, k) + c(n-1, k-1)    # recursion
        saved_c[(n,k)] = result
        return result

def main():
    print "C(100, 80) = %i " % c(100, 80)
    print "len(saved_c) = %i " % len(saved_c)

main()