A225826 Number of binary pattern classes in the (2,n)-rectangular grid: two patterns are in same class if one of them can be obtained by a reflection or 180-degree rotation of the other.

1, 3, 7, 24, 76, 288, 1072, 4224, 16576, 66048, 262912, 1050624, 4197376, 16785408, 67121152, 268468224, 1073790976, 4295098368, 17180065792, 68720001024, 274878693376, 1099513724928, 4398049656832, 17592194433024, 70368756760576

Offset: 0

Author

Yosu Yurramendi, May 16 2013

Keywords

• nonn
• easy

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• Gregory Emmett Coxson and Jon Carmelo Russo, Enumeration and Generation of PSL Equivalence Classes for Quad-Phase Codes of Even Length, IEEE Transactions on Aerospace and Electronic Systems, Year: 2017, Volume: 53, Issue: 4, p. 1907-1915.
• Vincent Pilaud and V. Pons, Permutrees, arXiv preprint arXiv:1606.09643 [math.CO], 2016.
• Index entries for linear recurrences with constant coefficients, signature (4,4,-16).

Crossrefs

Cf. A005418 = Number of binary pattern classes in the (1,n)-rectangular grid, A225826 to A225834 are the numbers of binary pattern classes in the (m,n)-rectangular grid, 1 < m < 11, A132390 is the sequence when the 90-degree rotation for pattern equivalence is allowed. So, only a(2) is different (communicated by Jon E. Schoenfield). See A054247 for (n,n)-grids.

A225910 is the table of (m,n)-rectangular grids.

Programs

Magma

[2^(n-3)*(2^(n+1)-(-1)^n+7): n in [0..25]]; // Vincenzo Librandi, Sep 03 2013

Mathematica

LinearRecurrence[{4, 4, -16}, {1, 3, 7}, 30] (* Bruno Berselli, May 17 2013 *)
CoefficientList[Series[(1 - x - 9 x^2) / ((1 - 2 x) (1 + 2 x) (1 - 4 x)), {x, 0, 33}], x] (* Vincenzo Librandi, Sep 03 2013 *)

Formula

a(n) = 4*a(n-1) + 4*a(n-2) - 16*a(n-3) with n>2, a(0)=1, a(1)=3, a(2)=7 (communicated by Jon E. Schoenfield).

a(n) = 2^(n-3)*(2^(n+1) - (-1)^n + 7).

G.f.: (1-x-9*x^2)/((1-2*x)*(1+2*x)*(1-4*x)).