A334682 a(n) is the total number of down-steps after the final up-step in all 3-Dyck paths of length 4*n (n up-steps and 3*n down-steps).

0, 3, 18, 118, 829, 6115, 46736, 366912, 2941528, 23981628, 198224910, 1657364566, 13992405626, 119118427610, 1021399476720, 8813544248100, 76475285228304, 666865500290884, 5840843616021192, 51361847992315320, 453282040123194425, 4013440075484640675

Offset

0,2

Comments

A 3-Dyck path is a lattice path with steps U = (1, 3), d = (1, -1) that starts at (0,0), stays (weakly) above the x-axis, and ends at the x-axis.

Links

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

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

Paul Drube, Raised k-Dyck paths, arXiv:2206.01194 [math.CO], 2022. See Appendix pp. 14-15.

Formula

a(n) = binomial(4*(n+1)+1, n+1)/(4*(n+1)+1) - binomial(4*n+1, n)/(4*n+1).

a(n) = A062750(n+1, 3*n-1).

From Muhammed Sefa Saydam, Mar 01 2025: (Start)

Let F(n,k) = binomial((k+1)*n,n)/(k*n+1), then a(n) = F(n+1,3) - F(n,3).

Generally, F(y+1,x) - F(y,x) = Sum_{k=1..y} ( F(k+1,x) - T(x,k) + F(y-k,x) ) where T(n,k) = 2*(n+1)*binomial(n*k+k-1, k-1)/(n*k+1). (End)

a(n) ~ 229 * 2^(8*n+1/2) / (3^(3*n+9/2) * n^(3/2) * sqrt(Pi)). - Amiram Eldar, Oct 26 2025

Example

For n = 2 the a(2) = 18 is the total number of down-steps after the last up-step in UdddUddd, UddUdddd, UdUddddd, UUdddddd.

Maple

b:= proc(x, y) option remember; `if`(x=y, x,
     `if`(y+3<x, b(x-1, y+3), 0)+`if`(y>0, b(x-1, y-1), 0))
    end:
a:= n-> b(4*n, 0):
seq(a(n), n=0..21);  # Alois P. Heinz, May 09 2020
# Alternative:
a:= proc(n) option remember; `if`(n<2, 3*n, (8*(4*n-1)*
      (2*n-1)*(4*n-3)*n*(229*n^2+303*n+98)*a(n-1))/
      (3*(n-1)*(3*n+2)*(3*n+4)*(n+1)*(229*n^2-155*n+24)))
    end:
seq(a(n), n=0..21);  # Alois P. Heinz, May 09 2020

Mathematica

nmax = 21;
A[_] = 0;
Do[A[x_] = 1 + x A[x]^4 + O[x]^(nmax + 2), nmax + 2];
CoefficientList[A[x], x] // Differences (* Jean-François Alcover, Aug 17 2020 *)

Prog

(PARI) a(n) = {binomial(4*(n+1)+1, n+1)/(4*(n+1)+1) - binomial(4*n+1, n)/(4*n+1)} \\ Andrew Howroyd, May 08 2020

Crossrefs

First order differences of A002293.

Cf. A062750.

Sequence in context: A113328 A196865 A153394 * A320616 A391325 A396208

Adjacent sequences: A334679 A334680 A334681 * A334683 A334684 A334685

Keyword

nonn,easy

Author

Andrei Asinowski, May 08 2020

Status

approved