notatio

DyckPathsByHeight ​

Dyck paths of semilength nn with maximum height exactly hh.

DyckPathsByHeight(n, h)Dyck paths of semilength nn with maximum height exactly hh
Typed signatures
TypePackageApplies
(integer<0..>, integer<0..>) -> indexed_collection<dyck_path>combinatoricsalways

Domain: Collections

Details
  • Rows sum to the Catalan numbers (A000108): ∑hCount(DyckPathsByHeight(n,h))=Cn\sum_h Count(DyckPathsByHeight(n, h)) = C_n.

Definition

Epsil, as the implementation runs it.

count(_n, _h)

0 if 0 > _h else _tables[2 * _n * 2 * (_h + 1) + 0 + (_h + 1) *
                                                     (1 if _h == 0 else 0) + 1]

unrank(_n, _h, _r)

Drop(Fold(Function(us if us[3] == 0 else Apply(
                                                (uc0: integer) => Join(
                                                                        [
                                                                          us[1] -
                                                                          0,
                                                                          us[2] +
                                                                          1,
                                                                          us[3] -
                                                                          1,
                                                                          Max(
                                                                               us[4],
                                                                               1 if us[2] + 1 ==
                                                                                    _h else 0,
                                                                             ),
                                                                        ],
                                                                        Drop(us, 4),
                                                                        [1],
                                                                      ) if us[1] <
                                                                          uc0 else Join([
                                                                                       us[1] - uc0,
                                                                                       us[2] - 1,
                                                                                       us[3] - 1,
                                                                                       Max(us[4], 1 if us[2] - 1 ==
                                                                                                       _h else 0),
                                                                                     ], Drop(us, 4), [0]),
                                                (0 if us[2] + 1 > _h else _tables[(us[3] - 1) *
                                                                                  2 *
                                                                                  (_h + 1) +
                                                                                  us[2] + 1 +
                                                                                  (_h + 1) *
                                                                                  Max(
                                                                                       us[4],
                                                                                       1 if us[2] + 1 ==
                                                                                            _h else 0,
                                                                                     ) +
                                                                                  1]) if 1 <= us[3] &&
                                                                                        us[2] + 1 >=
                                                                                        0 else 0,
                                              ), us, ui), [
                                                           _r,
                                                           0,
                                                           2 * _n,
                                                           1 if _h == 0 else 0,
                                                         ], Range(1, 2 * _n, 1)), 4)

rank(_n, _h, _x)

Fold(
      Function(Apply(
                      (rc0: integer) => [
                                          rs[1] + 0,
                                          rs[2] + 1,
                                          rs[3] - 1,
                                          Max(
                                               rs[4],
                                               1 if rs[2] + 1 == _h else 0,
                                             ),
                                        ] if rx == 1 else [
                                                           rs[1] + rc0,
                                                           rs[2] - 1,
                                                           rs[3] - 1,
                                                           Max(
                                                                rs[4],
                                                                1 if rs[2] - 1 ==
                                                                     _h else 0,
                                                              ),
                                                         ],
                      (0 if rs[2] + 1 > _h else _tables[(rs[3] - 1) * 2 * (_h +
                                                                           1) +
                                                        rs[2] + 1 + (_h + 1) *
                                                                    Max(
                                                                         rs[4],
                                                                         1 if rs[2] +
                                                                              1 ==
                                                                              _h else 0,
                                                                       ) + 1]) if 1 <= rs[3] && rs[2] +
                                                                            1 >=
                                                                            0 else 0,
                    ), rs, rx),
      [0, 0, 2 * _n, 1 if _h == 0 else 0],
      _x,
    )[1]

valid(_n, _h, _x)

Apply(
       (ve: list<integer>) => ve[1] == 0 && ve[2] == 2 * _n && ve[3] == _h,
       Fold(
             Function(
                       vs if vs[1] < 0 else [
                                              vs[1] + 1,
                                              vs[2] + 1,
                                              Max(vs[3], vs[1] + 1),
                                            ] if vx == 1 else [
                                                               vs[1] - 1,
                                                               vs[2] + 1,
                                                               Max(
                                                                    vs[3],
                                                                    vs[1] - 1,
                                                                  ),
                                                             ] if vx == 0 else [-1, 0, 0],
                       vs,
                       vx,
                     ),
             [0, 0, 0],
             _x,
           ),
     )

tables(_n, _h)

