A382987 a(n) is the total sum of the last symbol in all Catalan words of length n avoiding the pattern (>=,>=).

0, 0, 1, 4, 12, 34, 94, 258, 707, 1940, 5337, 14728, 40777, 113268, 315627, 882168, 2472669, 6949344, 19579971, 55296972, 156511626, 443902074, 1261440936, 3591153874, 10240960381, 29251149324, 83675868455, 239703961016, 687596129964, 1974890635522, 5679036727894

Offset

0,4

Comments

Avoiding the pattern (>=,>=) corresponds to ensuring that no subsequence of a Catalan word of length n, i.e., w_1...w_n, satisfies w_i >= w_{i+1} >= w_{i+2}, and it is equivalent to the avoidance of the consecutive patterns 000, 100, 110, 210.

Links

Table of n, a(n) for n=0..30.

M. Ahmia, J.-L. Baril, and B. Rezig, Enumeration on polyominoes determined by Catalan words avoiding (>=,>=), arXiv:2504.04828 [math.CO], 2025. See p. 6.

Formula

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

a(n) ~ 2*sqrt(3/Pi)*3^(n+1)/n^(3/2).

Example

a(4) = 12 since the sum of the last symbol of all Catalan words of length 4 avoiding the pattern (>=,>=) {0010, 0011, 0012, 0101, 0112, 0120, 0121, 0122, 0123} equals to 0 + 1 + 2 + 1 + 2 + 0 + 1 + 2 + 3 = 12 (see figure 2 at page 3 in Ahmia et al.).

Mathematica

f[x_]:=(x+1)((2x-1)Sqrt[1-2x-3x^2]+2x^3-3x+1)/(2x^4); CoefficientList[Series[f[x], {x, 0, 30}], x]

Crossrefs

Cf. A382988, A382989, A382990.

Sequence in context: A248873 A180224 A293005 * A173412 A079818 A115390

Adjacent sequences: A382984 A382985 A382986 * A382988 A382989 A382990

Keyword

nonn

Author

Stefano Spezia, Apr 11 2025

Status

approved