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 \le n$ , $n! = n \times (n-1) \times … \times 3 \times 2 \times 1$ and $0! = 1$

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

How many, not necessarily distinct, values of $\displaystyle \binom n r$ for $1 \le n \le 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