#53 - Combinatoric selections

There are exactly ten ways of selecting three from five, 12345: 123,  124,  125,  134,  135,  145,  234,  235,  245,  and 345123,\,\,124,\,\,125,\,\,134,\,\,135,\,\,145,\,\,234,\,\,235,\,\,245,\,\,\text{and }345

In combinatorics, we use the notation 5C3=10_5 C_3=10.

In general nCr=n!r!(nr)!_nC_r=\frac{n!}{r!(n-r)!}, where rn,n!=n×(n1)××3×2×1r\leq n, n!=n\times(n-1)\times\dots\times 3\times 2\times 1, and 0!=10!=1.

How many, not necessarily distinct, values of nCr_nC_r for 1n1001\leq n\leq 100, are greater than one-million?


Notice that the formula for nCr_nC_r has three factorials. Recomputing each of these factorials each time will be time-consuming and inefficient. Instead, we can find n!n! for all 0n1000\leq n\leq 100, and grab the values we need for each computation. Python’s math package has a quick factorial function we can use:

# file: "problem053.py"
factorials = [math.factorial(i) for i in range(0, 101)]
count = 0
for n in range(23, 101):
    for r in range(n + 1):
        if factorials[n] / (factorials[r] * factorials[n - r]) > 1000000:
            count += 1
print(count)

Running this short loop results in,

4075
0.0038949089640585117 seconds.

Thus, there are 4075 values that are greater than one million.

Bonus

We can actually solve this problem without computing a single factorial! We can use Pascal’s triangle to find nCr_nC_r, as the rows of the triangle are the values of nCr_nC_r. Pascal’s triangle is constructed in the following manner:

  1. The first row is 11.
  2. The second row is 111\quad 1.
  3. Each row after the second is formed by placing two ones at the ends, while the middle values are calculated by adding the two numbers above. For example, the first 5 rows are shown below.
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

If the rows are numbered starting from 0, and the elements in the row are also numbered starting from 0, the rthr^\text{th} number in the nthn^\text{th} row is exactly nCr_nC_r. Using the generative nature of Pascal’s triangle, we can continuously generate each row until the 100th row, and count the numbers which are greater than one-million.

currRow = [1, 1]
count = 0
for n in range(2, 101):
    nextRow = [0] * (n + 1)
    nextRow[0] = 1
    nextRow[-1] = 1
    # Make the next row
    for i in range(len(currRow) - 1):
        nextRow[i+1] = currRow[i] + currRow[i+1]
    # Count how many are bigger than 1 million
    count += len([x for x in nextRow if x > 1000000])
    currRow = nextRow
print(count)

We have to start from the beginning in order to see what the 23rd row is. Regardless, the output of is the same, although slightly faster.

4075
0.0015237512804923096 seconds.
0