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, \(\displaystyle \binom 5 3 = 10\).
In general, \(\displaystyle \binom n r = \dfrac{n!}{r!(n-r)!}\), 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: \(\displaystyle \binom {23} {10} = 1144066\).
How many, not necessarily distinct, values of \(\displaystyle \binom n r\) for \(1 \le n \le 100\), are greater than one-million?
The binomial coefficients with fixed \(n\) form the \((n+1)\)-st row of Pascal's triangle. It can be seen that \(\displaystyle \binom n r = \displaystyle \binom n{n-r}\), and that the coefficients in a row strictly increase until the midpoint. Therefore, if \(k_n\) is the minimum number such that \(\displaystyle \binom n{k_n}\) is greater than one million, then all of \(\displaystyle \binom n{k_n+1}, \binom n{k_n+2}, \ldots, \binom n{n-k_n}\) are greater than one million, for a total of \(n - 2k_n + 1\) values. The problem then reduces to finding \(k_n\) for all \(n \geq 23\).
Pascal's rule states that \(\displaystyle \binom {n-1}k + \binom{n-1}{k-1} = \binom nk\); and so if \(\displaystyle \binom {n-1}k\) is greater than one million, then so is \(\displaystyle \binom nk\). Thus our starting point for \(k_n\) is \(k_{n-1}\), and we decrease \(k_n\) until doing so would put the binomial coefficient below one million.
To avoid having to compute the binomial coefficient from scratch every time, my program uses the helpful identities \(\displaystyle \binom {n+1}k = \frac {n+1}{n-k+1} \binom nk\) and \(\displaystyle \binom n{k-1} = \frac k{n-k+1} \binom nk\).
def p53():
binom = 1144066
k = 10
res = 0
for n in range(23, 101):
while binom * k // (n-k+1) > 10**6:
binom = binom * k // (n-k+1)
k -= 1
res += n - 2*k + 1
binom = binom * (n+1) // (n-k+1)
return res