A394309 Number of peakless Motzkin paths of length n with up steps in n colors.

1, 1, 1, 4, 13, 56, 277, 1429, 8489, 51769, 344961, 2391698, 17496661, 133658565, 1060426557, 8749399966, 74494928017, 655734728718, 5936865639625, 55292734329958, 528332681177821, 5174197047357241, 51867294310990885, 531492968044248844, 5562798258563207737

Offset

0,4

Comments

A peakless Motzkin path of length n is a lattice path from (0,0) to (n,0) using only steps U = (1,1), F = (1,0) and D = (1,-1) but no consecutive steps UD.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..670

Wikipedia, Motzkin number

Formula

a(n) = Sum_{k>=0} n^k * A089732(n,k).

a(n) == 1 (mod n) for n>=1.

Maple

b:= proc(x, y, t, k) option remember; `if`(y<0 or y>x, 0,
     `if`(x=0, 1, k*b(x-1, y+1, true, k)+b(x-1, y, false, k)+
     `if`(t, 0, b(x-1, y-1, false, k))))
    end:
a:= n-> b(n, 0, false, n):
seq(a(n), n=0..24);

Mathematica

b[x_, y_, t_, k_]:=b[x, y, t, k]=If[y<0||y>x, 0, If[x==0, 1, k*b[x-1, y+1, True, k]+b[x-1, y, False, k]+If[t, 0, b[x-1, y-1, False, k]]]] (* from Maple *)
Array[b[#, 0, False, #] &, 25, 0] (* Shenghui Yang, Jul 13 2026 *)

Crossrefs

Cf. A001006, A089732, A307906.

Sequence in context: A163070 A239981 A243549 * A344418 A159595 A009300

Adjacent sequences: A394306 A394307 A394308 * A394310 A394311 A394312

Keyword

nonn,changed

Author

Alois P. Heinz, Apr 12 2026

Status

approved