Fold(Function(Join(
                    hf_t,
                    Fold(Function(ReplaceAt(
                                             hf_row,
                                             hf_c + 1,
                                             Apply((hf_y: integer) => Apply(
                                                                             (hf_f: integer) => 0 if hf_s < hf_y else (hf_t[(hf_s - 1) *
                                                                                                                            2 *
                                                                                                                            (_h + 1) +
                                                                                                                            hf_y + 1 +
                                                                                                                            (_h + 1) *
                                                                                                                            Max(hf_f, 1 if hf_y + 1 ==
                                                                                                                                           _h else 0) +
                                                                                                                            1] if hf_y < _h else 0) +
                                                                                                                      (hf_t[(hf_s - 1) *
                                                                                                                            2 *
                                                                                                                            (_h + 1) +
                                                                                                                            hf_y - 1 +
                                                                                                                            (_h + 1) *
                                                                                                                            hf_f +
                                                                                                                            1] if hf_y >= 1 else 0),
                                                                             (hf_c -
                                                                              hf_c %
                                                                              (_h +
                                                                               1)) /
                                                                             (_h +
                                                                              1),
                                                                           ), hf_c %
                                                                             (_h +
                                                                              1)),
                                           ), hf_row, hf_c), Map(
                                                                 Function(
                                                                           0,
                                                                           hf_z,
                                                                         ),
                                                                 Range(
                                                                        0,
                                                                        2 * (_h +
                                                                             1) -
                                                                        1,
                                                                        1,
                                                                      ),
                                                               ), Range(
                                                                        0,
                                                                        2 * (_h +
                                                                             1) -
                                                                        1,
                                                                        1,
                                                                      )),
                  ), hf_t, hf_s), Fold(
                                       Function(ReplaceAt(
                                                           hf_row,
                                                           hf_c + 1,
                                                           1 if hf_c == _h + 1 else 0,
                                                         ), hf_row, hf_c),
                                       Map(
                                            Function(0, hf_z),
                                            Range(0, 2 * (_h + 1) - 1, 1),
                                          ),
                                       Range(0, 2 * (_h + 1) - 1, 1),
                                     ), Range(1, 2 * _n + 1 - 1, 1))

Statistics

On DyckPath, called as CombinatorialStat(x, "Name").

Maps

Into and out of DyckPath, called as CombinatorialMap(x, "Name"). Properties are the laws we state and what FindStat records.

