A322325 Number of nondecreasing Motzkin paths of length n.

1, 1, 2, 4, 9, 21, 49, 115, 269, 630, 1474, 3450, 8073, 18893, 44212, 103465, 242125, 566617, 1325982, 3103035, 7261648, 16993545, 39767898, 93063924, 217786044, 509657890, 1192689641, 2791104828, 6531679192, 15285285161, 35770272112, 83708766611, 195893326791

Offset

0,3

Links

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

R. Flórez and J. L. Ramírez, Some enumerations on non-decreasing Motzkin paths, Australasian Journal of Combinatorics, 72(1) (2018), 138-154.

Index entries for linear recurrences with constant coefficients, signature (2,2,-3,0,1)

Formula

a(n) = 2*a(n-1) + 2*a(n-2) - 3*a(n-3) + a(n-5), a(0)=1, a(1)=1, a(2)=2, a(3)=4, a(4)=9.

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

Example

For n=6 we have 49 paths. Among the A001006(6) = 51 Motzkin paths, the following two paths are not nondecreasing Motzkin paths: UHUDDH and UUDHDH.

Mathematica

LinearRecurrence[{2, 2, -3, 0, 1}, {1, 1, 2, 4, 9}, 40] (* Amiram Eldar, Dec 03 2018 *)

Crossrefs

Column k=0 of A322329.

Cf. A001006, A001519.

Sequence in context: A266232 A052921 A219150 * A355046 A275864 A343264

Adjacent sequences: A322322 A322323 A322324 * A322326 A322327 A322328

Keyword

nonn,easy

Author

José Luis Ramírez Ramírez, Dec 03 2018

Status

approved