cp's OEIS Frontend

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

%I A378947 #35 Jan 26 2025 09:09:13
%S A378947 1,2,6,16,40,99,247,625,1605,4178,11006,29292,78652,212812,579672,
%T A378947 1588242,4374282,12103404,33628824,93786966,262450878,736710357,
%U A378947 2073834417,5853011847,16558618507,46949351272,133390812252,379708642286,1082797114046,3092894319075,8848275403639
%N A378947 Number of row states in an automaton for the enumeration of the number of fixed polyominoes with bounding box of width n.
%C A378947 The states track the non-crossing partitions of the connected components and whether each side of the bounding rectangle has been reached.
%C A378947 a(n) is an upper bound on the order of the generating function of row n of A292357.
%H A378947 Louis Marin, <a href="https://arxiv.org/abs/2406.16413">Counting Polyominoes in a Rectangle b x h</a>, arXiv:2406.16413 [cs.DM], 2024; EPTCS 403, 2024, pp. 145-149.
%F A378947 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.
%F A378947 From _Andrew Howroyd_, Dec 17 2024: (Start)
%F A378947 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).
%F A378947 a(n) = A001006(n+1) + 2*A001006(n) + A001006(n-1) - 3 for n > 0. (End)
%p A378947 a:= proc(n) option remember; `if`(n<3, [1, 2, 6][n+1],
%p A378947        ((3*n^2+2*n-12)*a(n-1)+(n^2-13*n+15)*a(n-2)
%p A378947         -3*(n-3)*(n-1)*a(n-3))/((n-2)*(n+3)))
%p A378947     end:
%p A378947 seq(a(n), n=0..30);  # _Alois P. Heinz_, Dec 20 2024
%t A378947 a[n_] := a[n] = If[n < 3, {1, 2, 6}[[n+1]],
%t A378947    ((3*n^2 + 2*n - 12)*a[n-1] + (n^2 - 13*n + 15)*a[n-2]
%t A378947    - 3*(n-3)*(n-1)*a[n-3])/((n-2)*(n+3))];
%t A378947 Table[a[n], {n, 0, 30}] (* _Jean-François Alcover_, Jan 26 2025, after _Alois P. Heinz_ *)
%o A378947 (PARI) b(n) = (1 + (hammingweight(bitxor(n, n>>1)))) >> 1;
%o A378947 C(n) = binomial(2*n, n)/(n+1);
%o A378947 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
%o A378947 (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
%Y A378947 Cf. A000108, A001006, A069010, A140662, A292357.
%K A378947 nonn,easy
%O A378947 0,2
%A A378947 _Louis Marin_, Dec 11 2024
%E A378947 More terms from _Michel Marcus_, Dec 12 2024
%E A378947 a(26) onwards from _Andrew Howroyd_, Dec 17 2024