A053090 - OEIS

%I #46 May 05 2022 12:33:13

%S 1,0,3,2,6,6,12,12,21,22,33,36,50,54,72,78,99,108,133,144,174,188,222,

%T 240,279,300,345,370,420,450,506,540,603,642,711,756,832,882,966,1022,

%U 1113,1176,1275,1344,1452,1528,1644,1728,1853,1944,2079,2178,2322,2430

%N Number of F^3-convex polyominoes on honeycomb lattice with given semiperimeter.

%C Sequence is also given by the Poincaré series [or Poincare series] of an ordinal Hodge algebra, or algebra with straightening law, that the three-strand braid group acts on. - _Stephen P. Humphries_, Feb 06 2009

%C From _Michael Somos_, Jun 21 2012: (Start)

%C Euler transform of length-6 sequence [ 0, 3, 2, 0, 0, -1].

%C Expansion of F^3(x, 1, 1, 1) in powers of x where F^3(x, y, q, t) is the generating function defined in the FPSAC97 article.

%C The polyominoes are counted up to translations but not rotations and reflections. Thus, the unique domino with two cells is counted three times for its three orientations.

%C The semiperimeter of each hexagonal cell is 3 but each common side shared by two cells decreases the semiperimeter by one. (End)

%C From _Jianing Song_, Apr 27 2022: (Start)

%C Let w = exp(2*Pi*i/6) be a primitive 6th root of 1. Then a(n+3) is number of nonnegative integer solutions to Sum_{j=0..5} x_j = n, Sum_{j=0..5} (x_j)*w^j = 0.

%C Proof: Sum_{j=0..5} (x_j)*w^j = x_0 + (x_1)*w + (x_2)*(w-1) - x_3 - (x_4)*w - (x_5)*(w-1), so Sum_{j=0..5} (x_j)*w^j = 0 if and only if x_0 + x_5 = x_2 + x_3 and x_1 + x_2 = x_4 + x_5, or equivalently, x_0 - x_3 = x_2 - x_5 = x_4 - x_1.

%C Case (a): x_0 - x_3 = x_2 - x_5 = x_4 - x_1 >= 0, then we can write x_0 = x+t, x_1 = z, x_2 = y+t, x_3 = x, x_4 = z+t, x_5 = y. The number of solutions in this case is equal to the number of solutions to 2*s + 3*t = n, x+y+z = s.

%C Case (b): x_0 - x_3 = x_2 - x_5 = x_4 - x_1 <= 0, then we can write x_0 = x, x_1 = z+t, x_2 = y, x_3 = x+t, x_4 = z, x_5 = y+t. The number of solutions in this case is also equal to the number of solutions to 2*s + 3*t = n, x+y+z = s.

%C The common part of case (a) and case (b) is the case where x_0 - x_3 = x_2 - x_5 = x_4 - x_1 = 0, in which case the number of solutions is equal to the number of solutions to x+y+z = n/2 for even n and 0 for odd n.

%C In conclusion, the total number of solutions is 2*Sum_{s=0..n/2, 3|(n-2*s)} (s+1)*(s+2)/2 - [n even]*(n/2+1)*(n/2+2)/2, where [] is an Iverson bracket. This can be shown to be equal to a(n+3). (End)

%D Fouad Ibn-Majdoub-Hassani. Combinatoire de polyominos et des tableaux décalés oscillants. Thèse de Doctorat. Laboratoire de Recherche en Informatique, Université Paris-Sud XI, France.

%D Alain Denise, Christoph Durr and Fouad Ibn-Majdoub-Hassani. Enumération et génération aléatoire de polyominos convexes en réseau hexagonal (French) [enumeration and random generation of convex polyominoes in the honeycomb lattice]. In Proceedings of 9th Conference on Formal Power Series and Algebraic Combinatorics (FPSAC97), pages 222-234, 1997.

%H Jianing Song, <a href="/A053090/b053090.txt">Table of n, a(n) for n = 3..10003</a>

%H Alain Denise, Christoph Duerr and Fouad Ibn-Majdoub-Hassani, <a href="http://www.fpsac.org/FPSAC97/ARTICLES/Denise.ps.gz">Enumération et génération aléatoire de polyominos convexes en réseau hexagonal (French)</a>

%H Stephen P. Humphries, <a href="http://dx.doi.org/10.1080/00927879808826195">Action of some braid groups on Hodge algebras</a> Comm. Algebra 26 (1998), no. 4, pages 1233-1242. See Proposition 3.4 on page 1241. [From _Stephen P. Humphries_, Feb 06 2009]

%H <a href="/index/Rec#order_08">Index entries for linear recurrences with constant coefficients</a>, signature (1,2,-1,-2,-1,2,1,-1)

%F G.f.: x^3*(1 + x^3)/((1 - x^2)^3*(1 - x^3)).

%F a(-n) = -a(n). a(n) = round( n*(2*n^2 + 3)/144 - (-1)^n*3*n/16 ). - _Michael Somos_, Jun 21 2012

%e x^3 + 3*x^5 + 2*x^6 + 6*x^7 + 6*x^8 + 12*x^9 + 12*x^10 + 21*x^11 + ...

%e +---+

%e | o | a(3) = 1

%e +---------------+

%e | o o | o  |  o | a(5) = 3

%e |     |  o | o  |

%e +---------------+

%e |  o  | o o | a(6) = 2

%e | o o |  o  |

%e +---------------------------------------+

%e |       | o   |   o |  o  |      | o o  |

%e | o o o |  o  |  o  | o o |  o o |  o o | a(7) = 6

%e |       |   o | o   |  o  | o o  |      |

%e +---------------------------------------+

%e - _Michael Somos_, Jun 21 2012

%o (PARI) {a(n) = round( n * (2*n^2 + 3) / 144 - (-1)^n * 3*n / 16)} /* _Michael Somos_, Jun 21 2012 */

%o (PARI) {a(n) = sign(n) * polcoeff( x^3 * (1 + x^3) / ((1 - x^2)^3 * (1 - x^3)) + x * O(x^abs(n)), abs(n))} /* _Michael Somos_, Jun 21 2012 */

%K nonn,easy

%O 3,3

%A _Fouad IBN MAJDOUB HASSANI_, Feb 28 2000