Problem Description

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, ⁿC_r = n! / r!(n−r)!, 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: ²³C₁₀ = 1144066.
How many, not necessarily distinct, values of  ⁿC_r, for 1 ≤ n ≤ 100, are greater than one-million?

Analysis

There is an efficient way to solve this using Pascal’s triangle.

Each row of this triangle is vertically symmetric, so C(n, r) = C(n, n-r) and any C(n, x) for x from r to (n-r) is greater than C(n, r).

If C(n, r) > 10⁶ then C(n, x) for x from r to (n-r) will also > 10⁶, therefore, the number of C(n, r) > 10⁶, is simply (n-r)-r+1 for that row n.

Solution

Runs < 1 second in Python.

from Euler import binomial
limit, maxn, c = 1e6, 100, 0
 
for n in range(23, maxn+1):
  for r in range(2, n/2+1):
    if binomial(n, r) > limit:
      c += n + 1 - 2*r
      break
print "Answer to PE53 = ", c

Comments

• More information on the Euler module can be found on the tools page.
• How many, not necessarily distinct, values of  ⁿC_r, for 1 ≤ n ≤ 1000, are greater than ten-billion? 490,806