combinat-0.2.9.0: Generate and manipulate various combinatorial objects.

Math.Combinat.LatticePaths

Description

Dyck paths, lattice paths, etc

For example, the following figure represents a Dyck path of height 5 with 3 zero-touches (not counting the starting point, but counting the endpoint) and 7 peaks:

Synopsis

# Types

data Step Source #

A step in a lattice path

Constructors

 UpStep the step (1,1) DownStep the step (1,-1)
Instances
 Source # Instance detailsDefined in Math.Combinat.LatticePaths Methods(==) :: Step -> Step -> Bool #(/=) :: Step -> Step -> Bool # Source # Instance detailsDefined in Math.Combinat.LatticePaths Methodscompare :: Step -> Step -> Ordering #(<) :: Step -> Step -> Bool #(<=) :: Step -> Step -> Bool #(>) :: Step -> Step -> Bool #(>=) :: Step -> Step -> Bool #max :: Step -> Step -> Step #min :: Step -> Step -> Step # Source # Instance detailsDefined in Math.Combinat.LatticePaths MethodsshowsPrec :: Int -> Step -> ShowS #show :: Step -> String #showList :: [Step] -> ShowS # Source # Instance detailsDefined in Math.Combinat.LatticePaths Methods Source # Instance detailsDefined in Math.Combinat.LatticePaths Methods Source # Instance detailsDefined in Math.Combinat.LatticePaths Methods

type LatticePath = [Step] Source #

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

# ascii drawing of paths

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

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

# elementary queries

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

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

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

# path-specific queries

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

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

# Bounded Dyck paths

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.

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] Source #

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

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

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.

# Zero-level touches

Arguments

 :: Int k = number of zero-touches -> Int m = half-length -> [LatticePath]

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.

Arguments

 :: Int k = number of zero-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.

Arguments

 :: Int k = number of zero-touches -> Int m = half-length -> Integer

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.

# Dyck paths with given number of peaks

Arguments

 :: Int k = number of peaks -> Int m = half-length -> [LatticePath]

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

Synonym for peakingDyckPathsNaive

Arguments

 :: Int k = number of peaks -> Int m = half-length -> [LatticePath]

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.

Arguments

 :: Int k = number of peaks -> Int m = half-length -> Integer

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

# Random lattice paths

randomDyckPath :: RandomGen g => Int -> g -> (LatticePath, g) Source #

A uniformly random Dyck path of length 2m