Problem 53 - How many values of C(n,r), for 1 ≤ n ≤ 100, exceed one-million?

링크

There are exactly ten ways of selecting three from five, 12345:

123, 124, 125, 134, 135, 145, 234, 235, 245, and 345

In combinatorics, we use the notation, ⁵C₃ = 10.

In general,

nCr =

n! r!(nr)!

,where r n, n! = n(n1)...321, and 0! = 1.

It is not until n = 23, that a value exceeds one-million: ²³C₁₀ = 1144066.

How many, not necessarily distinct, values of  ⁿC_r, for 1 n 100, are greater than one-million?

python

def pascalTriangle(m): pascal = [[0] * (m+1) for i in range(m+1)] pascal[0][0] = 1 for n in range(1, m+1): pascal[n][0] = 1 for r in range(1, n+1): pascal[n][r] = pascal[n-1][r-1] + pascal[n-1][r] return pascal pascal = pascalTriangle(100) print sum([1 for n in range(101) for r in range(101) if pascal[n][r] > 1000000])