Problem 15: Lattice Paths

Mathematical Development

Definitions

Definition 1. A monotone lattice path from $(0,0)$ to $(m,n)$ is a sequence of $m + n$ unit steps, each either $R = (+1,0)$ or $D = (0,+1)$, such that exactly $m$ steps are $R$ and exactly $n$ steps are $D$.

Definition 2. Let $P(i,j)$ denote the number of monotone lattice paths from $(0,0)$ to $(i,j)$.

Theorems

Theorem 1 (Closed-form path count). The number of monotone lattice paths from $(0,0)$ to $(m,n)$ is

Proof. A path is a binary string of length $m + n$ over the alphabet $\{R, D\}$ containing exactly $m$ copies of $R$. The path is uniquely determined by specifying the positions of the $m$ right-steps among the $m + n$ total steps. The number of ways to choose these positions is $\binom{m+n}{m}$. $\square$

Theorem 2 (Pascal recurrence). The function $P$ satisfies:

Proof. Boundary conditions: There is exactly one path from $(0,0)$ to $(i,0)$ (all $R$-steps) and one path to $(0,j)$ (all $D$-steps).

Recurrence: Every path to $(i,j)$ with $i,j \ge 1$ takes its last step from either $(i-1,j)$ (a right-step) or $(i,j-1)$ (a down-step). These two sets of paths are disjoint and exhaustive, so $P(i,j) = P(i-1,j) + P(i,j-1)$. $\square$

Lemma 1 (Equivalence with Pascal’s triangle). $P(i,j) = \binom{i+j}{i}$ for all $i,j \ge 0$.

Proof. By strong induction on $i + j$. The base case $i + j = 0$ gives $P(0,0) = 1 = \binom{0}{0}$. For boundary cases, $P(i,0) = 1 = \binom{i}{i}$ and $P(0,j) = 1 = \binom{j}{0}$. For $i,j \ge 1$, by the inductive hypothesis and Theorem 2:

where the last equality is Pascal’s identity: $\binom{n-1}{k-1} + \binom{n-1}{k} = \binom{n}{k}$. $\square$

Theorem 3 (Exact evaluation via telescoping product). The binomial coefficient $\binom{2n}{n}$ can be computed as

Moreover, the partial products $\prod_{k=1}^{j} \frac{n+k}{k} = \binom{n+j}{j}$ are integers for all $1 \le j \le n$.

Proof. We have

For integrality of partial products: $\prod_{k=1}^{j} \frac{n+k}{k} = \frac{(n+1)(n+2)\cdots(n+j)}{j!} = \binom{n+j}{j}$, which is an integer since it counts the number of $j$-element subsets of an $(n+j)$-element set. $\square$

Corollary 1. The multiplicative formula computes $\binom{2n}{n}$ using only integer arithmetic (no fractions), since each intermediate quotient $\text{result} \cdot (n+k) / k$ is exact.

Proof. At step $k$, the running product equals $\binom{n+k}{k} \cdot \frac{(n+k-1)!}{(n+k-1)!}$… more directly: after multiplying by $(n+k)$ and dividing by $k$, the result equals $\binom{n+k}{k}$, which is an integer by Theorem 3. $\square$

Numerical Evaluation

Editorial

We compute the central binomial coefficient multiplicatively instead of expanding full factorials. The loop traverses $k = 1, \ldots, n$ and multiplies the accumulator by $(n+k)/k$ at each step, which stays integral by the binomial-coefficient derivation. This is sufficient because the resulting product is exactly $\binom{2n}{n}$, the number of lattice paths.

Correctness. By Theorem 3, this computes $\prod_{k=1}^{n} \frac{n+k}{k} = \binom{2n}{n}$. By Corollary 1, all divisions are exact.

Pseudocode

Algorithm: Central Binomial Coefficient by Multiplicative Update
Require: An integer n ≥ 0.
Ensure: The number of lattice paths through an n x n grid.
1: Initialize P ← 1.
2: For each k in {1, 2, ..., n} do:
3:     Update P ← P · (n + k) / k.
4: Return P.

Complexity Analysis

Proposition. The multiplicative formula runs in $O(n)$ time and $O(1)$ auxiliary space (assuming $O(1)$-cost arithmetic on integers of size $O(\log \binom{2n}{n}) = O(n)$ bits).

Proof. The loop executes $n$ iterations, each performing one multiplication and one division. The result $\binom{2n}{n}$ has $\Theta(n)$ bits by Stirling’s approximation:

If arbitrary-precision arithmetic is used, each multiplication costs $O(n)$ bit operations, giving $O(n^2)$ total. With machine-word arithmetic (valid for $n = 20$ since $\binom{40}{20} \approx 1.38 \times 10^{11} < 2^{63}$), the cost is $O(n)$. $\square$

Remark. The dynamic programming approach (Theorem 2) requires $O(n^2)$ time and $O(n)$ space (using row-by-row computation).

Answer

#include <bits/stdc++.h>
using namespace std;

int main() {
    // Compute C(40, 20) via the telescoping product (Theorem 3).
    // Each intermediate result * (20+k) / k is exact (Corollary 1).
    long long result = 1;
    for (int k = 1; k <= 20; k++)
        result = result * (20 + k) / k;
    cout << result << endl;
    return 0;
}

"""Project Euler Problem 15: Lattice Paths"""


def solve():

    from math import comb

    return comb(40, 20)


answer = solve()
assert answer == 137846528820
print(answer)