Problem 53

Problem 53

26 September 2003

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?

找到第一个r使得ⁿC_r > 1000000, 则对于n其大于1000000的数量为i - 2*j + 1

def fun53():
    f = [1]*101
    for i in range(2, 101):
        f[i] = i*f[i-1]
    #print f
    count = 0
    for i in range(23, 101):
        for j in range(0, i/2+1):
            t = f[i]/(f[j]*f[i-j])
            if t > 1000000:
                #print i, j
                count += i - 2*j + 1
                """
                if i%2 == 0:
                    count += ((i+1)/2 - j)*2
                else:
                    count += (i/2 -j)*2 + 1
                """
                break
    return count

answer 4075
time:0.0