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

1, 8, 34, 132, 501, 1892, 7150, 27092, 102986, 392768, 1502596, 5764904, 22175565, 85503420, 330385110, 1279079220, 4960619070, 19269309840, 74959501020, 291986605560, 1138745167170, 4446052592904, 17376761107404, 67979051046152, 266172272041396, 1043048503525952

Offset

2,2

Links

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

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

Formula

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

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

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

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

Mathematica

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

Crossrefs

Cf. A000108, A000302, A000984, A390111, A390116.

Sequence in context: A302083 A124843 A082840 * A101644 A126395 A335749

Adjacent sequences: A390112 A390113 A390114 * A390116 A390117 A390118

Keyword

nonn,easy

Author

Stefano Spezia, Oct 25 2025

Status

approved