A287709 Number of Dyck paths of semilength n such that every peak at level y > 1 is preceded by (at least) one peak at level y-1.
1, 1, 1, 2, 4, 9, 22, 57, 154, 430, 1234, 3625, 10865, 33136, 102598, 321913, 1021963, 3278543, 10617413, 34678693, 114151769, 378436049, 1262822229, 4239469076, 14312153289, 48567846377, 165610404277, 567259571451, 1951218773118, 6738242931451, 23356148951482
Offset: 0
Keywords
Examples
. a(3) = 2: /\ . /\/\/\ /\/ \ , . . a(4) = 4: /\ /\ /\/\ . /\/\/\/\ /\/\/ \ /\/ \/\ /\/ \ .
References
- Andrei Asinowski and Vít Jelínek. Two types of Dyck paths (unpublished manuscript).
Links
- Alois P. Heinz, Table of n, a(n) for n = 0..1000
- Andrei Asinowski and Michaela A. Polley, Patterns in rectangulations. Part I: T-like patterns, inversion sequence classes I(010, 101, 120, 201) and I(011, 201), and rushed Dyck paths, arXiv:2501.11781 [math.CO], 2025. See pp. 1, 7, 25, 27.
- Axel Bacher, Progressive and rushed Dyck paths, arXiv:2403.08120 [math.CO], 2024.
- Manosij Ghosh Dastidar and Michael Wallner, Bijections and congruences involving lattice paths and integer compositions, arXiv:2402.17849 [math.CO], 2024. See p. 26.
- Anthony Guttmann, Analysis of series expansions for non-algebraic singularities, arXiv:1405.5327 [math-ph], 2014.
- Alois P. Heinz, Animation of a(7) = 57 paths
- Toufik Mansour and Mark Shattuck, Enumeration of Catalan and smooth words according to capacity, Integers (2025) Vol. 25, Art. No. A5. See p. 12.
- Wikipedia, Counting lattice paths
Programs
-
Maple
b:= proc(x, y, k) option remember; `if`(x=0, 1, `if`(y>0, b(x-1, y-1, max(y, k)), 0)+ `if`(y<=k and y -
Mathematica
b[x_, y_, k_] := b[x, y, k] = If[x == 0, 1, If[y > 0, b[x - 1, y - 1, Max[y, k]], 0] + If[y <= k && y < x - 1, b[x - 1, y + 1, k], 0]]; a[n_] := b[2n, 0, 0]; Table[a[n], {n, 0, 35}] (* Jean-François Alcover, Jun 01 2018, from Maple *) nmax = 30; CoefficientList[Series[1 + Sum[(Sqrt[x])^(k + 1)/ChebyshevU[k + 1, 1/(2*Sqrt[x])], {k, 0, nmax}], {x, 0, nmax}], x] (* Vaclav Kotesovec, after Andrei Asinowski, Jun 22 2021 *)
Formula
G.f.: 1 + Sum_{k>=0} x^(k+1)/U_{k+1}(1/(2*x)), where U_{k}(x) is the k-th Chebyshev polynomial of the second kind. - Andrei Asinowski, Jun 21 2021
Conjecture: a(n) = Sum_{j=0..n-2} R(n-2, j) for n > 1 with a(0) = a(1) = 1 where R(n, j) = Sum_{p=0..n - j - 1} binomial(j + p, p)*R(n - j - 1, p) for 0 <= j < n with R(n, n) = 1. See A059715 for a similar conjecture. - Mikhail Kurkov, Oct 16 2023
a(n) ~ ((4*Pi)^(5/6) * log(2)^(1/3) / sqrt(3)) * 4^n * exp(-3*(Pi*log(2)/2)^(2/3) * n^(1/3)) * n^(-5/6) [Bacher, 2024, see also Guttmann, 2014, p. 21]. - Vaclav Kotesovec, Mar 14 2024
Comments