notatio

DyckPaths ​

The Dyck paths of semilength nn — balanced up/down words — a lazy family of Catalan many.

✓ checked against that system · ! checked, with disagreements (hover a chip)WikipediaDyck languageMathWorldDyckPathWikidataQ1268618OEISA000108✓A120588✓SageMathDyckWords(n)mathlib4DyckWordcatalan
DyckPaths(n)the CnC_n lattice paths of nn up- and nn down-steps that never dip below the axis.
Typed signatures
TypePackageApplies
(integer<0..>) -> indexed_collection<dyck_path>combinatoricsalways

Domain: Collections

Details
  • A lazy indexed collection; the count is the Catalan number Cn=1n+1(2nn)C_n = \frac{1}{n+1}\binom{2n}{n} — C4=14C_4 = 14. See CatalanNumber.
  • Each element is the step word (1 up, 0 down); drawn as a mountain range. Height, Area, Returns and Hills are Dyck-path statistics.
  • In bijection with binary trees, triangulations, and non-crossing partitions — all Catalan families.

Definition

Epsil, as the implementation runs it.

count(_n)

Apply((bd: integer) => 0 if 2 * _n < 0 || (2 * _n - 0) % 2 == 1 else Binomial(2 *
                                                                              _n, bd) -
                                                                     (0 if bd ==
                                                                           0 else Binomial(2 * _n, bd - 1)), (2 * _n -
                                                                        0 - (2 *
                                                                            _n - 0) %
                                                                           2) / 2)

unrank(_n, _r)

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

rank(_n, _x)

Fold(Function(Apply(
                     (rc0: integer) => [rs[1] + 0, rs[2] + 1, rs[3] - 1, 1] if rx ==
                                                                               1 else [
                                                                                       rs[1] + rc0,
                                                                                       rs[2] - 1,
                                                                                       rs[3] - 1,
                                                                                       1,
                                                                                     ],
                     Apply(
                            (bd: integer) => 0 if rs[3] - 1 < rs[2] + 1 || (rs[3] -
                                                                            1 -
                                                                            (rs[2] +
                                                                             1)) %
                                                                           2 == 1 else Binomial(rs[3] - 1, bd) -
                                                                                      (0 if bd == 0 else Binomial(rs[3] - 1, bd - 1)),
                            (rs[3] - 1 - (rs[2] + 1) - (rs[3] - 1 - (rs[2] + 1)) %
                                                       2) / 2,
                          ) if 1 <= rs[3] && rs[2] + 1 >= 0 else 0,
                   ), rs, rx), [0, 0, 2 * _n, 1], _x)[1]

valid(_n, _x)

Apply(
       (ve: list<integer>) => ve[1] == 0 && ve[2] == 2 * _n,
       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,
           ),
     )

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

Basic #

C3C_3

live ↗
InCount(DyckPaths(3))\mathrm{Count}(\mathrm{DyckPaths}(3))Out55

three ups then three downs

live ↗
InDyckPaths(3)[1]\mathrm{DyckPaths}(3)[1]OutDyckPath⁡([1,1,1,0,0,0]){\operatorname{DyckPath}}([1, 1, 1, 0, 0, 0])
Statistics #

Dyck paths of semilength 4 by height

live ↗
InTally(CombinatorialStat(DyckPaths(4),Height))\mathrm{Tally}(\mathrm{CombinatorialStat}(\mathrm{DyckPaths}(4), \text{Height}))OutTuple⁡([4,3,2,1],[1,5,7,1])\operatorname{Tuple}(\bigl\lbrack4, 3, 2, 1\bigr\rbrack,\bigl\lbrack1, 5, 7, 1\bigr\rbrack)

by returns to the axis: a row of the Catalan triangle

live ↗
InTally(CombinatorialStat(DyckPaths(4),Returns))\mathrm{Tally}(\mathrm{CombinatorialStat}(\mathrm{DyckPaths}(4), \text{Returns}))OutTuple⁡([1,2,3,4],[5,5,3,1])\operatorname{Tuple}(\bigl\lbrack1, 2, 3, 4\bigr\rbrack,\bigl\lbrack5, 5, 3, 1\bigr\rbrack)

by peaks: the Narayana numbers

live ↗
InTally(CombinatorialStat(DyckPaths(4),Peaks))\mathrm{Tally}(\mathrm{CombinatorialStat}(\mathrm{DyckPaths}(4), \text{Peaks}))OutTuple⁡([1,2,3,4],[1,6,6,1])\operatorname{Tuple}(\bigl\lbrack1, 2, 3, 4\bigr\rbrack,\bigl\lbrack1, 6, 6, 1\bigr\rbrack)

by area: the coefficients of Carlitz's q-Catalan number

live ↗
InTally(CombinatorialStat(DyckPaths(4),Area))\mathrm{Tally}(\mathrm{CombinatorialStat}(\mathrm{DyckPaths}(4), \text{Area}))OutTuple⁡([6,5,4,3,2,1,0],[1,1,2,3,3,3,1])\operatorname{Tuple}(\bigl\lbrack6, 5, 4, 3, 2, 1, 0\bigr\rbrack,\bigl\lbrack1, 1, 2, 3, 3, 3, 1\bigr\rbrack)
About
Examples6
CrosswalkWikipediaMathWorldWikidataOEIS ×2SageMathmathlib4 ×2

See also: CatalanNumber, Count, At, BinaryTrees