Problem 884: Lattice Walks with Barriers

Mathematical Analysis

Theorem 1 (Unrestricted Lattice Paths)

The number of paths from $(0,0)$ to $(m,n)$ using $m$ right steps and $n$ up steps is $\binom{m+n}{m}$.

Proof. Each path is a sequence of $m+n$ steps, choosing $m$ positions for right steps. $\square$

Theorem 2 (Reflection Principle / Andre’s Reflection)

The number of paths from $(0,0)$ to $(m,n)$ that do not touch the line $y = x + 1$ (staying weakly below $y = x$) is:

This is the ballot problem formula. When $m = n$, this gives the Catalan number $C_n = \frac{1}{n+1}\binom{2n}{n}$.

Proof. By reflection across $y = x + 1$: paths touching the barrier biject with unrestricted paths from $(-1, 1)$ to $(m, n)$, counted by $\binom{m+n}{m+1}$. $\square$

Theorem 3 (LGV Lemma)

Let $A = \{a_1, \ldots, a_k\}$ be source points and $B = \{b_1, \ldots, b_k\}$ be destination points. Let $e(a_i, b_j)$ be the number of paths from $a_i$ to $b_j$. Then the number of $k$-tuples of non-intersecting paths (path $i$ goes from $a_i$ to $b_i$) is:

Proof. Expand the determinant as $\sum_\sigma \text{sgn}(\sigma) \prod_i e(a_i, b_{\sigma(i)})$. By a sign-reversing involution, all terms with intersecting paths cancel, leaving only non-intersecting configurations. $\square$

Concrete Numerical Examples

Catalan Numbers (Dyck Paths)

Paths from $(0,0)$ to $(n,n)$ staying below $y = x$:

LGV Example: Two Non-Intersecting Paths

Sources: $a_1 = (0,0)$, $a_2 = (0,1)$. Destinations: $b_1 = (3,2)$, $b_2 = (3,3)$.

Verification Table (Ballot Problem)

Catalan Number Interpretations

$C_n$ counts many combinatorial structures:

1. Dyck paths from $(0,0)$ to $(2n,0)$
2. Valid sequences of $n$ pairs of parentheses
3. Triangulations of a convex $(n+2)$-gon
4. Full binary trees with $n+1$ leaves
5. Non-crossing partitions of $\{1, \ldots, n\}$

Generating Function

satisfying $C(x) = 1 + x \cdot C(x)^2$.

Asymptotic

Complexity Analysis

Answer

/*
 * Problem 884: Lattice Walks with Barriers
 * Catalan numbers, ballot problem, LGV lemma.
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll comb_val(int n, int r) {
    if (r < 0 || r > n) return 0;
    if (r > n - r) r = n - r;
    ll result = 1;
    for (int i = 0; i < r; i++)
        result = result * (n - i) / (i + 1);
    return result;
}

ll catalan(int n) { return comb_val(2*n, n) / (n + 1); }

ll ballot(int m, int n) {
    if (n > m) return 0;
    return comb_val(m + n, m) - comb_val(m + n, m + 1);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cout << "=== Catalan Numbers ===" << endl;
    for (int n = 0; n <= 15; n++)
        cout << "C_" << n << " = " << catalan(n) << endl;

    cout << "\n=== Ballot Problem ===" << endl;
    for (auto [m, n] : vector<pair<int,int>>{{3,3},{4,4},{5,5},{4,2},{6,3}}) {
        cout << "ballot(" << m << "," << n << ") = " << ballot(m, n) << endl;
    }

    cout << "\nAnswer: C_10 = " << catalan(10) << endl;
    return 0;
}

"""
Problem 884: Lattice Walks with Barriers
LGV lemma, reflection principle, Catalan numbers.
"""

import numpy as np
from math import comb

def catalan(n):
    """n-th Catalan number."""
    return comb(2 * n, n) // (n + 1)

def ballot(m, n):
    """Paths from (0,0) to (m,n) staying weakly below y=x."""
    if n > m:
        return 0
    return comb(m + n, m) - comb(m + n, m + 1)

def lgv_det(sources, dests):
    """Compute LGV determinant for non-intersecting lattice paths."""
    k = len(sources)
    M = np.zeros((k, k))
    for i in range(k):
        for j in range(k):
            dx = dests[j][0] - sources[i][0]
            dy = dests[j][1] - sources[i][1]
            if dx >= 0 and dy >= 0:
                M[i][j] = comb(dx + dy, dx)
            else:
                M[i][j] = 0
    return round(np.linalg.det(M))

# --- Verification ---
print("=== Catalan Numbers ===")
for n in range(11):
    c = catalan(n)
    b = ballot(n, n)
    print(f"  C_{n} = {c}, ballot({n},{n}) = {b}, Match: {'OK' if c == b else 'FAIL'}")
    assert c == b

print("\n=== Ballot Problem ===")
for m, n in [(3,3),(4,4),(5,5),(4,2),(5,3),(6,2)]:
    total = comb(m + n, m)
    below = ballot(m, n)
    print(f"  ({m},{n}): total={total}, below y=x: {below}")

print("\n=== LGV Examples ===")
# Two non-intersecting paths
sources = [(0, 0), (0, 1)]
dests = [(3, 2), (3, 3)]
result = lgv_det(sources, dests)
print(f"  Sources={sources}, Dests={dests}: {result} non-intersecting path pairs")

# Three paths
sources3 = [(0, 0), (0, 1), (0, 2)]
dests3 = [(4, 2), (4, 3), (4, 4)]
result3 = lgv_det(sources3, dests3)
print(f"  3 paths: {result3} non-intersecting triples")

answer = catalan(10)
print(f"\nAnswer: C_10 = {answer}")

# --- 4-Panel Visualization ---