A378383 Number of subwords of the form UDDD in nondecreasing Dyck paths of length 2*n.

0, 0, 0, 1, 5, 19, 64, 202, 612, 1803, 5206, 14809, 41650, 116114, 321478, 885169, 2426462, 6627499, 18048088, 49026874, 132901176, 359625015, 971639014, 2621683741, 7065545950, 19022080034, 51163908874, 137499581917, 369235213742, 990822728623, 2657069356996

Offset

0,5

Comments

A Dyck path is nondecreasing if the y-coordinates of its valleys form a nondecreasing sequence.

Links

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

E. Barcucci, A. Del Lungo, S. Fezzi, and R. Pinzani, Nondecreasing Dyck paths and q-Fibonacci numbers, Discrete Math., 170 (1997), 211-217.

Éva Czabarka, Rigoberto Flórez, Leandro Junes, and José L. Ramírez, Enumerations of peaks and valleys on non-decreasing Dyck paths, Discrete Math., Vol. 341, No. 10 (2018), pp. 2789-2807. See p. 2798.

Rigoberto Flórez, Leandro Junes, Luisa M. Montoya, and José L. Ramírez, Counting Subwords in Non-Decreasing Dyck Paths, J. Int. Seq. (2025) Vol. 28, Art. No. 25.1.6. See pp. 15, 19.

Rigoberto Flórez, Leandro Junes, and José L. Ramírez, Enumerating several aspects of non-decreasing Dyck paths, Discrete Mathematics, Vol. 342, Issue 11 (2019), 3079-3097. See page 3092.

Index entries for linear recurrences with constant coefficients, signature (10,-39,74,-69,28,-4).

Formula

a(n) =((n-3)*L(2n-5)+L(2n-3)+F(2n+2) -5*(n+5)*2^(n-4))/5 for n>=3, where F(n) = A000045(n) and L(n) = A000032(n).

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

Mathematica

Table[If[n < 3, 0, (1/5)((n-3)LucasL[2n-5]+LucasL[2n-3]+Fibonacci[2n+2]-5(n+5) 2^(n-4))], {n, 0, 26}]

Crossrefs

Cf. A000032, A000045, A377679, A377670, A375995, A377857, A377866, A377867.

Sequence in context: A304134 A387185 A318946 * A229239 A296330 A304162

Adjacent sequences: A378380 A378381 A378382 * A378384 A378385 A378386

Keyword

nonn,easy,changed

Author

Rigoberto Florez, Nov 24 2024

Status

approved