combinat-0.2.7.2: Generate and manipulate various combinatorial objects.

Safe Haskell None Haskell2010

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

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.

countLatticePaths :: (Int, Int) -> Integer Source

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`