A378939 Number of Schroeder paths of semilength n up to reversal.

1, 2, 5, 15, 54, 216, 947, 4375, 21018, 103550, 520041, 2649391, 13655190, 71053780, 372727751, 1968880111, 10463765490, 55909445082, 300160457453, 1618364548591, 8759315367894, 47574840887024, 259215969470139, 1416461749625543, 7760734001872842, 42624971709868054

Offset

0,2

Comments

A Schroeder path of semilength n is a path from (0,0) to (2n,0) using only steps U = (1,1), H = (2,0) and D = (1,-1). This sequence considers a path and its reversal to be the same.

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) = (A006318(n) + A110110(n))/2.

G.f.: ( -2*x - sqrt(1 - 6*x + x^2) + sqrt(1 - 6*x^2 + x^4)*(1 + x)/(1 - 2*x - x^2) ) / (4*x).

Example

The a(1)..a(3) paths are:
a(1) = 1: H, UD;
a(2) = 5: HH, UHD, UDUD, UUDD, HUD=UDH;
a(3) = 15: HHH, HUDH, UHHD, UDHUD, UDUDUD, UUHDD, UUDUDD, UUUDDD, HHUD=UDHH, HUHD=UHDH, HUDUD=UDUDH, UHDUD=UDUHD, HUUDD=UDUDH, UHUDD=UUDHD, UDUUDD=UUDDUD.

Prog

(PARI) seq(n) = { my(A=O(x^(n+2))); Vec(( -2*x - sqrt(1 - 6*x + x^2 + A) + sqrt(1 - 6*x^2 + x^4 + A)*(1 + x)/(1 - 2*x - x^2) ) / (4*x)) }

Crossrefs

Cf. A006318, A110110, A007123 (similar for Dyck paths), A378941 (similar for Motzkin paths).

Sequence in context: A277175 A056841 A390195 * A185040 A387774 A369599

Adjacent sequences: A378936 A378937 A378938 * A378940 A378941 A378942

Keyword

nonn

Author

Andrew Howroyd, Dec 19 2024

Status

approved