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
Links
- Louis Marin, Counting Polyominoes in a Rectangle b x h, arXiv:2406.16413 [cs.DM], 2024; EPTCS 403, 2024, pp. 145-149.
Programs
-
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 *) -
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
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).
Extensions
More terms from Michel Marcus, Dec 12 2024
a(26) onwards from Andrew Howroyd, Dec 17 2024
Comments