Generate lattice paths

A lattice path is a path in the two-dimensional integer grid $\mathbb{Z}^2$ that starts at the origin $(0,0)$ and that consists of steps that change the current position by $(+1,+1)$ or by $(+1,-1)$, and these are called upsteps and downsteps, respectively. We only consider lattice paths that have the same number of upsteps and downsteps, i.e., they end on the line $y=0$. In our program, we represent a lattice path by a bitstring, by reading the path from left to right, and encoding every downstep by a 0-bit and every upstep by a 1-bit. A flaw of the lattice path is a downstep below the line $y=0$. The following figure shows a lattice path with 3 flaws (highlighted in red), together with its bitstring representation.

100100111100

A Dyck path is a lattice path with no flaws. The Chung-Feller theorem [CF49] asserts that for each fixed number $e$ of flaws, the number of lattice paths of length $2k$ with $e$ flaws is given by the $k$-th Catalan number, independently of the value of $e$. In particular, Dyck paths are counted by the Catalan numbers. The paper by Mütze, Standke and Wiechert [MSW18] provides a new proof of the Chung-Feller theorem. Specifically, it describes a bijection between lattice paths of length $2k$ with $e$ flaws and $e+1$ flaws, with the additional property that the bijection only swaps two steps of the lattice path (an upstep with a downstep). This bijection is illustrated in the following figure for $k=3$, and it operates along the columns. When iterating the bijection from $e=0$ to $e=k$, every step of the lattice path is flipped exactly once, i.e., the bijection maps complementary paths onto each other (compare the first and last row).

flaws
0
1
2
3

The algorithm running on this website implements the bijection described above, and it outputs the lattice paths in the table column by column. In the graphical output, flaws are highlighted in red, and in the textual output, the number of flaws is printed first.

The number of lattice paths of length $2k$ with exactly $k$ many upsteps and downsteps is given by the central binomial coefficient $\binom{2k}{k}$, which is OEIS A000984. Dyck paths are enumerated by the Catalan numbers $C_k=\frac{1}{k+1}\binom{2k}{k}$, which is OEIS A000108.

[Zipped C++ source code (GNU GPL)]

• [CF49] K. L. Chung and W. Feller. On fluctuations in coin-tossing. Proc. Nat. Acad. Sci. U. S. A., 35:605–608, 1949.
• [MSW18] T. Mütze, C. Standke, and V. Wiechert. A minimum-change version of the Chung-Feller theorem for Dyck paths. European J. Combin., 69:260–275, 2018.