FinePaths
Dyck paths of semilength with no hills — an elementary up/down step touching the ground on both sides.
OEIS
A000957FinePaths(n)Dyck paths of semilength with no hills — an elementary up/down step touching the ground on both sidesTyped signatures
| Type | Package | Applies |
|---|---|---|
(integer<0..>) -> indexed_collection<dyck_path> | combinatorics | always |
Details
- Count is the Fine number (A000957).
Definition
Epsil, as the implementation runs it.
count(_n)
0 if _n < 0 else _tables[_n + 1]unrank(_n, _r)
Drop(Fold(
Function(ks if ks[1] == 0 else Apply((kg: integer) => Apply((kr: integer) => Apply(
(kf: list<integer>) => Apply((kq: integer) => Apply((kt: integer) => Apply(
(ki: list<integer>) => Join([kg - kq, kf[1] % kt], Drop(ks, 2), [1], ki, [0]),
Apply((kn: integer) => Apply(
(kd: integer) => 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), [kd, 0, 2kn, 1], Range(1, 2kn, 1)), 4),
(kf[1] -
kf[1] % kt) /
kt,
), kq - 1),
), _tables[kg - kf[2] +
1]), kf[2]),
Fold(
Function(Apply(
(kw: integer) => ka if ka[3] == 1 else [ka[1], km, 1] if ka[1] < kw else [ka[1] - kw, km, 0],
_tables[Max(_n, 0) +
2 +
(km - 1)] *
_tables[kg - km +
1],
), ka, km),
[kr, 0, 0],
Range(2, kg, 1),
),
), ks[2]), ks[1]), ks, kb),
[_n, _r],
Range(1, (Max(_n, 0) - Max(_n, 0) % 2) / 2, 1),
), 2)rank(_n, _x)
Fold(
Function(ks if ks[1] == 0 else Apply((kg: integer) => Apply((kp: integer) => Apply(
(ke: list<integer>) => Apply(
(km: integer) => Apply(
(kx: list<integer>) => Apply((kn: integer) => [
kg - km,
ks[2] +
Fold(Function(kc +
_tables[Max(_n, 0) +
2 +
(kq - 1)] *
_tables[kg - kq +
1], kc, kq), 0, Range(2, km - 1, 1)) +
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, 2kn, 1], kx)[1] *
_tables[kg - km +
1],
ke[2] + 1,
], km - 1),
Take(Drop(_x, kp), ke[2] -
(kp + 1)),
),
(ke[2] - kp +
1 -
(ke[2] - kp +
1) %
2) /
2,
),
Fold(
Function(([0, kj] if kh[1] +
(1 if _x[kj] == 1 else -1) ==
0 else [kh[1] +
(1 if _x[kj] == 1 else -1), 0]) if kh[2] == 0 else kh, kh, kj),
[0, 0],
Range(kp, Length(_x), 1),
),
), ks[3]), ks[1]), ks, kb),
[_n, 0, 1],
Range(1, (Max(_n, 0) - Max(_n, 0) % 2) / 2, 1),
)[2]valid(_n, _x)
Fold(Function([
hs[1] + (1 if _x[hj] == 1 else -1),
(1 if _x[hj + 1] == 0 else hs[2]) if hs[1] == 0 &&
_x[hj] == 1 && hj <
Length(_x) else hs[2],
], hs, hj), [0, 0], Range(1, Length(_x), 1))[2] == 0 if 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,
),
) else Falsetables(_n)
Apply(
(fc: list<integer>) => Join(Fold(
Function(Apply((ff: list<integer>) => ReplaceAt(
ft,
fk + 1,
Fold(
Function(fs +
fc[fm] *
ff[fk - fm +
1], fs, fm),
0,
Range(2, fk, 1),
),
), ft), ft, fk),
Join(
[1],
Map(
Function(0, fz),
Range(1, Max(_n, 0), 1),
),
),
Range(1, Max(_n, 0), 1),
), fc),
Fold(
Function(Apply((cc: list<integer>) => ReplaceAt(
ct,
ck + 2,
Fold(
Function(cs +
cc[ci + 1] *
cc[ck - ci +
1], cs, ci),
0,
Range(
0,
ck,
1,
),
),
), ct), ct, ck),
Join([1], Map(Function(0, cz), Range(1, Max(_n, 0), 1))),
Range(0, Max(_n, 0) - 1, 1),
),
)Statistics
On DyckPath, called as CombinatorialStat(x, "Name").
- AdjointInvariantDescentsSt001104The descents of the invariant in a tensor power of the adjoint representation of GL2 that the path indexes, read over its step pairs.
- AreaSt000012St001295The whole squares between the path and the diagonal below it: the sum of the area sequence.
- AreaAboveBouncePathSt001584The boxes between the path and its bounce path: the area less the area of the bounce path.
- BicoloredMotzkinHeightSt001031The height of the bicolored Motzkin path made by reading the steps in pairs: two up steps rise, two down steps fall.
- BicoloredMotzkinLevelStepsSt001032The level steps of that bicolored Motzkin path: pairs of steps with one up and one down.
- BounceSt000005The bounce statistic: the sum of the bounce points of the path that bounces from its end back toward the origin.
- BounceCountSt000306The number of bounce points of the bounce path, not counting the two ends.
- BounceDeficitSt000376The binomial(n, 2) less the area and the bounce.
- BoxesBelowAtLeastTwoPeaksSt000980The boxes between the path and the diagonal that lie right of and below at least two peaks.
- BoxesBelowOnePeakSt000984The boxes between the path and the diagonal that lie right of and below exactly one peak.
- BoxWeightSt001808The product, over the up steps, of one more than the number of down steps before it.
- CenteredMultitunnelsSt000675Factorizations of the path into three parts, the middle one a Dyck path and the outer two of equal length.
- CenteredTunnelsSt000117Tunnels (an up step with its matching down step) centered on the middle of the path: positions summing to the length plus one.
- CoareaThe complement of the area within the staircase: binomial(n, 2) less the area.
- DiagonalStandardMonomialDegreeSt001508The degree of the standard monomial of the path relative to the diagonal boundary.
- DinvSt000006The dinv statistic, read from the area sequence.
- DinvDeficitSt000369The binomial(n, 2) less the area and the dinv: the boxes of the partition traced out by the path where leg minus arm is not 0 or 1.
- DoubleFallPositionSumSt000978The sum of the positions where a down step is followed by a down step.
- DoubleRisePositionSumSt000976The sum of the positions where an up step is followed by an up step.
- DoubleRisesSt000024Occurrences of two consecutive up steps.
- DoubleStepVisiblePointsSt000683Points below the path, at the parity of the path's height there, from which the north-east diagonal meets a double fall and the north-west diagonal meets a double rise.
- DownStepHeightProductSt000038The product, over the down steps, of the height each starts from.
- DownStepMajorIndexSt000947The major index counting positions in down steps only: over each valley, the number of down steps up to and including its down step; summed.
- DualRegularModuleFirstExtensionDimensionSt000951The dimension of the first extensions of the direct sum of the indecomposable injective modules by the regular module.
- FirstComponentSemilengthSt000026The position of the first return to height 0, counted in up steps: half the steps of the first primitive component.
- FirstDownStepPositionSt000439The position of the first down step.
- FirstMaximalPeakPositionSt001809The position of the up step into the first peak of maximal height.
- FirstSimpleOfMaximalProjectiveDimensionSt001264The first vertex, counting from 0, whose simple module has projective dimension equal to the global dimension.
- FirstSimpleProjectiveDimensionSt001135The projective dimension of the first simple module of the path's linear Nakayama algebra.
- GlobalMaximaSt000617The number of points of the path at the greatest height it reaches.
- HalfEvenSimpleProjectiveDimensionSumSt001507Half the sum of the projective dimensions of the simple modules that have even projective dimension.
- HalfMacMahonEqualIndexSt000979Half the sum of the positions of double rises and double falls.
- HeightSt000013The greatest height the path reaches.
- HillsSt000674Peaks at height 1 — an up step from the axis immediately followed by a down step.
- HillsOfSizeThreeSt001141Occurrences of three up steps then three down steps, starting on the axis.
- HillsOfSizeTwoSt001139Occurrences of two up steps then two down steps, starting on the axis.
- InitialRiseSt000025The length of the opening run of up steps.
- InjectiveProjectiveDimensionSumSt001018The sum of the projective dimensions of the indecomposable injective modules of the path's linear Nakayama algebra.
- InjectivesOfCodominantDimensionAtLeastTwoSt001182The indecomposable injective modules of codominant dimension at least two.
- InjectivesOfCodominantDimensionEqualToGlobalDimensionSt001013The indecomposable injective modules whose codominant dimension is the global dimension.
- InjectivesOfEvenProjectiveDimensionSt001872The indecomposable injective modules of even projective dimension.
- InjectivesOfMaximalProjectiveDimensionSt001009The indecomposable injective modules whose projective dimension is the global dimension.
- InjectivesOfNonMaximalSocleProjectiveDimensionMinusProjectiveInjectivesSt001164The indecomposable injective modules whose socle has projective dimension less than the global dimension, less the indecomposable projective-injective modules.
- InjectivesOfNonVanishingSecondExtensionWithRegularModuleSt001216The indecomposable injective modules with a nonzero second extension by the regular module.
- InjectivesOfProjectiveDimensionAtMostOneSt001180The indecomposable injective modules of projective dimension at most one.
- InjectivesOfProjectiveDimensionAtMostTwoSt001179The indecomposable injective modules of projective dimension at most two.
- InjectivesOfProjectiveDimensionOneSt001008The indecomposable injective modules of projective dimension one.
- InjectivesOfProjectiveDimensionOneBelowMaximalSt001010The indecomposable injective modules whose projective dimension is one less than the global dimension.
- InjectivesOfProjectiveDimensionTwoSt001274The indecomposable injective modules of projective dimension two.
- InteractionDifferenceSt000335The pyramid weight less the upper interactions: lower interactions less upper interactions.
- InteriorReturnsReturns to height 0 strictly before the end.
- LargestAreaSequenceEntrySt000442The largest entry of the area sequence: the greatest area to the right of an up step.
- LastDoubleRisePositionSt000874The position of the last double rise; 0 if there is none.
- LastSimpleOfMaximalProjectiveDimensionSt001265The last vertex, counting from 0, whose simple module has projective dimension equal to the global dimension.
- LastUpStepPositionSt000438The position of the last up step.
- LeftTunnelsSt000120Tunnels (an up step with its matching down step) left of the middle: positions summing to less than the length plus one.
- LogarithmicHeightSt000920The floor of the binary logarithm of the height plus one.
- LongestAscentSt000444The longest run of consecutive up steps.
- LongestDescentThe longest run of consecutive down steps.
- LongestZigzagSt000981The length of the longest stretch of steps that alternate between up and down.
- LongTunnelsSt000443St001007St001187St001224The longest sequences of consecutive tunnels: the semilength less the valleys.
- MacMahonEqualIndexSt000977The sum of the positions of double rises and double falls: MacMahon's equal index of the step word.
- MajorIndexThe sum of the descent positions of the step word — where an up step is followed by a down step.
- MaximalFirstExtensionWithRegularModuleSt001210The greatest dimension of the first extensions of an indecomposable module by the regular module.
- MaximalModuleProjectiveAndInjectiveDimensionSumSt001258The greatest sum of the projective and the injective dimension of an indecomposable module.
- MaximalSecondExtensionOfSimplesWithRegularModuleSt001192The greatest dimension of the second extensions of a simple module by the regular module.
- MaximalSimpleDominantDimensionSt001024The greatest dominant dimension of a simple module.
- MaximalSimpleProjectiveAndInjectiveDimensionSumSt001183The greatest sum of the projective and the injective dimension of a simple module.
- MiddleNonRunHeightSt001910The height of the middle turning point: the middle one of the peaks and valleys, left to right.
- MinimalPeakHeightSt001481The height of the lowest peak.
- MinimalRiseSt000655The length of the shortest rise.
- MinimalValleyHeightSt001107The lowest height of a valley, or the semilength if the path has none.
- ModulesOfMaximalProjectiveAndInjectiveDimensionSt001001The indecomposable modules whose projective and injective dimensions both equal the global dimension.
- ModulesOfMaximalProjectiveDimensionSt001000The indecomposable modules whose projective dimension is the global dimension.
- ModulesOfProjectiveAndInjectiveDimensionAtLeastTwoSt001140The indecomposable modules whose projective and injective dimensions are both at least two.
- ModulesOfProjectiveAndInjectiveDimensionAtMostOneSt001002The indecomposable modules whose projective and injective dimensions are both at most one.
- ModulesOfProjectiveDimensionAtMostOneSt001003The indecomposable modules of projective dimension at most one.
- ModulesOfProjectiveDimensionTwoSt001232The indecomposable modules of projective dimension two.
- ModulesOfProjectiveOrInjectiveDimensionAtMostOneSt001138The indecomposable modules whose projective dimension or injective dimension is at most one.
- ModulesOfVanishingFirstExtensionWithRegularModuleSt001213The indecomposable modules with no first extension by the regular module.
- NakayamaDominantDimensionSt000685The dominant dimension of the path's linear Nakayama algebra.
- NakayamaGlobalDimensionSt000684The global dimension of the linear Nakayama algebra of the path: the largest projective dimension of a simple module.
- NakayamaGlobalMinusDominantDimensionSt000688The global dimension less the dominant dimension of the path's linear Nakayama algebra.
- NestedCenteredTunnelPairsSt000790Pairs of centered tunnels, one strictly inside the other.
- NestedLeftTunnelPairsSt000791Pairs of left tunnels, one strictly inside the other.
- NoncrossingMergeableSingletonPairsSt001932Pairs of singleton blocks of the path's noncrossing partition that can be merged into one block, leaving the partition noncrossing.
- NonFinalConstantRunsOfLengthAtLeastTwoSt000340Maximal runs of equal steps, at least two long, that are followed by a step of the other kind: the occurrences of two up steps then a down step, or two down steps then an up step.
- NonProjectiveInjectiveCodominantDimensionSumSt001020The sum of the codominant dimensions of the non-projective indecomposable injective modules.
- NonProjectiveInjectiveProjectiveDimensionSpreadSt001026The difference between the greatest and the least projective dimension of a non-projective indecomposable injective module.
- NonProjectiveInjectiveToNonInjectiveProjectiveHomDimensionSt000687The dimension of the homomorphisms from the direct sum of the non-projective indecomposable injective modules to the direct sum of the non-injective indecomposable projective modules.
- NorthStepOrderingCountSt001786The total orderings of the up steps such that the up steps after the k-th down step are never among the first k in the order.
- OccurrencesOfDDUSt000386Occurrences of two down steps followed by an up step.
- OccurrencesOfUDUSt000932St001067St001223Occurrences of an up, a down and an up step.
- OccurrencesOfUUUSt000931Occurrences of three consecutive up steps.
- ParallelogramPolyominoAreaSt001034The cells of the parallelogram polyomino the path corresponds to under the Delest-Viennot bijection.
- ParallelogramPolyominoInnerCornersSt001036The inner corners of the parallelogram polyomino: the turns from east to north on its two bounding paths, not counting the corners every polyomino has.
- ParallelogramPolyominoMaximalColumnHeightSt001039The height of the tallest column of the parallelogram polyomino.
- ParallelogramPolyominoMinimalColumnHeightSt001038The height of the shortest column of the parallelogram polyomino.
- ParallelogramPolyominoNormalizedAreaSt001033The area of the parallelogram polyomino less the semilength: the cells beyond the smallest polyomino.
- ParallelogramPolyominoUpperInnerCornersSt001037The inner corners of the polyomino's upper path: its turns from east to north, not counting the first.
- ParkingFunctionCountSt000014The parking functions supported by the path: semilength factorial over the product of the factorials of the rise lengths.
- PeakHeightExcessSt000394The sum of the heights of the peaks, less the number of peaks.
- PeakHeightProductSt001959The product of the heights of the peaks.
- PeakHeightSquareSumSt001688The sum of the squares of the heights of the peaks.
- PeakHeightSumSt000395The sum of the heights of the peaks.
- PeakLeftToRightMaximaSt001732Peaks higher than every peak to their left.
- PeakRectangleAreaSumSt000645The sum, over consecutive peaks, of the area of the rectangle they span with the valley between them.
- PeaksSt000015St001068Occurrences of an up step immediately followed by a down step.
- PeaksMinusNakayamaDominantDimensionSt000970The peaks of the path less the dominant dimension of its linear Nakayama algebra.
- PeaksMinusNakayamaGlobalDimensionSt000966The peaks of the path less the global dimension of its linear Nakayama algebra.
- ProjectiveMinusCodominantDimensionSumSt001021The sum, over the non-projective indecomposable injective modules, of their projective dimension less their codominant dimension.
- ProjectivesOfMaximalInjectiveDimensionSt000999The indecomposable projective modules whose injective dimension is the global dimension.
- ProperlyAboveDyckPathCountSt000419The Dyck paths of the same semilength weakly above this path, itself excluded.
- ProperlyBelowDyckPathCountSt000421The Dyck paths of the same semilength weakly below this path, itself excluded.
- PyramidWeightSt000144Over each peak, the shorter of the up run before it and the down run after it, summed: the sizes of the maximal pyramids.
- RadicalEndomorphismDimensionSt001228The dimension of the endomorphisms of the Jacobson radical of the path's linear Nakayama algebra.
- RadicalSelfExtensionDimensionSt001225The dimension of the first extensions of the Jacobson radical by itself.
- RadicalToSquaredRadicalExtensionDimensionSt001229The dimension of the first extensions of the Jacobson radical by its square.
- RegularModuloSocleToRadicalExtensionDimensionSt001254The dimension of the first extensions of the regular module modulo its socle by the Jacobson radical.
- ReturnsSt000011Points where the path comes back to height 0.
- RisesOfLengthAtLeastThreeSt000660Rises (maximal runs of up steps) of length at least 3.
- RisesOfLengthAtLeastTwoSt000659Rises (maximal runs of up steps) of length at least 2.
- RisesOfLengthOneSt000445Rises (maximal runs of up steps) of length 1.
- RisesOfLengthOneAtOddHeightSt001172Rises of length 1 that start at an odd height.
- RisesOfLengthThreeSt000661Rises (maximal runs of up steps) of length 3.
- RisesOfLengthTwoSt000658Rises (maximal runs of up steps) of length 2.
- RunsOfLengthOneSt001669Maximal runs of equal steps that are a single step.
- SecondToLastInjectiveProjectiveDimensionSt001217The projective dimension of the indecomposable injective module whose socle is the second-to-last simple module.
- SetValuedTableauComajorIndexSt001956The comajor index of the set-valued two-row tableau the path corresponds to: the sum, over its natural descents k, of the semilength plus one less k.
- SetValuedTableauNaturalDescentsSt001955The natural descents of the set-valued two-row tableau the path corresponds to, read off the step pairs by FindStat's rules.
- SimpleProjectiveDimensionProductSt001299The product of the nonzero projective dimensions of the simple modules of the path's linear Nakayama algebra.
- SimpleProjectiveDimensionSumSt001019The sum of the projective dimensions of the simple modules of the path's linear Nakayama algebra.
- SimplesOfDominantDimensionAtLeastThreeSt001163The simple modules whose dominant dimension is at least three.
- SimplesOfDominantDimensionEqualToGlobalDimensionSt001159The simple modules whose dominant dimension is the global dimension.
- SimplesOfEqualProjectiveAndInjectiveDimensionSt001027The simple modules whose projective dimension equals their injective dimension.
- SimplesOfEvenProjectiveDimensionSt001165St001471The simple modules of even projective dimension.
- SimplesOfMaximalEvenProjectiveDimensionSt001493The simple modules whose projective dimension is the greatest even one that occurs: the global dimension if it is even, else one less.
- SimplesOfMaximalProjectiveDimensionSt001006The simple modules whose projective dimension is the global dimension.
- SimplesOfNonMaximalProjectiveDimensionSt001170The simple modules whose projective dimension is less than the global dimension.
- SimplesOfProjectiveDimensionAtMostFourSt001190The simple modules of projective dimension at most four.
- SimplesOfProjectiveDimensionAtMostThreeSt001023The simple modules of projective dimension at most three.
- SimplesOfProjectiveDimensionAtMostTwoSt001012The simple modules of projective dimension at most two.
- SimplesOfProjectiveDimensionFourSt001025The simple modules of projective dimension four.
- SimplesOfProjectiveDimensionThreeSt001022The simple modules of projective dimension three.
- SimplesOfProjectiveDimensionTwoSt001011The simple modules of projective dimension two.
- SimplesOfSmallInjectiveDimensionOrPositiveDominantDimensionSt001237The simple modules whose injective dimension is at most one or whose dominant dimension is at least one.
- SimplesOfTwoDimensionalSecondExtensionWithRegularModuleSt001221The simple modules whose second extensions by the regular module have dimension two.
- SimplesOfVanishingSecondExtensionWithRegularModuleSt001211The simple modules with no second extension by the regular module.
- SimpleSummandsOfSecondRadicalLayerSt001480The simple summands of J^2/J^3 for the Jacobson radical J of the path's linear Nakayama algebra, one for each indecomposable projective of dimension at least three.
- SkewHookPositionSumSt000946The sum of the skew hook positions: after two up steps and a down step, the down step's rank among the down steps; after two down steps and an up step, the rank of the second down step.
- SocleSimplesOfVanishingFirstExtensionWithRegularModuleSt001483The simple modules in the socle of the regular module that have no first extension by the regular module.
- SocleToRadicalExtensionDimensionSt001227The dimension of the first extensions of the socle of the regular module by the Jacobson radical.
- SymmetryDegreeSt001523The number of step pairs, counting inward from the ends, at which the path agrees in height with its mirror image.
- ThreeCatalanPathCountSt001800The paths from the origin to (n, n, n) with x >= y >= z whose first two coordinates trace this Dyck path and whose last two coordinates trace it as well.
- ThreeDimensionalModulesOfProjectiveDimensionOneSt001234The indecomposable modules of dimension three and projective dimension one.
- TouchPointCountSt000011Points where the path touches the axis — the returns.
- TwoDimensionalModulesOfProjectiveDimensionOneSt001233The indecomposable modules of dimension two and projective dimension one.
- UnitIntervalGraphTwinVerticesSt001189The twin vertices of the path's unit interval graph: the indices where the next up step and the next down step each follow directly.
- UpperInteractionsSt000331Over each valley, the shorter of the down run before it and the up run after it, summed: the factors of k down steps then k up steps.
- UpStepMajorIndexSt001161The major index counting positions in up steps only: over each valley, the number of up steps up to its down step; summed.
- UpStepsAfterLastDoubleRiseSt000678Up steps after the first step of the last double rise; all of them if there is none.
- UpStepsAtEvenPositionsSt000329Up steps at an even position, counting from 1.
- UpStepsAtOddPositionsSt000676Up steps at an odd position, counting from 1.
- ValleyPositionSumSt000027The sum of the positions of the valleys: a down step followed by an up step.
- ValleysSt000053St001169Occurrences of a down step immediately followed by an up step.
- ValleysAboveAxisSt000052Valleys not on the axis: a down step followed by an up step, at height above 0.
- ValleyTunnelSemilengthSumSt000476The sum of the semilengths of the tunnels that end at a valley.
- WeaklyAboveDyckPathCountSt000420The Dyck paths of the same semilength weakly above this path, itself included.
- WeaklyAboveLatticePathCountSt001361The up-and-down paths of the same length, ending anywhere, that stay weakly above this path.
- WeaklyBelowDyckPathCountSt000418The Dyck paths of the same semilength weakly below this path, itself included.
- WeakPeakLeftToRightMaximaSt001733Peaks at least as high as every peak to their left.
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 oraclesAbout
| Examples | 3 |
|---|---|
| Crosswalk | OEIS |
See also: DyckPaths