Problem 53 : Combinatoric selections

Problem Statement

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,

In general,

where r≤n , n!=n×(n−1)×…×3×2×1 and 0!=1

It is not until n=23, that a value exceeds one-million:

How many, not necessarily distinct, values of (nr) for 1≤n≤100 are greater than one-million?

Solution

dic=[1]

for i in range(1,101):
    val =dic[-1]*i
    dic.append(val)


def choose(n,r):
    sol = dic[n]//(dic[n-r]*dic[r])
    return sol

def func(maxi, valu): 
    count = 0
    for i in range(2,maxi+1):
        for j in range(1,i+1):
            val = choose(i,j)
            if  val>valu:
                count+=1         
    return count


print(func(100, 10**6))

Ouputs

4075