A step in a lattice path

A lattice path is a path using only the allowed steps, never going below the zero level line y=0.

Note that if you rotate such a path by 45 degrees counterclockwise, you get a path which uses only the steps (1,0) and (0,1), and stays above the main diagonal (hence the name, we just use a different convention).

Draws the path into a list of lines. For example try:

autotabulate RowMajor (Right 5) (map asciiPath $ dyckPaths 4)

A lattice path is called "valid", if it never goes below the y=0 line.

A Dyck path is a lattice path whose last point lies on the y=0 line

Maximal height of a lattice path

Endpoint of a lattice path, which starts from (0,0).

Returns the coordinates of the path (excluding the starting point (0,0), but including the endpoint)

Counts the up-steps

Counts the down-steps

Counts both the up-steps and down-steps

Number of peaks of a path (excluding the endpoint)

Number of points on the path which touch the y=0 zero level line (excluding the starting point (0,0), but including the endpoint; that is, for Dyck paths it this is always positive!).

Number of points on the path which touch the level line at height h (excluding the starting point (0,0), but including the endpoint).

dyckPaths m lists all Dyck paths from (0,0) to (2m,0).

Remark: Dyck paths are obviously in bijection with nested parentheses, and thus also with binary trees.

Order is reverse lexicographical:

sort (dyckPaths m) == reverse (dyckPaths m)

dyckPaths m lists all Dyck paths from (0,0) to (2m,0).

sort (dyckPathsNaive m) == sort (dyckPaths m) 

Naive recursive algorithm, order is ad-hoc

The number of Dyck paths from (0,0) to (2m,0) is simply the m'th Catalan number.

The trivial bijection

The trivial bijection in the other direction

boundedDyckPaths h m lists all Dyck paths from (0,0) to (2m,0) whose height is at most h. Synonym for boundedDyckPathsNaive.

boundedDyckPathsNaive h m lists all Dyck paths from (0,0) to (2m,0) whose height is at most h.

sort (boundedDyckPaths h m) == sort [ p | p <- dyckPaths m , pathHeight p <= h ]
sort (boundedDyckPaths m m) == sort (dyckPaths m) 

Naive recursive algorithm, resulting order is pretty ad-hoc.

All lattice paths from (0,0) to (x,y). Clearly empty unless x-y is even. Synonym for latticePathsNaive

All lattice paths from (0,0) to (x,y). Clearly empty unless x-y is even.

Note that

sort (dyckPaths n) == sort (latticePaths (0,2*n))

Naive recursive algorithm, resulting order is pretty ad-hoc.

Lattice paths are counted by the numbers in the Catalan triangle.

touchingDyckPaths k m lists all Dyck paths from (0,0) to (2m,0) which touch the zero level line y=0 exactly k times (excluding the starting point, but including the endpoint; thus, k should be positive). Synonym for touchingDyckPathsNaive.

touchingDyckPathsNaive k m lists all Dyck paths from (0,0) to (2m,0) which touch the zero level line y=0 exactly k times (excluding the starting point, but including the endpoint; thus, k should be positive).

sort (touchingDyckPathsNaive k m) == sort [ p | p <- dyckPaths m , pathNumberOfZeroTouches p == k ]

Naive recursive algorithm, resulting order is pretty ad-hoc.

There is a bijection from the set of non-empty Dyck paths of length 2n which touch the zero lines t times, to lattice paths from (0,0) to (2n-t-1,t-1) (just remove all the down-steps just before touching the zero line, and also the very first up-step). This gives us a counting formula.

peakingDyckPaths k m lists all Dyck paths from (0,0) to (2m,0) with exactly k peaks.

Synonym for peakingDyckPathsNaive

peakingDyckPathsNaive k m lists all Dyck paths from (0,0) to (2m,0) with exactly k peaks.

sort (peakingDyckPathsNaive k m) = sort [ p | p <- dyckPaths m , pathNumberOfPeaks p == k ]

Naive recursive algorithm, resulting order is pretty ad-hoc.

Dyck paths of length 2m with k peaks are counted by the Narayana numbers N(m,k) = binom{m}{k} binom{m}{k-1} / m

A uniformly random Dyck path of length 2m