OFFSET
0,4
COMMENTS
Also the number of Dyck paths of semilength (n-1) whose maximum height is attained by the initial ascent. (That is, Dyck paths with prefix U^kD, k>=1, and maximum height k.) For a(3)=2: UDUD, UUDD. For a(4)=3: UDUDUD, UUDUDD, UUDDUD, UUUDDD. (Andrei Asinowski and Vít Jelínek) - Andrei Asinowski, Jun 21 2021
From Andrei Asinowski, Sep 01 2025: (Start)
Also the number of strong rectangulations of size (n-1) that avoid the patterns "top" and "bottom" (that is, the T-shape and the upside-down T-shape). (Andrei Asinowski and Michaela Polley, Thm. 13).
Also the number of (010,101,120,201)-avoiding inversion sequences e of length (n-1) in which all left-to-right maxima e_j satisfy e_j=j-1. Also the number of (010,110,120,210)-avoiding inversion sequences of length (n-1) that satisfy this condition. Also the number of (010,100,120,210)-avoiding inversion sequences of length (n-1) that satisfy this condition. (Andrei Asinowski and Michaela Polley, Prop. 14).
Also the number of (011,201)-avoiding inversion sequences e of length (n-1) in which the set of values is precisely {0,1,2,...,M}, where M is the maximum value of e. (Andrei Asinowski and Michaela Polley, Prop. 15). (End)
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.
Danai Deligeorgaki and Krishna Menon, How to bounce your canon permutation, arXiv:2603.22565 [math.CO], 2026. See pp. 26-27.
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.
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
EXAMPLE
. a(3) = 2: /\
. /\/\/\ /\/ \ ,
.
. a(4) = 4: /\ /\ /\/\
. /\/\/\/\ /\/\/ \ /\/ \/\ /\/ \ .
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<x-1, b(x-1, y+1, k), 0))
end:
a:= n-> b(2*n, 0$2):
seq(a(n), n=0..35);
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 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Alois P. Heinz, May 30 2017
STATUS
approved