Lattice Paths

// Count paths from (0,0) to (m,n) never going above y=x (Catalan)
// = C(m+n, m) - C(m+n, m+1) = C(m+n, m) / (m-n+1) * (m-n+1)
// = C(m+n, m) * (m-n+1) / (m+1) for m >= n

// Reflection principle: paths from A to B that touch a "bad" line
// = paths from A' (reflection of A across bad line) to B
function pathsBelowDiagonal(m, n) { // paths (0,0)→(m,n) not going above y=x
    // Requires n <= m (otherwise 0 paths)
    if (n > m) return 0;
    // = C(m+n, n) - C(m+n, n-1) using reflection
    const comb = (a, b) => {
        if (b > a || b < 0) return 0;
        let r = 1;
        for (let i = 0; i < b; i++) r = r * (a - i) / (i + 1);
        return Math.round(r);
    };
    return comb(m + n, n) - comb(m + n, n - 1);
}

// Count monotone lattice paths from (r1,c1) to (r2,c2) (r steps down, c steps right)
// Without constraint: C(r2-r1 + c2-c1, r2-r1)
// With constraint "stay below y=x": use reflection principle

// Ballot problem: P(A always strictly ahead of B | A gets a votes, B gets b)
// = (a - b) / (a + b) for a > b

// LGV lemma for non-intersecting paths: determinant of C(aᵢ→bⱼ)
function lgvDeterminant(sources, sinks, pathCount) {
    const n = sources.length;
    const mat = sources.map(s => sinks.map(t => pathCount(s, t)));
    // Compute determinant
    // For 2×2: ad - bc
    if (n === 2) return mat[0][0]*mat[1][1] - mat[0][1]*mat[1][0];
    // For general n: use standard det algorithm
    // ...
}