Lattice path

A lattice path is a sequence of points in an integer lattice whose consecutive differences belong to a prescribed finite set of steps.

An $n$-step self-avoiding walk on a graph is a sequence $v_0,\dots ,v_n$ of distinct graph vertices with an edge between successive graph vertices. It is a graph path with $n$ edges and $n+1$ graph vertices. On a transitive graph, the exponential growth rate of rooted self-avoiding walk counts is the connective constant.

On the square lattice, a self-avoiding walk using north, east and west steps but no south steps. At each horizontal height, self-avoidance forces one monotone horizontal run. Conversely, such runs separated by north steps always give self-avoiding walks, because every new run is at a previously unvisited height.

A horizontal run has generating function $R(z)=(1+z)/(1-z)$. Decomposing each walk into $H(NH{)}^k$ gives $A(z)=R(z)/(1-zR(z))=(1+z)/(1-2z-z^2)$. Thus $a_0=1,a_1=3$ and $a_n=2a_{n-1}+a_{n-2}$. The exponential growth rate is $1+\sqrt{2}$, furnishing a strict lower bound greater than two for the connective constant of all square-lattice self-avoiding walks.

The generating function weights each self-avoiding walk by $x$ to the power of its length, including the zero-length walk. Its radius of convergence is the reciprocal of the upper exponential growth rate of the rooted counts, by the Cauchy-Hadamard theorem.

In a bipartite graph, a self-avoiding walk ends in its starting class exactly when it has even length. If degrees are bounded by $\Delta$, deleting the last edge gives ${\sigma }_{2k+1}\le \Delta {\sigma }_{2k}$ and hence $Z_G^0(x)\le Z_G(x)\le (1+\Delta x)Z_G^0(x)$ for $x\ge 0$. Thus these generating functions have the same radius of convergence.

Replace every degree-three vertex of a graph in one class of a bipartite graph by a triangle with one port for each incident edge. A self-avoiding walk whose endpoints remain in the other class cannot make two completed passages through the same triangle: each passage needs two unused ports and only three exist. Each old two-edge passage has exactly two replacements, of lengths three and four. Therefore the restricted generating functions satisfy $Z_H^0(x)=Z_G^0(\sqrt{x^3+x^4})$. If the old radius is $1/\mu$, the new radius obeys ${\rho }^3+{\rho }^4={\mu }^{-2}$.

In independent bond percolation on a graph, let $c_n$ be the number of $n$-step self-avoiding walks from a fixed graph vertex and ${\kappa }_n$ the number that are open. Then $\mathbb{E}{\kappa }_n=c_n{p}^n$. The Jensen inequality for the concave function $t^{1/n}$ gives $\mathbb{E}({\kappa }_n^{1/n})\le p{c}_n^{1/n}$. No independence between different self-avoiding walk indicators is needed. When $c_n^{1/n}\to \mu$, the limit superior is at most $p\mu$.

On the doubly infinite ladder graph, self-avoiding walks from a fixed graph vertex using only rightward or vertical steps are in bijection with words in $R,V$ containing no consecutive $V$ symbols. Their count is ${\sigma }_n=F_{n+2}$, since ${\sigma }_0=1$, ${\sigma }_1=2$, and ${\sigma }_n={\sigma }_{n-1}+{\sigma }_{n-2}$. Its exponential growth rate is the golden ratio.

If $b_n$ counts the $n$-step self-avoiding walks from a fixed vertex of a transitive lattice, the connective constant is the exponential growth rateSubmultiplicativity of $b_n$ and the Fekete lemma applied to $\log b_n$ prove existence of this limit.

For an infinite connected locally finite graph with a uniform degree bound, let ${\sigma }_n(v)$ count its length-$n$ self-avoiding walks from $v$. The suprema satisfy ${\sigma }_{m+n}\le {\sigma }_m{\sigma }_n$, so the Fekete lemma applied to their logarithms gives a finite connective constant. Unlike the usual rooted definition on a vertex-transitive graph, this definition explicitly takes the supremum over roots.

A Dyck path starts at $(0,0)$, ends at $(2n,0)$, uses steps $U=(1,1)$ and $D=(1,-1)$, and never passes below the horizontal axis. Its semilength of a Dyck path is $n$: there are $n$ up steps and $n$ down steps. The nonnegative height records a constraint throughout the journey, not just the endpoint. The Catalan number $C_n$ counts the Dyck paths of this size.

Half the number of steps in a Dyck path. A Dyck path with semilength of a Dyck path $n$ has $2n$ steps and $n$ up/down pairs; the empty Dyck path has $n=0$.

