A382989 a(n) is the total sum of area over all (>=,>=)-polyominoes of length n.

0, 1, 5, 19, 66, 218, 701, 2215, 6919, 21438, 66034, 202502, 618892, 1886433, 5737755, 17421735, 52823013, 159970938, 483979572, 1463006976, 4419285573, 13340964849, 40252007970, 121389925346, 365929470596, 1102688346763, 3321748158985, 10003556543907, 30118208180650

Offset

0,3

Comments

The (>=,>=)-polyominoes are those polyominoes that represent Catalan words avoiding the pattern (>=,>=). 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..28.

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

Formula

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

a(n) = (3^(n+1) + 2*T(n+1) - T(n+2) - 3*T(n+3) + T(n+4))/2, where T(n) = A002426(n).

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

Example

a(4) = 66 since the total sum of area over all (>=,>=)-polyominoes of length 4, corresponding to the Catalan words {0010, 0011, 0012, 0101, 0112, 0120, 0121, 0122, 0123}, equals to 5 + 6 + 7 + 6 + 8 + 7 + 8 + 9 + 10 = 66 (see figure 2 at page 3 in Ahmia et al.).

Mathematica

CoefficientList[Series[(1 - 4*x + 7*x^3 + 2*x^4 - (1 - 3*x - x^2 + 2*x^3)*Sqrt[1 - 2*x - 3*x^2])/(6*x^6 + 4*x^5 - 2*x^4), {x, 0, 29}], x] (* or *)
A002426[n_]:=SeriesCoefficient[1/Sqrt[1-2x-3x^2], {x, 0, n}]; a[n_]:=(3^(n+1)+2A002426[n+1]-A002426[n+2]-3A002426[n+3]+A002426[n+4])/2; Array[a, 29, 0]

Crossrefs

Cf. A002426, A382987, A382988, A382990.

Sequence in context: A124806 A059509 A137745 * A005021 A067325 A273599

Adjacent sequences: A382986 A382987 A382988 * A382990 A382991 A382992

Keyword

nonn

Author

Stefano Spezia, Apr 11 2025

Status

approved