A347036 Number of Motzkin paths of length n avoiding UHHD.

1, 1, 2, 4, 8, 18, 33, 73, 127, 279, 473, 1045, 1749, 3905, 6490, 14652, 24244, 55286, 91190, 209748, 345102, 799580, 1312844, 3060614, 5016396, 11756454, 19239412, 45294870, 74024768, 174964546, 285599169, 677384297, 1104527095, 2627757663, 4280633021, 10211786449

Offset

0,3

Links

Table of n, a(n) for n=0..35.

Christian Bean, Antonio Bernini, Matteo Cervetti and Luca Ferrari, Pattern avoiding Motzkin paths are almost rational, arXiv:2108.03037 [math.CO], 2021.

Formula

G.f.: (1-3*x-4*x^2+12*x^3 - (1-3*x-4*x^2+8*x^3)*sqrt(1-4*x^2))/(2*x^2*(1-2*x-3*x^2+8*x^3-4*x^4)).

D-finite with recurrence -(n+2)*(87*n-587)*a(n) +2*(262*n^2-1391*n-1316)*a(n-1) +(-439*n^2+2325*n+3238)*a(n-2) +6*(-291*n^2+1878*n-3058)*a(n-3) +4*(787*n^2-5112*n+7910)*a(n-4) -8*(n-3)*(175*n-628)*a(n-5)=0. - R. J. Mathar, Mar 06 2022

Prog

(PARI) my(x='x+O('x^40)); Vec((1-3*x-4*x^2+12*x^3 - (1-3*x-4*x^2+8*x^3)*sqrt(1-4*x^2))/(2*x^2*(1-2*x-3*x^2+8*x^3-4*x^4)))

Crossrefs

Cf. A001006.

Sequence in context: A229718 A246469 A092507 * A297188 A291583 A218874

Adjacent sequences: A347033 A347034 A347035 * A347037 A347038 A347039

Keyword

nonn,easy

Author

Michel Marcus, Aug 12 2021

Status

approved