From DyckPath

  • AdinBagnoRoichmanDyckPath → DyckPathBijectionGraded mapMp00124The bijection of Adin, Bagno and Roichman on the 321-avoiding permutation of the path, read back as a path: it keeps the ups before each peak.
  • Avoiding132PermutationDyckPath → PermutationInjectionGraded mapMp00025The 132-avoiding permutation of Krattenthaler's bijection, built from the path's area sequence read from the end.
  • Avoiding312PermutationDyckPath → PermutationInjectionGraded mapMp00031The 312-avoiding permutation of Bandlow and Killpatrick: from the identity, each area-sequence entry swaps neighbouring positions that many times.
  • Avoiding321PermutationDyckPath → PermutationInjectionGraded mapMp00024The 321-avoiding permutation whose RSK pair is the pair of two-row tableaux read off the first and last halves of the path.
  • BarnabeiCastronuovoDyckPath → DyckPathBijectionGraded mapInvolutionMp00123The Schützenberger involution that reverses the canonical decompositions of the two halves of the path.
  • BilleyJockuschStanleyPermutationDyckPath → PermutationInjectionGraded mapMp00129The 321-avoiding permutation with entry (ups through a valley) + 1 at the position of its downs through that valley: the Billey-Jockusch-Stanley bijection.
  • BinaryTreeDyckPath → BinaryTreeinverseBijectionGraded mapMp00034A Dyck path U A D B, cut at its first return, as the binary tree [φ⁻¹(A), φ⁻¹(B)].
  • BinaryWordDyckPath → BinaryWordInjectionGraded mapMp00093The Dyck word as a binary word: 1 for an up step, 0 for a down step.
  • BouncePathDyckPath → DyckPathidempotentIdempotentGraded mapMp00099The bounce path of a Dyck path, bouncing between the path and the diagonal from the far corner.
  • ClockwiseTriangulationRotationDyckPath → DyckPathbijectioninverseBijectionGraded mapMp00330Rotate the triangulation of the (n + 2)-gon the path stands for one step clockwise.
  • CoriLeBorgneDyckPath → DyckPathBijectionGraded mapInvolutionMp00121The involution that appends a down step to the path, reverses the word, and takes its one rotation that is a Dyck word followed by a down step.
  • CounterclockwiseTriangulationRotationDyckPath → DyckPathbijectioninverseBijectionGraded mapMp00331Rotate the triangulation of the (n + 2)-gon the path stands for one step counterclockwise.
  • CutOutPartitionDyckPath → IntegerPartitionInjectionMp00027The partition cut out of the staircase by the path: part i is the number of downs before the (n + 1 - i)-th up step.
  • DecompositionReverseDyckPath → DyckPathinvolutionBijectionGraded mapInvolutionMp00101Split a path as U A D B at its first return, and swap the pieces, recursively: U B' D A'.
  • DelestViennotDyckPath → DyckPathbijectioninverseBijectionGraded mapMp00229The Dyck path of the parallelogram polyomino whose columns are as tall as the path's peaks, by the classical bijection.
  • ElizaldeDeutschDyckPath → DyckPathBijectionGraded mapMp00122Reading the steps in the order first, last, second, second to last, and so on, a step of the image is an up step when its matching step has not yet been read.
  • InverseDelestViennotDyckPath → DyckPathbijectioninverseBijectionGraded mapMp00227The path whose peaks are the polyomino's columns, for the polyomino the classical bijection gives this path.
  • InverseKrewerasComplementDyckPath → DyckPathBijectionGraded mapMp00327The inverse Kreweras complement of the path read as a noncrossing partition: the blocks are the downs after each up step.
  • InversePromotionDyckPath → DyckPathinverseBijectionGraded mapMp00143Inverse promotion of the Dyck path's two-row standard tableau, read back as a path.
  • InverseZetaMapDyckPath → DyckPathbijectioninverseBijectionGraded mapMp00032The inverse of the zeta map.
  • KnuthKrattenthalerDyckPath → DyckPathBijectionGraded mapMp00296The 321-avoiding permutation whose left-to-right maxima are the path's peaks, its RSK pair, and the first row of P with the second row of Q as ups.
  • KrattenthalerPermutationDyckPath → PermutationInjectionGraded mapMp00119The 321-avoiding permutation whose left-to-right maxima are the path's peaks: Krattenthaler's bijection.
  • LalanneKrewerasDyckPath → DyckPathinvolutionBijectionGraded mapInvolutionMp00120The Lalanne-Kreweras involution: labels of the ups and downs that start a double rise or fall, differenced.
  • NoncrossingPartitionDyckPath → SetPartitionInjectionGraded mapMp00138Biane's noncrossing set partition: the up steps whose matching downs lie in one run of downs form a block.
  • NoncrossingPermutationDyckPath → PermutationInjectionGraded mapMp00023The noncrossing permutation Stump's bijection gives the path: the cycles of its touch points, peeled off round by round.
  • OrderedTreeDyckPath → OrderedTreeinverseBijectionGraded mapMp00026A Dyck path as the ordered tree whose depth-first contour it is: an up step opens a child, a down step closes it.
  • PeaksToValleysDyckPath → DyckPathbijectionBijectionGraded mapMp00222The path with a valley wherever the original has a peak of height at least 2, each valley two lower than its peak.
  • PeelingDyckPath → DyckPathGraded mapMp00103The path whose area sequence is this one's with its first entry dropped and the rest lowered by two.
  • PrimeDyckPathDyckPath → DyckPathInjectionGraded mapMp00199The path wrapped in one more up step first and down step last: a path that touches the diagonal only at its ends.
  • PromotionDyckPath → DyckPathinverseBijectionGraded mapMp00142Promotion of the Dyck path's two-row standard tableau, read back as a path.
  • ReflectParallelogramPolyominoDyckPath → DyckPathinvolutionBijectionGraded mapInvolutionMp00228Reflect the path's parallelogram polyomino across the diagonal, so the first column becomes the first row.
  • ReverseComplementDyckPath → DyckPathinvolutionBijectionGraded mapInvolutionMp00028The path read backwards, with ups and downs swapped: its mirror image across the vertical.
  • RingelDyckPath → PermutationInjectionGraded mapMp00201The Ringel permutation of the Nakayama algebra whose Kupisch series the path gives, one size up.
  • RiseCompositionDyckPath → IntegerCompositionsurjectionSurjectionGraded mapMp00102The lengths of the maximal runs of up steps, left to right.
  • SwapReturnsAndLastDescentDyckPath → DyckPathBijectionGraded mapInvolutionMp00118An involution exchanging the number of returns with the length of the last descent.
  • TamariBinaryTreeDyckPath → BinaryTreebijectionBijectionGraded mapMp00029A path D = L U R D as the binary tree whose left and right subtrees are those of L and R: the bijection compatible with the Tamari order.
  • TouchCompositionDyckPath → IntegerCompositionsurjectionSurjectionGraded mapMp00100The semilengths of the primitive pieces between a path's returns to the diagonal.
  • TwoRowTableauDyckPath → StandardTableauInjectionGraded mapMp00033The standard tableau of shape (n, n) with the positions of the up steps in its first row and of the down steps in its second.
  • ZetaMapDyckPath → DyckPathbijectionBijectionGraded mapMp00030The zeta map: the area sequence read backwards, level by level from the top, as ups and downs.

