A287776 -id:A287776 - cp's OEIS frontend

A371705 Number of Dyck paths of semilength n such that neighboring peaks have different heights.

1, 1, 1, 3, 6, 16, 43, 116, 329, 947, 2762, 8176, 24469, 73896, 224960, 689623, 2126947, 6595273, 20548732, 64298032, 201969823, 636639087, 2013174695, 6384574754, 20302081620, 64716553655, 206764068578, 661983640080, 2123573339921, 6824597707820, 21969711674581

Offset: 0

Alois P. Heinz, Apr 03 2024

nonn

			a(3) = 3:    /\
            /  \        /\            /\
           /    \      /  \/\      /\/  \    .

Alois P. Heinz, Table of n, a(n) for n = 0..555
Wikipedia, Counting lattice paths

Cf. A000108, A287776.

b:= proc(x, y, h, t) option remember;
     `if`(y<0 or y>x, 0, `if`(x=0, 1, b(x-1, y+1, h, 1)+
     `if`(t=0 or y<>h, b(x-1, y-1, `if`(t=1, y, h), 0), 0)))
    end:
a:= n-> b(2*n, 0$3):
seq(a(n), n=0..30);

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.

Original entry on oeis.org

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

Alois P. Heinz, May 30 2017

nonn

Also 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

			. a(3) = 2:                 /\
.             /\/\/\     /\/  \     ,
.
. a(4) = 4:                   /\       /\         /\/\
.             /\/\/\/\   /\/\/  \   /\/  \/\   /\/    \   .

Andrei Asinowski and Vít Jelínek. Two types of Dyck paths (unpublished manuscript).

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

Cf. A000108, A059715, A287776.

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 b(2*n, 0$2):
seq(a(n), n=0..35);

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 *)

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

A371726 Number of Dyck paths of semilength n such that neighboring peaks differ in height by at most one and first and last peak are at height one.

Original entry on oeis.org

1, 1, 1, 1, 2, 4, 8, 17, 39, 93, 227, 567, 1447, 3760, 9917, 26492, 71567, 195256, 537397, 1490614, 4163508, 11702411, 33078992, 93986117, 268294604, 769171970, 2213834911, 6395017291, 18534987580, 53887644375, 157121564325, 459351495858, 1346290327899

Offset: 0

Alois P. Heinz, Apr 04 2024

nonn

			a(4) = 2:                     /\
             /\/\/\/\      /\/  \/\      .

Alois P. Heinz, Table of n, a(n) for n = 0..2031
Alois P. Heinz, Animation of a(9)=93 paths
Wikipedia, Counting lattice paths

Cf. A000108, A287776, A371705, A371727.

b:= proc(x, y, h, t) option remember; `if`(y<0 or y>x, 0,
      `if`(x=0, `if`(h>1, 0, 1), `if`(t=1 and abs(y-h)>1, 0,
         b(x-1, y-1, `if`(t=1, y, h), 0))+b(x-1, y+1, h, 1)))
    end:
a:= n-> b(2*n, 0$3):
seq(a(n), n=0..32);

cp's OEIS Frontend

A371705 Number of Dyck paths of semilength n such that neighboring peaks have different heights.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A371726 Number of Dyck paths of semilength n such that neighboring peaks differ in height by at most one and first and last peak are at height one.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple