A390111 a(n) is the total number of vertices of degree 1 in Catalan word grid graphs with n parts.

4, 10, 29, 91, 300, 1023, 3575, 12727, 45968, 167960, 619514, 2302990, 8617640, 32427585, 122611275, 465542655, 1774086600, 6782469540, 26004015510, 99953651850, 385077767880, 1486591659150, 5749679124774, 22275652390326, 86434602692480, 335860170462208, 1306751215490420

Offset

2,1

Links

Table of n, a(n) for n=2..28.

Aubrey Blecher and Arnold Knopfmacher, Grid graphs of Catalan words, Online Journal of Analytic Combinatorics, Issue 20, 2025. 1-19. See Theorem 3.1 at p. 9.

Formula

a(n) = (3*binomial(2*n,n) + 5*binomial(2*n-2, n-1) - binomial(2*n+2, n+1))/2.

G.f.: (1 - x - 5*x^2)/(2*x) - (1 - 3*x - 5*x^2)/(2*x*sqrt(1-4*x)).

E.g.f.: (exp(2*x)*((1 + 5*x)*BesselI(0, 2*x) - (2 + 5*x)*BesselI(1, 2*x)) - 1 - 5*x)/2.

a(n) ~ 4^(n-1)/(2*sqrt(Pi*n)).

Mathematica

a[n_]:=(3Binomial[2n, n]+5Binomial[2n-2, n-1]-Binomial[2n+2, n+1])/2; Array[a, 27, 2] (* or *)
CoefficientList[Series[(1-x-5x^2)/(2x)-(1-3*x-5x^2)/(2x*Sqrt[1-4x]), {x, 0, 28}], x]

Crossrefs

Cf. A000108, A000302, A000984, A390115, A390116.

Sequence in context: A212262 A233347 A264158 * A152808 A243601 A243602

Adjacent sequences: A390108 A390109 A390110 * A390112 A390113 A390114

Keyword

nonn,easy

Author

Stefano Spezia, Oct 25 2025

Status

approved