A378947 Number of row states in an automaton for the enumeration of the number of fixed polyominoes with bounding box of width n.

1, 2, 6, 16, 40, 99, 247, 625, 1605, 4178, 11006, 29292, 78652, 212812, 579672, 1588242, 4374282, 12103404, 33628824, 93786966, 262450878, 736710357, 2073834417, 5853011847, 16558618507, 46949351272, 133390812252, 379708642286, 1082797114046, 3092894319075, 8848275403639

Offset

0,2

Comments

The states track the non-crossing partitions of the connected components and whether each side of the bounding rectangle has been reached.

a(n) is an upper bound on the order of the generating function of row n of A292357.

Links

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

Louis Marin, Counting Polyominoes in a Rectangle b x h, arXiv:2406.16413 [cs.DM], 2024; EPTCS 403, 2024, pp. 145-149.

Formula

a(n) = 1 + Sum_{m=1..2^n-1} A000108(A069010(m)) * 2^[m=0 mod 2] * 2^[m<2^(n-1)], where [] is the Iverson bracket.

From Andrew Howroyd, Dec 17 2024: (Start)

a(n) = 1 + Sum_{k=1..floor((n+1)/2)} (binomial(n+1, 2*k) + 2*binomial(n,2*k) + binomial(n-1,2*k)) * binomial(2*k, k)/(k+1).

a(n) = A001006(n+1) + 2*A001006(n) + A001006(n-1) - 3 for n > 0. (End)

Maple

a:= proc(n) option remember; `if`(n<3, [1, 2, 6][n+1],
       ((3*n^2+2*n-12)*a(n-1)+(n^2-13*n+15)*a(n-2)
        -3*(n-3)*(n-1)*a(n-3))/((n-2)*(n+3)))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Dec 20 2024

Mathematica

a[n_] := a[n] = If[n < 3, {1, 2, 6}[[n+1]],
   ((3*n^2 + 2*n - 12)*a[n-1] + (n^2 - 13*n + 15)*a[n-2]
   - 3*(n-3)*(n-1)*a[n-3])/((n-2)*(n+3))];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Jan 26 2025, after Alois P. Heinz *)

Prog

(PARI) b(n) = (1 + (hammingweight(bitxor(n, n>>1)))) >> 1;
C(n) = binomial(2*n, n)/(n+1);
a(n) = 1 + sum(m=1, 2^n-1, C(b(m)) * 2^((m % 2)==0) * 2^(m<2^(n-1))); \\ Michel Marcus, Dec 12 2024
(PARI) a(n) = {1 + sum(k=1, (n+1)\2, (binomial(n+1, 2*k)+2*binomial(n, 2*k)+binomial(n-1, 2*k))*binomial(2*k, k)/(k+1))} \\ Andrew Howroyd, Dec 17 2024

Crossrefs

Cf. A000108, A001006, A069010, A140662, A292357.

Sequence in context: A264551 A293004 A265278 * A111281 A018021 A215340

Adjacent sequences: A378944 A378945 A378946 * A378948 A378949 A378950

Keyword

nonn,easy,changed

Author

Louis Marin, Dec 11 2024

Extensions

More terms from Michel Marcus, Dec 12 2024

a(26) onwards from Andrew Howroyd, Dec 17 2024

Status

approved