cp's OEIS Frontend

A378941 Number of Motzkin paths of length n up to reversal.

%I A378941 #19 Dec 18 2024 19:20:45
%S A378941 1,1,2,3,7,13,32,70,179,435,1142,2947,7889,21051,57192,155661,427795,
%T A378941 1179451,3271214,9102665,25434661,71282431,200406472,564905068,
%U A378941 1596435581,4521772933,12835116530,36504093693,104012240063,296871993373,848694481664,2429882584254,6966789756243
%N A378941 Number of Motzkin paths of length n up to reversal.
%C A378941 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 A378941 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 A378941 Andrew Howroyd, <a href="/A378941/b378941.txt">Table of n, a(n) for n = 0..1000</a>
%F A378941 a(n) = (A001006(n) + A005773(floor(1 + n/2))) / 2.
%e A378941 The Motzkin paths for a(1)..a(5) are:
%e A378941 a(1) = 1: H;
%e A378941 a(2) = 2: HH, UD;
%e A378941 a(3) = 3: HHH, UHD, HUD=UDH;
%e A378941 a(4) = 7: HHHH, HUDH, UHHD, UUDD, UDUD, HHUD=UDHH, HUHD=UHDH.
%e A378941 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 A378941 (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 A378941 Cf. A001006, A005773, A007123 (similar for Dyck paths), A175954, A185100, A287151, A292357.
%K A378941 nonn
%O A378941 0,3
%A A378941 _Andrew Howroyd_, Dec 17 2024