A394309 - OEIS

%I #27 Jul 20 2026 19:07:57

%S 1,1,1,4,13,56,277,1429,8489,51769,344961,2391698,17496661,133658565,

%T 1060426557,8749399966,74494928017,655734728718,5936865639625,

%U 55292734329958,528332681177821,5174197047357241,51867294310990885,531492968044248844,5562798258563207737

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

%C 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.

%H Alois P. Heinz, <a href="/A394309/b394309.txt">Table of n, a(n) for n = 0..670</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Motzkin_number">Motzkin number</a>

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

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

%p b:= proc(x, y, t, k) option remember; `if`(y<0 or y>x, 0,

%p      `if`(x=0, 1, k*b(x-1, y+1, true, k)+b(x-1, y, false, k)+

%p      `if`(t, 0, b(x-1, y-1, false, k))))

%p     end:

%p a:= n-> b(n,0,false,n):

%p seq(a(n), n=0..24);

%t 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 *)

%t Array[b[#, 0, False, #] &, 25,0] (* _Shenghui Yang_, Jul 13 2026 *)

%Y Cf. A001006, A089732, A307906.

%K nonn,changed

%O 0,4

%A _Alois P. Heinz_, Apr 12 2026