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 ${}^5C_3 = 10$.
In general,
$\displaystyle {}^nC_r = \frac{n!}{r!(n−r)!}$, where $r \le n$, $n! = n\times(n−1)×\cdots×3×2×1$, and $0! = 1$. It is not until $n = 23$, that a value exceeds one million: ${}^{23}C_{10} = 1144066$.
How many, not necessarily distinct, values of ${}^nC_r$, for $1 \le n \le 100$, are greater than one million?
In [2]:
n, r, C = 23, 9, 817190
total = 4
while n < 100:
n += 1
C = (C * n) // (n - r)
while C <= 1000000:
C1 = C * (n-r) // (r+1)
if C1 <= 1000000:
C = C1
else:
break
while C > 1000000:
C = (C * r) // (n - r + 1)
r -= 1
total += (n - 2*r - 1)
print(total)
Explanation: For each n we find the value of r that satisfies C(n, r) <= 10^6 < C(n, r+1). We search through Pascal's triangle moving one step at a time.