The Catalan number $C_n$ counts Dyck paths with semilength of a Dyck path $n$. For a nonnegative integer $n$,The count $C_0=1$ includes the empty path. Of the $\left(\genfrac{}{}{0ex}{}{6}{3}\right)=20$ paths with three up steps and three down steps, exactly five stay at nonnegative height. Their shapes and balanced parentheses encodings appear below.^[ref]

The useful connection is a shared decomposition. A Dyck path splits uniquely at its first-return decomposition of a Dyck path; a binary tree splits at its root into left and right subtrees; a binary parenthesization splits at its last operation. Each removes one outer unit and leaves an ordered pair of smaller objects. The resulting Catalan recurrence lets one count several different structures with the same calculation. A count of five does not mean the structures are physically identical: a bijection supplies the precise translation between them.

The first-return decomposition of a Dyck path and the rule of product giveFor a given $k$, choose the inside path in $C_k$ ways and its suffix in $C_{n-1-k}$ ways. Different first-return locations give disjoint groups, so the rule of sum adds their counts. For $n=4$, the terms are $1\cdot 5+1\cdot 2+2\cdot 1+5\cdot 1=14$. Iterating the recurrence relation computes the counts without enumerating every full path.

The ordinary generating function $C(x)={\sum }_{n\ge 0}{C}_n{x}^n$ packages the Catalan recurrence. Its Cauchy product gives the formal power series identityThe constant term is $C_0=1$. Solving the quadratic equation chooseswith the formal power series square root having constant term one. The apparent quotient at $x=0$ has constant term one after cancellation; the other quadratic solution has a pole and cannot be this ordinary generating function. The equation records the empty object or an outer unit with two ordered smaller objects.

A binary parenthesization specifies the order of binary operations on a fixed ordered list of operands, combining exactly two existing expressions at each step. It has a full binary tree as its expression structure: operands are leaves and operations are internal vertices. For four operands $a,b,c,d$, the five possibilities are $((ab)c)d$, $(a(bc))d$, $(ab)(cd)$, $a((bc)d)$, and $a(b(cd))$.

A binary parenthesization of $n+1$ operands contains $n$ binary operations. At the last operation, its left expression can contain $k$ operations and its right expression $n-1-k$. The Catalan recurrence therefore gives $C_n$ possible evaluation structures. The order of operands stays fixed; this is not a count of their permutations. Even for an associative operation whose result is unchanged, different structures can have different evaluation costs, as in the matrix-chain multiplication problem.^[ref]

Leonhard Euler's 1751 correspondence already studied triangulations of a convex polygon and gave a closed formula for their counts. Johann Andreas von Segner supplied a combinatorial recurrence relation in a paper written in 1758. Eugène Charles Catalan's nineteenth-century work connected the formula to bracketed products. This history, documented in Igor Pak's account, shows how the same counting structure reappeared through different objects; the modern name alone does not establish discovery priority.^[ref]

A string of opening and closing parentheses is balanced when its total numbers of openings and closings agree and every prefix has at least as many openings as closings. Thus (()()) is balanced, while ())(() has equal totals but an invalid prefix. Reading ( as an up step and ) as a down step gives a bijection with Dyck paths: height is the number of openings awaiting a closing parenthesis. There are $C_n$ balanced strings with $n$ pairs, including one empty string. This models nested syntax and the stack discipline that remembers the most recently opened unfinished part.

A nonempty Dyck path starts with $U$. At its first later return to height zero, cut after the matching $D$. The segment between these two steps stays at height at least one; translating it down one level gives a Dyck path $P$. The remaining suffix is another Dyck path $Q$. This gives the unique form $UPDQ$.

If the original semilength of a Dyck path is $n$ and that of $P$ is $k$, then $Q$ has semilength of a Dyck path $n-1-k$. The first return occurs after $2(k+1)$ steps. For the illustrated path UUUDDDUD, $n=4$, $P$ is UUDD, $Q$ is UD, and the first return occurs after six steps.

There are $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$ paths with $n$ up steps and $n$ down steps, ignoring the height constraint. For $n\ge 1$, reflect the prefix of a bad path through its first visit to height $-1$, swapping its up and down steps. The resulting path has $n+1$ up steps and $n-1$ down steps, hence final height two. Its first visit to height one identifies the inverse reflection, so this is a bijection. There are $\left(\genfrac{}{}{0ex}{}{2n}{n+1}\right)$ bad paths. Subtracting givesThis count connects a global nonnegative-height requirement to an unrestricted binomial coefficient. The case $n=0$ is separately the unique empty path.