Combinatoric Selections

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?

First, we need to understand it’s not necessary to iterate through every possible combination of n and r for 1 ≤ n ≤ 100.
We know that the values of the binomial coefficient increase as we approach the middle of the row (i.e., as r approaches n/2) and then decrease again. This makes the binomial coefficient symmetric with respect to r. More formally, if n ≥ 2r, then C(n,r) ≤ C(n,r-1).

This fact can help us find the value of r for a given n such that C(n, r) > 1 million. We can start from r = 1 and keep increasing until we reach a value > 1 million, and we know that all the subsequent values till r = n – r will also be greater than one-million.

Next, we need to remember that we don’t need to calculate the binomial coefficients exactly. We’re only interested to know if they’re greater than one-million. Therefore, when multiplying, we can stop as soon as the product exceeds one-million.

So now comes the code part of the solution. Although we’re doing it in Python, the logic will be similar in other programming languages.

“`python
# Define a function to compute the combination
def nCr(n, r):
result = 1
for i in range(1, r + 1):
result = result * (n – i + 1) // i
if result > 1000000: # If the result is already greater than one million, we return
return result
return result

# Initialize total to 0
total = 0

# Loop through all possible values of n
for n in range(1, 101):

# Loop through all possible values of r
for r in range(1, n + 1):

# If the combination of n and r is more than 1 million, we add to the total
if nCr(n, r) > 1000000:
total += (n-2*r+1) #we add the symmetric count and break the loop as all further will be smaller
break

print(total)
“`

The output of this script should be the total number of not necessarily distinct values of C(n, r) for 1 ≤ n ≤ 100 which are greater than one-million. In our case, the output is 4075.

More Answers: