A378941 - OEIS

%I #19 Dec 18 2024 19:20:45

%S 1,1,2,3,7,13,32,70,179,435,1142,2947,7889,21051,57192,155661,427795,

%T 1179451,3271214,9102665,25434661,71282431,200406472,564905068,

%U 1596435581,4521772933,12835116530,36504093693,104012240063,296871993373,848694481664,2429882584254,6966789756243

%N Number of Motzkin paths of length n up to reversal.

%C A Motzkin path of length n is a path from (0,0) to (n,0) using only steps U = (1,1), H = (1,0) and D = (1,-1). This sequence considers a path and its reversal to be the same. The number of symmetric paths of length 2n (and also 2n+1) is given by A005773(n+1).

%C a(n) + 1 is an upper bound on the order of the linear recurrence of column n-1 of A287151. At least for columns up to 7, this bound gives the actual order of the recurrence. For example, a(5) = 13 and the order of the recurrence of column 4 (=A059524) is 14.

%H Andrew Howroyd, <a href="/A378941/b378941.txt">Table of n, a(n) for n = 0..1000</a>

%F a(n) = (A001006(n) + A005773(floor(1 + n/2))) / 2.

%e The Motzkin paths for a(1)..a(5) are:

%e a(1) = 1: H;

%e a(2) = 2: HH, UD;

%e a(3) = 3: HHH, UHD, HUD=UDH;

%e a(4) = 7: HHHH, HUDH, UHHD, UUDD, UDUD, HHUD=UDHH, HUHD=UHDH.

%e a(5) = 13: HHHHH, HUHDH, UHHHD, UUHDD, UDHUD, HHHUD=UDHHH, HHUHD=UHDHH, HHUDH=HUDHH, HUHHD=UHHDH, HUUDD=UUDDH, HUDUD=UDUDH, UHUDD=UUHDD, UHDUD=UPUHD.

%o (PARI) Vec(-3/(4*x)-(1+sqrt(1-2*x-3*x^2+O(x^40)))/(4*x^2)+(1+x)/(-1+3*x^2+sqrt(1-2*x^2-3*x^4+O(x^40)))) \\ _Thomas Scheuerle_, Dec 18 2024

%Y Cf. A001006, A005773, A007123 (similar for Dyck paths), A175954, A185100, A287151, A292357.

%K nonn

%O 0,3

%A _Andrew Howroyd_, Dec 17 2024