Lattice path
A lattice path is a path on the integer lattice \mathbb{Z}^d, typically d=2, consisting of a sequence of consecutive points where each step connects adjacent lattice points via unit vectors in a predefined step set, such as east (1,0), north (0,1), or more general small steps in \{-1,0,1\}^2 \setminus \{(0,0)\}.[1][2][3] In enumerative combinatorics, lattice paths serve as a core model for counting problems, with the unrestricted paths from the origin (0,0) to (a,b) using only east and north steps enumerated by the binomial coefficient \binom{a+b}{a}, which counts the ways to arrange a east steps and b north steps in sequence.[1][2] This basic enumeration extends to higher dimensions via multinomial coefficients and forms the foundation for more complex variants, such as paths confined to cones or strips.[2] Notable restricted lattice paths include Dyck paths, which are paths from (0,0) to (2n,0) with up (1,1) and down (1,-1) steps that never go below the x-axis, counted by the Catalan number C_n = \frac{1}{n+1} \binom{2n}{n}, and they bijectively correspond to balanced parentheses, binary trees, and non-crossing partitions.[2][3] The ballot theorem, which quantifies paths staying above the diagonal using the reflection principle, further refines these counts, with applications to election outcomes and queueing theory.[2] Lattice paths have broad applications beyond pure combinatorics, modeling random walks in probability and statistics, vicious walkers in statistical physics, polymer configurations in chemistry, and integer programming solutions in computer science.[2][3] Advanced enumeration techniques, including generating functions, the kernel method, and the Lindström-Gessel-Viennot lemma for non-intersecting paths, enable asymptotic analysis and connections to orthogonal polynomials, symmetric functions, and plane partitions.[2]Basic Concepts
Definition and Terminology
A lattice path is a sequence of points in the integer lattice \mathbb{Z}^d, typically \mathbb{Z}^2, where each consecutive pair of points differs by a fixed set of allowed steps, connecting lattice points with integer coordinates.[4] These paths often start at the origin (0,0) and end at a specified point (m,n), forming a walk along the grid lines of the lattice.[1] Standard steps in lattice paths include the east step (1,0) and the north step (0,1), though other directions such as south (0,-1) or west (-1,0) may be permitted depending on the context.[5] Particular emphasis is placed on monotone lattice paths, which use only non-decreasing steps like east and north, ensuring the path never moves left or down. Key terminology includes lattice points, the integer-coordinate vertices visited by the path; edges or steps, the line segments connecting consecutive points; and the length of the path, defined as the number of steps taken.[4] Paths are commonly notated as sequences of step abbreviations, such as R for right (east) and U for up (north), e.g., the sequence RURRU represents a specific path from (0,0) to (3,2). The starting and ending points are specified to define the path's scope, with the endpoint determining the total displacement in each coordinate.[1] The study of lattice paths originated in 18th-century combinatorics, with foundational work by Leonhard Euler on related enumeration problems in grids, predating explicit developments in the 19th century.[5]Grid and Step Types
Lattice paths are primarily constructed on the integer lattice \mathbb{Z}^2, where points have integer coordinates, allowing paths to traverse the entire plane unless otherwise constrained.[1] This grid structure provides a discrete framework for modeling sequences of moves between adjacent points. In many combinatorial applications, paths are restricted to the first quadrant \mathbb{N}_0^2 (non-negative integers), ensuring that coordinates remain non-negative and preventing excursions into negative regions.[6] Extensions to the full \mathbb{Z}^2 plane accommodate paths that may cross axes, while higher-dimensional lattices like \mathbb{Z}^d generalize the concept for multidimensional paths.[7] Toroidal grids, formed by identifying opposite boundaries of a finite rectangular lattice to create periodic conditions, appear in certain graph-theoretic variants of lattice paths.[8] The step sets defining lattice paths consist of vectors corresponding to moves between adjacent lattice points, typically unit length for simplicity. Common steps include horizontal moves (1,0) (east) or (-1,0) (west), and vertical moves (0,1) (north) or (0,-1) (south), forming a sequence of connected line segments.[1] For monotone paths, the step set is restricted to non-decreasing directions, such as only east (1,0) and north (0,1), ensuring no backtracking or descent in coordinates.[6] In contrast, paths allowing down or left steps, such as including (0,-1) or (-1,0), enable closed or returning configurations, though these may violate monotonicity. More general directed steps, like diagonals (1,1) or (1,-1), expand the set while maintaining a positive horizontal drift.[7] Path constraints emphasize monotonicity in many cases, where each step increases at least one coordinate without reversal, defining the path length as the total number of steps taken. For instance, a monotone path from (0,0) to (2,2) requires exactly two east steps and two north steps in some order, forming a sequence of four moves.[1] Variations distinguish directed paths, which enforce steps in predefined orientations (e.g., only positive directions), from undirected paths that permit symmetric moves without directional bias, though the latter are less common in enumerative combinatorics.[6] Finite grids impose boundary limits on path extent, while infinite grids like \mathbb{Z}^2 allow unbounded exploration.[7]Monotone Paths
North-East Paths
North-East lattice paths represent the simplest form of monotone lattice paths, consisting exclusively of horizontal and vertical movements in positive directions. A North-East path from the origin (0,0) to a point (m,n) in the integer lattice is defined as a sequence of steps, where each step is either an East move of (1,0) or a North move of (0,1), resulting in exactly m East steps and n North steps to reach the endpoint.[9] These paths inherently remain within the non-negative quadrant, as no step decreases the x- or y-coordinate, ensuring all intermediate points have non-negative integer coordinates. The total length of such a path is m + n steps, with the order of East and North steps determining the specific route taken. For example, a path to (2,2) might follow the sequence East-East-North-North (EENN), which proceeds along the x-axis to (2,0) before ascending to (2,2); alternatively, East-North-East-North (ENEN) alternates directions, passing through points (1,0), (1,1), (2,1), and (2,2); or North-North-East-East (NNEE), which first climbs to (0,2) along the y-axis and then moves right to (2,2). These examples illustrate how different interleavings of the steps create varied trajectories while adhering to the monotone constraint.[10] In combinatorial terms, North-East paths correspond directly to sequences (or words) in the alphabet {E, N} of length m + n, containing precisely m E's and n N's, where the position of each step dictates the path's shape on the grid.[11] This sequential representation underscores their role as foundational objects in enumerative combinatorics, facilitating analysis of their structural properties without imposing additional boundaries.[9]Enumeration via Binomial Coefficients
The number of unrestricted north-east lattice paths from (0,0) to (m,n), consisting of m east steps (1,0) and n north steps (0,1), is given by the binomial coefficient \binom{m+n}{m}, which equals \frac{(m+n)!}{m! \, n!}.[5] This counts the distinct sequences of steps required to reach the endpoint, where the total number of steps is m + n.[12] To derive this formula, consider that any such path is a sequence of exactly m east steps and n north steps in some order. The total number of distinct sequences is the number of ways to choose m positions out of the m + n total steps for the east steps (with the remaining n positions assigned to north steps), which directly yields \binom{m+n}{m}.[5] This combinatorial argument provides a straightforward counting mechanism without reference to generating functions or recurrences.[12] A proof of this enumeration can be established via a bijection to the set of subsets of size m from a set of m + n elements. Specifically, map each path to the subset of positions where east steps occur; this correspondence is one-to-one and onto, confirming the count \binom{m+n}{m}.[12] An inductive proof also holds: the base case for m = 0 or n = 0 is trivial (1 path each), and for larger values, paths to (m,n) either end with an east step (preceded by paths to (m-1,n)) or a north step (preceded by paths to (m,n-1)), giving the recurrence \binom{m+n}{m} = \binom{m+n-1}{m-1} + \binom{m+n-1}{m}, which aligns with the Pascal identity for binomial coefficients.[5] Combinatorially, these paths interpret as binary sequences of length m + n with exactly m zeros (east steps) and n ones (north steps), providing a direct equivalence to the definition of binomial coefficients.[12] In a voting context, they model sequences where m voters favor one candidate and n favor another, with the path tracing the cumulative vote tally without restrictions on lead changes.[5] This enumeration generalizes to paths with multiple step types via multinomial coefficients. For instance, the number of paths from (0,0,0) to (m,n,k) using east (1,0,0), north (0,1,0), and up (0,0,1) steps is \binom{m+n+k}{m,n,k} = \frac{(m+n+k)!}{m! \, n! \, k!}, obtained by choosing positions for each step type in the total sequence of m + n + k steps.[5]Bounded and Non-Intersecting Paths
Dyck Paths
A Dyck path of semilength n is a lattice path from (0,0) to (n,n) on the integer grid, consisting of n east steps (1,0) and n north steps (0,1), that never rises above the diagonal line y = x.[13] This condition is equivalent to requiring that, in the sequence of steps, the number of east steps is at least the number of north steps in every prefix.[11] As a result, the path stays weakly below the diagonal, touching it at the start and end points, and possibly at intermediate lattice points along the way.[14] This two-dimensional formulation of Dyck paths on the grid is closely related to a one-dimensional representation, where the path is viewed as a walk from (0,0) to (2n,0) using up steps (1,1) and down steps (1,-1), never descending below the x-axis.[15] In this equivalent model, the up steps correspond to east steps in the grid version, and down steps to north steps, preserving the non-negativity condition that mirrors the prefix balance in the original lattice path.[16] This reformulation grounds the combinatorial structure in a simpler excursion on the line while maintaining the bounded nature inherent to the two-dimensional grid paths. For illustration, consider n=1: the unique Dyck path is the sequence east then north, tracing (0,0) \to (1,0) \to (1,1), which satisfies y \leq x at every point.[11] For n=2, the two Dyck paths are:- East, east, north, north: (0,0) \to (1,0) \to (2,0) \to (2,1) \to (2,2)
- East, north, east, north: (0,0) \to (1,0) \to (1,1) \to (2,1) \to (2,2)