Problem statement

Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

Thoughts

This could be approached recursively, as the first descision whether to go right or down can always reduce the situation to the sum of two smaller grids. The problem can be recursively reduced to $2 \times 2$ and built up from there.

As I was working this out on a piece of paper though, it seemed obvious that there should be a formula for this. After a little longer than I like to admit I realised this just needs an application of the binomial coefficient! For an $n \times n$ grid, there'll be $2n$ total moves ($n$ right and $n$ down). We need to choose which $n$ are to the right, and the rest can only be down. The solution is just $2n \choose n$.

Diagram showing problem reduction of 3 by 3 grid

Solution

Implement the formula ${n \choose k} = \frac{n!}{k! (n-k)!}$ and pass in 20.

Where it becomes sort of a problem is in how large the numbers get. We can keep the number "relatively low" by realising that $(n - k)!$ is a factor of $n!$, so we just need to multiply $40 \times 39 \times 38 \times \ldots \times 21$ and divide by $k!$, but this number is still no joke; it won't fit inside an unsigned long long, so will require bespoke handling.

We can take advantage of our knowledge that $n = 2k$ to deduce that $k | n(n - 1)$, and that $(k - 1) | (n - 2)(n - 3)$. This allows us to interleave the required multiplication and division, without needing to compute two ridiculous numbers just for the sake of dividing them again.

#include <stdio.h>

int main()
{
	const int num = 20;
	unsigned long n = 2 * num, k = num, res = 1;

	/* We only need to multiply from n down to k + 1, as the (k - 1)! is a factor of n!;
	 * use `num` as the threshold variable, as we modify `k` along the way. */
	for (; n > num; n--) {
		res *= n;
		if (n % 2 == 0)
			res /= k--;
	}

	while (k > 1)
		res /= k--;

	printf("%lu\n", res);
}