Problem 53: 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, $(\binom{5}{3}) = 10$ .

In general, $(\binom{n}{r}) = \frac{n!}{r! (n - r)!}$ , where $r \leq 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: $(\binom{23}{10}) = 1144066$ .

How many, not necessarily distinct, values of $(\binom{n}{r})$ for $1 \leq n \leq 100$ , are greater than one-million?

Solution

The binomial coefficients with fixed $n$ form the $(n + 1)$ -st row of Pascal's triangle. It can be seen that $(\binom{n}{r}) = (\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 $(\binom{n}{k_{n}})$ is greater than one million, then all of $(\binom{n}{k_{n} + 1}), (\binom{n}{k_{n} + 2}), \dots, (\binom{n}{n - k_{n}})$ are greater than one million, for a total of $n - 2 k_{n} + 1$ values. The problem then reduces to finding $k_{n}$ for all $n \geq 23$ .

Pascal's rule states that $(\binom{n - 1}{k}) + (\binom{n - 1}{k - 1}) = (\binom{n}{k})$ ; and so if $(\binom{n - 1}{k})$ is greater than one million, then so is $(\binom{n}{k})$ . 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 $(\binom{n + 1}{k}) = \frac{n + 1}{n - k + 1} (\binom{n}{k})$ and $(\binom{n}{k - 1}) = \frac{k}{n - k + 1} (\binom{n}{k})$ .

Python Code

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

Previous Problem Next Problem

Back to Project Euler