notatio

GrandDyckPaths ​

Free ±1\pm 1-step paths of length 2n2n starting and ending at height 00, with no non-negativity constraint.

OEISA000984
GrandDyckPaths(n)Free ±1\pm 1-step paths of length 2n2n starting and ending at height 00, with no non-negativity constraint
Typed signatures
TypePackageApplies
(integer<0..>) -> indexed_collection<dyck_path>combinatoricsalways

Domain: Collections

Details
  • Count is the central binomial coefficient (2nn)\binom{2n}{n} (A000984).

Definition

Epsil, as the implementation runs it.

count(_n)

Binomial(_n + _n, _n) if 0 <= _n && _n <= _n + _n else 0

unrank(_n, _r)

Drop(Fold(Function(Apply(
                          (lu_o: integer) => Join([
                                                    lu_s[1] - lu_o,
                                                    lu_s[2] - 1,
                                                    1,
                                                  ], Drop(lu_s, 2)) if lu_s[1] >=
                                                                      lu_o else Join(
                                                                                  [lu_s[1], lu_s[2], 0],
                                                                                  Drop(lu_s, 2),
                                                                                ),
                          Binomial(lu_j - 1, lu_s[2]) if 0 <= lu_s[2] && lu_s[2] <=
                                                                         lu_j -
                                                                         1 else 0,
                        ), lu_s, lu_j), [_r, _n], Range(_n + _n, 1, -1)), 2)

rank(_n, _x)

Fold(Function([
                lr_s[1] +
                ((Binomial(lr_s[3] - 1, lr_s[2] + 1) if 0 <= lr_s[2] + 1 && lr_s[2] +
                                                                            1 <=
                                                                            lr_s[3] -
                                                                            1 else 0) if lr_t == 1 else 0),
                lr_s[2] + (1 if lr_t == 1 else 0),
                lr_s[3] + 1,
              ], lr_s, lr_t), [0, 0, 1], _x)[1]

valid(_n, _x)

Length(_x) == _n + _n && Fold(Function(
                                        ok_lv_t && 0 <= lv_t && lv_t <= 1,
                                        ok_lv_t,
                                        lv_t,
                                      ), True, _x) && Fold(Function(
                                                                    lv_c + lv_u,
                                                                    lv_c,
                                                                    lv_u,
                                                                  ), 0, _x) == _n

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(GrandDyckPaths(3))=20Count(GrandDyckPaths(3)) = 20

live ↗
InCount(GrandDyckPaths(3))\mathrm{Count}(\mathrm{GrandDyckPaths}(3))Out2020

The first element in enumeration order

live ↗
InGrandDyckPaths(3)[1]\mathrm{GrandDyckPaths}(3)[1]OutDyckPath⁡([1,1,1,0,0,0]){\operatorname{DyckPath}}([1, 1, 1, 0, 0, 0])
About
Examples3
CrosswalkOEIS

See also: DyckPaths