A334979 a(n) is the total number of down steps between the (n-1)-th and n-th up steps in all 3_1-Dyck paths of length 4*n. A 3_1-Dyck path is a lattice path with steps (1, 3), (1, -1) that starts and ends at y = 0 and stays above the line y = -1.

0, 1, 16, 132, 1034, 8134, 64880, 525132, 4307512, 35750473, 299759200, 2535849836, 21619615164, 185582339740, 1602675301920, 13915031036412, 121396437548136, 1063653520870612, 9355905795325888, 82585983533819920, 731350409249262330, 6495673923406863630

Offset

0,3

Comments

For n = 1, there is no (n-1)-th up step, a(1) = 1 is the total number of down steps before the first up step.

Links

Michael De Vlieger, Table of n, a(n) for n = 0..1027

Andrei Asinowski, Benjamin Hackl, and Sarah J. Selkirk, Down-step statistics in generalized Dyck paths, arXiv:2007.15562 [math.CO], 2020-2022.

Formula

a(0) = 0 and a(n) = binomial(4*n+6, n+1)/(2*n+3) - 4*binomial(4*n+2, n)/(2*n+1) for n > 0.

G.f.: ((1 - 4*x)*hypergeom([1/2, 3/4, 5/4], [4/3, 5/3], 2^8*x/3^3) - 1 + 2*x)/x. - Stefano Spezia, Aug 25 2025

a(n) ~ 37 * 2^(8*n+11/2) / (3^(3*n+11/2) * n^(3/2) * sqrt(Pi)). - Amiram Eldar, Oct 23 2025

Example

For n = 2, the 3_1-Dyck paths are UDDDDUDD, UDDDUDDD, UDDUDDDD, UDUDDDDD, UUDDDDDD, DUDDDUDD, DUDDUDDD, DUDUDDDD, DUUDDDDD. Therefore the total number of down steps between the first and second up steps is a(2) = 4 + 3 + 2 + 1 + 0 + 3 + 2 + 1 + 0 = 16.

Mathematica

a[0] = 0; a[n_] := Binomial[4*n+6, n+1]/(2*n + 3) - 4 * Binomial[4*n + 2, n]/(2*n + 1); Array[a, 22, 0]

Prog

(SageMath) [binomial(4*n + 6, n + 1)/(2*n + 3) - 4*binomial(4*n + 2, n)/(2*n + 1) if n > 0 else 0 for n in srange(30)] # Benjamin Hackl, May 19 2020

Crossrefs

Cf. A334976, A334977, A334978, A334980.

Sequence in context: A335560 A253224 A387286 * A183535 A197278 A237880

Adjacent sequences: A334976 A334977 A334978 * A334980 A334981 A334982

Keyword

nonn,easy

Author

Sarah Selkirk, May 18 2020

Status

approved