notatio

DyckPath ​

The singular-inhabitant constructor for a Dyck path, as its up/down steps.

WikipediaDyck languageNarayana numbervia NarayanaNumbersMathWorldDyckPathWikidataQ1268618OEISA000108via DyckPathsA001263via NarayanaNumbersFindStatMp00012via BinaryTreeMp00051via OrderedTreeSageMathDyckWords(n)via DyckPathssage.combinat.combinat.narayana_number(n, k)via NarayanaNumbersmathlib4DyckWordvia DyckPathscatalanvia DyckPaths
DyckPath(list)The singular-inhabitant constructor for a Dyck path, as its up/down steps.
Typed signatures
TypePackageApplies
((list<integer>) -> dyck_path) & ((binary_tree) -> dyck_path) & ((ordered_tree) -> dyck_path)combinatoricsalways

Domain: Collections·Drawn as Graphics

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

Examples

Basic #

From a binary tree: up, left tree, down, right tree (FindStat Mp00012)

live ↗
InDyckPath⁡(BinaryTree⁡([[0,0],[0,[0,0]]]))\operatorname{DyckPath}({\operatorname{BinaryTree}}(\bigl\lbrack\bigl\lbrack0, 0\bigr\rbrack, \bigl\lbrack0, \bigl\lbrack0, 0\bigr\rbrack\bigr\rbrack\bigr\rbrack))OutDyckPath⁡([1,1,0,0,1,0,1,0]){\operatorname{DyckPath}}([1, 1, 0, 0, 1, 0, 1, 0])

The same conversion, chosen by the target collection

live ↗
InCombinatorialMap(BinaryTree⁡([[0,0],[0,[0,0]]]),DyckPaths)\mathrm{CombinatorialMap}({\operatorname{BinaryTree}}(\bigl\lbrack\bigl\lbrack0, 0\bigr\rbrack, \bigl\lbrack0, \bigl\lbrack0, 0\bigr\rbrack\bigr\rbrack\bigr\rbrack), \mathrm{DyckPaths})OutDyckPath⁡([1,1,0,0,1,0,1,0]){\operatorname{DyckPath}}([1, 1, 0, 0, 1, 0, 1, 0])

The same conversion, by its FindStat id

live ↗
InCombinatorialMap(BinaryTree⁡([[0,0],[0,[0,0]]]),Mp00012)\mathrm{CombinatorialMap}({\operatorname{BinaryTree}}(\bigl\lbrack\bigl\lbrack0, 0\bigr\rbrack, \bigl\lbrack0, \bigl\lbrack0, 0\bigr\rbrack\bigr\rbrack\bigr\rbrack), \text{Mp00012})OutDyckPath⁡([1,1,0,0,1,0,1,0]){\operatorname{DyckPath}}([1, 1, 0, 0, 1, 0, 1, 0])
About
Examples3
CrosswalkWikipedia ×2MathWorldWikidataOEIS ×2FindStat ×2SageMath ×2mathlib4 ×2