How statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
Statement
Fix a natural number , start points and end points in . Put
the number of monotone lattice paths from to . Then
where is the set of non-intersecting -systems (Path systems between two families of lattice points, and non-intersecting systems).
If the configuration is compatible, meaning that every monotone path meets every monotone path whenever and , then only the identity permutation contributes and
Facts & Assumptions
Given: a natural number , start points , end points , and the matrix with .
For , the determinant is (For , the determinant over a commutative ring by the Leibniz formula, and for a real matrix).
For each permutation , the set of -systems is finite, and its cardinality is the product (Path systems between two families of lattice points, and non-intersecting systems, The product rule: , and ).
There is a sign-reversing involution on the intersecting systems (Tail-swapping is a sign-reversing involution on the intersecting systems).
The sign is multiplicative, so and hence (The sign is a homomorphism , surjective exactly when ).
Proof
Expanding by [F1] and reindexing the finite sum by gives Indeed [F3] gives and, after putting , the product becomes .
For each permutation , the product is exactly the number of -systems by [F2], so
Split each finite set into its non-intersecting part and its intersecting part. The intersecting systems cancel in pairs under the involution of [L1], because paired terms carry opposite signs and equal absolute values. Therefore the sum of step 2.1 reduces to
In the compatible case, every non-identity permutation has an inversion with , and the compatibility hypothesis says that every path meets every path ; so every -system is intersecting and . Only the identity permutation remains, and the determinant counts the non-intersecting systems joining to .
Remarks
- This is the lattice-path form of the Lindstrom-Gessel-Viennot lemma. The general acyclic-digraph statement needs digraph machinery that this page does not build, so the theorem is stated exactly in the form the page uses.
Depends on
- Path systems between two families of lattice points, and non-intersecting systems
- Tail-swapping is a sign-reversing involution on the intersecting systems
- For $n\ge1$, the determinant over a commutative ring by the Leibniz formula, and $|\det A|$ for a real matrix
- Finite rectangular matrices over a commutative ring, their entries, rows and columns
- The sign is a homomorphism $S_n\to\{+1,-1\}$, surjective exactly when $n\ge 2$
- The product rule: $\lvert A \times B\rvert = \lvert A\rvert\,\lvert B\rvert$, and $\big\lvert\prod_{i<m} A_i\big\rvert = \prod_{i<m}\lvert A_i\rvert$
- The sum rule: a finite disjoint union is finite with $\lvert A \cup B\rvert = \lvert A\rvert + \lvert B\rvert$ and $\lvert\bigcup_{i \in I} A_i\rvert = \sum_{i \in I}\lvert A_i\rvert$, and a sum over a finite index set splits along a partition
- $\lvert\mathcal{M}((0,0),(m,n))\rvert=\binom{m+n}{n}$
Used by
Dependency tree · two levels
48 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.
Sources
- C. Krattenthaler, "Lattice Path Enumeration", ch. 10 of the Handbook of Enumerative Combinatorics, §10.13 (standard reference, not scraped)