#
30 Mar 2017
Combinatoric selections

## Project Euler.

#### Problem 53 (solved in Python language).

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, 5C3 = 10.

In general, nCr = n!/r!(n-r)! ,where r <= n, n! = nx(n-1)x…x3x2x1, and 0! = 1.

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

How many, not necessarily distinct, values of nCr, for 1 <= n <= 100, are greater than one-million?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | fact_c = { 0: 1, 1: 1 } def fact_rec(n): return fact_c.has_key(n) and fact_c[ n ] or fact_c.setdefault(n, n * fact_rec(n-1)) def fact_it(n): p = 1 for i in range(1, n + 1): p = p * i return p def comb(n, r): return (fact_rec(n) / (fact_rec(r) * fact_rec(n - r))) answer = len([(x,y) for x in range(1, 100+1) for y in range(x) if comb(x,y) > 1000000]) print answer |