login
A322325
Number of nondecreasing Motzkin paths of length n.
2
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
R. Flórez and J. L. Ramírez, Some enumerations on non-decreasing Motzkin paths, Australasian Journal of Combinatorics, 72(1) (2018), 138-154.
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.
Sequence in context: A266232 A052921 A219150 * A355046 A275864 A343264
KEYWORD
nonn,easy
AUTHOR
STATUS
approved