To DyckPath

  • CompositionBouncePathIntegerComposition → DyckPathInjectionGraded mapMp00231The Dyck path that bounces off the diagonal once for each part: a run of that many ups, then as many downs.
  • DyckPathBinaryTree → DyckPathinverseBijectionGraded mapMp00012A binary tree [L, R] as the Dyck path U φ(L) D φ(R).
  • DyckPathOrderedTree → DyckPathinverseBijectionGraded mapMp00051An ordered tree as the Dyck path of its depth-first contour: an up step into each child, a down step out.
  • LeftToRightMaximaDyckPathPermutation → DyckPathsurjectionSurjectionGraded mapMp00127The Dyck path whose rises climb to each left-to-right maximum and whose falls run to the next one.
  • MinimalDyckPathIntegerPartition → DyckPathInjectionMp00043The shortest Dyck path tracing the shape of the Ferrers diagram.
  • ParallelogramPolyominoDyckPathIntegerPartition → DyckPathInjectionMp00230The Dyck path of the partition read as a parallelogram polyomino, one column per part.
  • SupportDyckPathParkingFunction → DyckPathSurjectionGraded mapMp00056The Dyck path whose area sequence is j minus the j-th smallest entry: the parking function's support.
  • TamariDyckPathBinaryTree → DyckPathbijectioninverseBijectionGraded mapMp00020The Dyck path T(L) U T(R) D of a tree with subtrees L and R: the bijection compatible with the Tamari order.
13 more in FindStat, not implemented here
  • Mp00007AlternatingSignMatrix → DyckPathSurjectionGraded mapto Dyck path
  • Mp00035DyckPath → AlternatingSignMatrixInjectionGraded mapto alternating sign matrix
  • Mp00132DyckPath → DyckPathBijectionGraded mapInvolutionswitch returns and last double rise
  • Mp00137DyckPath → AlternatingSignMatrixInjectionGraded mapto symmetric ASM
  • Mp00140DyckPath → BinaryTreeBijectionGraded maplogarithmic height to pruning number
  • Mp00141BinaryTree → DyckPathBijectionGraded mappruning number to logarithmic height
  • Mp00146DyckPath → PerfectMatchingInjectionGraded mapto tunnel matching
  • Mp00150PerfectMatching → DyckPathSurjectionGraded mapto Dyck path
  • Mp00232DyckPath → Posetsparallelogram poset
  • Mp00233DyckPath → SkewPartitionInjectionskew partition
  • Mp00242DyckPath → PosetsInjectionGraded mapHessenberg poset
  • Mp00333AlternatingSignMatrix → DyckPathSurjectionGraded maplink pattern
  • Mp00334AlternatingSignMatrix → DyckPathSurjectionGraded mapdiagonal height

Enumeration

Examples

1 more kept as data, checked against the oracles
Basic #

Count(DyckPathsByHeight(4,2))=7Count(DyckPathsByHeight(4, 2)) = 7

live ↗
InCount(DyckPathsByHeight(4,2))\mathrm{Count}(\mathrm{DyckPathsByHeight}(4, 2))Out77

The first element in enumeration order

live ↗
InDyckPathsByHeight(4,2)[1]\mathrm{DyckPathsByHeight}(4, 2)[1]OutDyckPath⁡([1,1,0,1,0,1,0,0]){\operatorname{DyckPath}}([1, 1, 0, 1, 0, 1, 0, 0])
About
Examples3

See also: DyckPaths