A382990 a(n) is the total number of interior points of over all (>=,>=)-polyominoes of length n.

0, 0, 0, 2, 13, 59, 230, 830, 2858, 9547, 31227, 100599, 320417, 1011664, 3172230, 9892182, 30708696, 94975383, 292822629, 900431037, 2762584182, 8459318100, 25859561685, 78934174379, 240626872721, 732695058014, 2228730824384, 6773206968802, 20567144954853, 62406771069411

Offset

0,4

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..29.

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

Formula

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

a(n) = (3^(n+1) + 8*T(n) + 8*T(n+1) - 5*T(n+2) - 3*T(n+3) + T(n+4))/2 for n > 0, where T(n) = A002426(n).

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

Example

a(4) = 66 since the total number of interior points over all (>=,>=)-polyominoes of length 4, corresponding to the Catalan words {0010, 0011, 0012, 0101, 0112, 0120, 0121, 0122, 0123}, equals to 0 + 1 + 1 + 0 + 2 + 1 + 2 + 3 + 3 = 13 (see figure 2 at page 3 in Ahmia et al.).

Mathematica

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

Crossrefs

Cf. A002426, A382987, A382988, A382989.

Sequence in context: A042061 A229736 A396387 * A187560 A338818 A290721

Adjacent sequences: A382987 A382988 A382989 * A382991 A382992 A382993

Keyword

nonn

Author

Stefano Spezia, Apr 11 2025

Status

approved