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

1, 1, 2, 3, 7, 13, 32, 70, 179, 435, 1142, 2947, 7889, 21051, 57192, 155661, 427795, 1179451, 3271214, 9102665, 25434661, 71282431, 200406472, 564905068, 1596435581, 4521772933, 12835116530, 36504093693, 104012240063, 296871993373, 848694481664, 2429882584254, 6966789756243

Offset

0,3

Comments

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).

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.

Links

Andrew Howroyd, Table of n, a(n) for n = 0..1000

Yi-Zhong Wang, A Mathematical Derivation of the Isomorphism Between the Minimum Recurrence Order of Chromatic Polynomials for Grid Graphs and Sequence A378941, Nat'l Yang Ming Chiao Tung Univ. (Taiwan, 2026).

Formula

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

Example

The Motzkin paths for a(1)..a(5) are:
a(1) = 1: H;
a(2) = 2: HH, UD;
a(3) = 3: HHH, UHD, HUD=UDH;
a(4) = 7: HHHH, HUDH, UHHD, UUDD, UDUD, HHUD=UDHH, HUHD=UHDH.
a(5) = 13: HHHHH, HUHDH, UHHHD, UUHDD, UDHUD, HHHUD=UDHHH, HHUHD=UHDHH, HHUDH=HUDHH, HUHHD=UHHDH, HUUDD=UUDDH, HUDUD=UDUDH, UHUDD=UUHDD, UHDUD=UPUHD.

Prog

(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

Crossrefs

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

Sequence in context: A003120 A032131 A389767 * A324844 A007827 A250308

Adjacent sequences: A378938 A378939 A378940 * A378942 A378943 A378944

Keyword

nonn

Author

Andrew Howroyd, Dec 17 2024

Status

approved