Detailed mathematical approach

Problem Summary

The problem asks for the number of shortest routes from the upper-left corner of a \(20\times 20\) grid to the lower-right corner when every move is restricted to one step right or one step down. Brute-force enumeration would mean generating every admissible route, but the geometry of the grid makes a closed-form count possible.

More generally, for an \(n\times n\) grid the question is to count monotone lattice paths from \((0,0)\) to \((n,n)\). In the Project Euler instance \(n=20\), so the target quantity is \(\binom{40}{20}\).

Mathematical Approach

The key observation is that every shortest path has the same length and the same multiset of moves. Once a path is encoded as an ordering problem, the answer becomes a binomial coefficient, and the implementations can evaluate that coefficient exactly without ever forming huge factorials.

Every shortest path uses the same moves

To go from \((0,0)\) to \((n,n)\), the horizontal coordinate must increase by \(n\) and the vertical coordinate must increase by \(n\). Since the only allowed moves are \(R=(1,0)\) and \(D=(0,1)\), any shortest path contains exactly \(n\) right moves and \(n\) down moves, so its total length is forced to be \(2n\).

There is therefore no choice in how many times each move appears. The only freedom is the order in which those \(2n\) moves are arranged.

Encode the path as a binary word

Once the step counts are fixed, a path is completely determined by choosing which \(n\) of the \(2n\) positions are right moves. The remaining \(n\) positions must then be down moves. This gives a bijection between shortest lattice paths and \(n\)-element subsets of a \(2n\)-element set, so

$L(n)=\binom{2n}{n}=\frac{(2n)!}{n!\,n!}.$

For the Project Euler input,

$L(20)=\binom{40}{20}=137846528820.$

This number is the central binomial coefficient, which is exactly the combinatorial object the code evaluates.

The lattice recurrence gives the same count

If \(P(i,j)\) denotes the number of valid monotone paths from \((0,0)\) to \((i,j)\), then any such path reaching \((i,j)\) must come from either \((i-1,j)\) or \((i,j-1)\). Those two cases are disjoint, so for \(i,j\ge 1\),

$P(i,j)=P(i-1,j)+P(i,j-1),$

with boundary conditions

$P(i,0)=1,\qquad P(0,j)=1.$

This is Pascal's triangle written on the grid. The implementations do not use dynamic programming for the final answer, but this recurrence is the natural invariant behind the combinatorics and a useful way to verify the formula.

Worked example: a \(2\times 2\) grid

For \(n=2\), every shortest path is an ordering of the multiset \(\{R,R,D,D\}\). The six possibilities are \(RRDD\), \(RDRD\), \(RDDR\), \(DRRD\), \(DRDR\), and \(DDRR\), so

$L(2)=\binom{4}{2}=6.$

The recurrence viewpoint agrees: starting with ones along the top edge and left edge, the interior counts become \(2\), \(3\), and finally \(6\) in the lower-right corner. This small case is also used as a checkpoint in the implementations.

The exact multiplicative formula used by the implementations

Computing \((2n)!\) and then dividing by \((n!)^2\) is mathematically correct but numerically clumsy, because the intermediate factorials grow much faster than the final answer. The C++ and Java implementations therefore evaluate a generic binomial coefficient by the product

$\binom{N}{k}=\prod_{i=1}^{k}\frac{N-k+i}{i},$

and then substitute \(N=2n\) and \(k=n\).

After the \(i\)-th update, the running value equals \(\binom{N-k+i}{i}\). That invariant explains why each division by \(i\) is exact: the algorithm never leaves the integers. The generic routine also replaces \(k\) by \(\min(k,N-k)\); in this square-grid problem that symmetry does not change the final loop length, but it is the correct combinatorial simplification in general.

How the Code Works

Shared combinatorial core

The C++, Python, and Java implementations all reduce the problem to evaluating \(\binom{2n}{n}\). None of them enumerates paths, and none of them needs to store a two-dimensional grid. The C++ and Java versions perform the multiplicative update step by step, while the Python version calls the standard library's exact binomial routine.

Language-specific numeric choices

The C++ implementation uses wider intermediate arithmetic during the multiply-then-divide loop and checks that the final value still fits into 64-bit storage before printing it. The Java implementation uses 64-bit signed integers, which are sufficient for the target case \(n=20\). The Python implementation relies on arbitrary-precision integers, so it can compute the same combinatorial quantity without overflow concerns. Small sanity checks such as \(L(1)=2\) and \(L(2)=6\) confirm that the formula has been encoded correctly.

Complexity Analysis

The implemented method performs one multiplicative loop of length \(k\), where \(k=n\) for this problem. That gives \(O(n)\) arithmetic steps and \(O(1)\) extra space in the C++ and Java implementations. For \(n=20\), the calculation is effectively instantaneous.

For comparison, the lattice recurrence would require \(O(n^2)\) time and either \(O(n^2)\) space for a full table or \(O(n)\) space with row compression. The binomial route is superior here because the mathematics has already collapsed the search space to one exact closed form.

Footnotes and References

1. Problem page: Project Euler 15
2. Binomial coefficient: Wikipedia - Binomial coefficient
3. Central binomial coefficient: Wikipedia - Central binomial coefficient
4. Lattice path: Wikipedia - Lattice path
5. Pascal's triangle: Wikipedia - Pascal's triangle
6. Sequence of central binomial coefficients: OEIS A000984