Math.Combinat.LatticePaths

Dyck paths, lattice paths, etc

Types

data Step

A step in a lattice path

Constructors

UpStep

the step (1,1)

DownStep

the step (1,-1)

Instances

Eq Step

Ord Step

Show Step

type LatticePath = [Step]

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).

isValidPath :: LatticePath -> Bool

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

pathHeight :: LatticePath -> Int

Maximal height of a lattice path

pathEndpoint :: LatticePath -> (Int, Int)

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

pathCoordinates :: LatticePath -> [(Int, Int)]

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

pathNumberOfZeroTouches :: LatticePath -> Int

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!).

pathNumberOfTouches'

Arguments

:: Int

h = the touch level

-> LatticePath

-> Int

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

Dyck paths

dyckPaths :: Int -> [LatticePath]

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.

countDyckPaths :: Int -> Integer

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

Bounded Dyck paths

boundedDyckPaths

Arguments

:: Int

h = maximum height

-> Int

m = half-length

-> [LatticePath]

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

boundedDyckPathsNaive

Arguments

:: Int

h = maximum height

-> Int

m = half-length

-> [LatticePath]

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.

More general lattice paths

latticePaths :: (Int, Int) -> [LatticePath]

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

latticePathsNaive :: (Int, Int) -> [LatticePath]

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.

Zero-level touches

touchingDyckPaths

Arguments

:: Int

k = number of touches

-> Int

m = half-length

-> [LatticePath]

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). Synonym for touchingDyckPathsNaive.

touchingDyckPathsNaive

Arguments

:: Int

k = number of touches

-> Int

m = half-length

-> [LatticePath]

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.