A054247 -id:A054247 - cp's OEIS frontend

A177793 Partial sums of A054247.

1, 3, 9, 111, 8659, 4220403, 8594777715, 70377477369459, 2305913405481561715, 302233760834929839713907, 158456627262298939528655810163, 332307157402856267706609817833582195

Offset: 0

Jonathan Vos Post, May 13 2010

Partial sums of number of n X n binary matrices under action of dihedral group of the square D_4. Can this ever be prime?

			a(4) = 1 + 2 + 6 + 102 + 8548 = 8659 = 7 * 1237.

Cf. A002724, A054247, A054407.

A054247(n)={ local(a) ; if(n%2==0, a=2^(n^2)+2*2^(n^2/4)+3*2^(n^2/2)+2*2^((n^2+n)/2), a=2^(n^2)+2*2^((n^2+3)/4)+2^((n^2+1)/2)+4*2^((n^2+n)/2); ) ; return(a/8) ; }
A177793(n)={ return(sum(i=0,n,A054247(i))) ; }
{ for(n=0,20, print1(A177793(n),",") ; ) ; } (End)

a(n) = SUM[i=0..n] A054247(i) = SUM[i=0..n] [(1/8)*(2^(i^2)+2*2^(i^2/4)+3*2^(i^2/2)+2*2^((i^2+i)/2)) if i is even and (1/8)*(2^(i^2)+2*2^((i^2+3)/4)+2^((i^2+1)/2)+4*2^((i^2+i)/2)) if i is odd].

Extended by R. J. Mathar, May 28 2010

A014409 Number of inequivalent ways (mod D_4) a pair of checkers can be placed on an n X n board.

Original entry on oeis.org

0, 2, 8, 21, 49, 93, 171, 278, 446, 660, 970, 1347, 1863, 2471, 3269, 4188, 5356, 6678, 8316, 10145, 12365, 14817, 17743, 20946, 24714, 28808, 33566, 38703, 44611, 50955, 58185, 65912, 74648, 83946, 94384, 105453, 117801, 130853, 145331, 160590, 177430, 195132

Offset: 1

Borghard, William (bogey(AT)hostare.att.com)

Computed by Fred Hallden.

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (2,2,-6,0,6,-2,-2,1).

Cf. A054252, A019318, A082966, A242279, A242358, A054247.

[(2*n^4+14*n^2-12*n-1-(-1)^n*(2*n^2-4*n-1))/32 : n in [1..60]]; // Wesley Ivan Hurt, Dec 30 2023

LinearRecurrence[{2, 2, -6, 0, 6, -2, -2, 1}, {0, 2, 8, 21, 49, 93, 171, 278}, 40]
CoefficientList[Series[- x (x^5 + x^4 + 3 x^3 + x^2 + 4 x + 2)/((x - 1)^5 (x + 1)^3), {x, 0, 50}], x] (* Vincenzo Librandi, Oct 15 2013 *)

a(n)=if(n%2, n^4 + 8*n^2 - 8*n - 1, n^4 + 6*n^2 - 4*n)/16  \\ Charles R Greathouse IV, Feb 09 2017

a(2*n) = n/2*(2*n^3 + 3*n - 1); a(2*n+1) = n/2*(2*n^3 + 4*n^2 + 7*n + 3).
a(0)=0, a(1)=2, a(2)=8, a(3)=21, a(4)=49, a(5)=93, a(6)=171, a(7)=278, a(n)=2*a(n-1)+2*a(n-2)-6*a(n-3)+0*a(n-4)+6*a(n-5)-2*a(n-6)- 2*a(n-7)+ a(n-8). - Harvey P. Dale, May 06 2012
G.f.: -x^2*(x^5+x^4+3*x^3+x^2+4*x+2) / ((x-1)^5*(x+1)^3). - Colin Barker, Jul 11 2013
From James Stein, May 22 2014: (Start)
For odd n: a(n) = (n^4 + 8*n^2 - 8*n - 1)/16;
For even n: a(n) = n*(n^3 + 6*n - 4)/16. (End)
a(n) = A054252(n, 2), n >= 0. - Wolfdieter Lang, Oct 03 2016
E.g.f.: (x*(1 + 13*x + 6*x^2 + x^3)*cosh(x) + (-1 + 3*x + 15*x^2 + 6*x^3 + x^4)*sinh(x))/16. - Stefano Spezia, Apr 14 2022
a(n) = (2*n^4+14*n^2-12*n-1-(-1)^n*(2*n^2-4*n-1))/32. - Wesley Ivan Hurt, Dec 30 2023

More terms and formula from Hugo van der Sanden

More terms from Colin Barker, Jul 11 2013

A054252 Triangle T(n,k) of n X n binary matrices with k=0..n^2 ones under action of dihedral group of the square D_4.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 8, 16, 23, 23, 16, 8, 3, 1, 1, 3, 21, 77, 252, 567, 1051, 1465, 1674, 1465, 1051, 567, 252, 77, 21, 3, 1, 1, 6, 49, 319, 1666, 6814, 22475, 60645, 136080, 256585, 410170, 559014, 652048, 652048, 559014, 410170, 256585, 136080

Offset: 0

Vladeta Jovovic, May 04 2000

From Geoffrey Critzer, Feb 19 2013: (Start)
Cycle indices for n=2,3,4,5 respectively are:
(1/8)(s[1]^4 + 2*s[1]^2*s[2] + 3*s[2]^2 + 2*s[4]).
(1/8)(s[1]^9 + 4*s[1]^3*s[2]^3 + s[1]s[2]^4 + 2*s[1]*s[4]^2).
(1/8)(s[1]^16 + 2*s[1]^4*s[2]^6 + 2*s[4]^4 + 3*s[2]^8).
(1/8)(s[1]^25 + 4*s[1]^5*s[2]^10 + 2*s[1]*s[4]^6 + s[1]*s[2]^12).
(End)
Also the number of equivalence classes of ways of placing k 1 X 1 tiles in an n X n square under all symmetry operations of the square. - Christopher Hunt Gribble, Feb 17 2014
From Wolfdieter Lang, Oct 03 2016: (Start)
The cycle index G(n) for a square n X n grid with squares coming in two colors with k squares of one color is for the D_4 group (with 8 elements R(90)^j, S R(90)^j, j=0..3)
  (s[1]^(n^2) + s[2]^(n^2/2) +2*s[4]^(n^2/4))/8 + (s[2]^(n^2/2) + s[1]^n*s[2]^((n^2-n)/2))/4 if n is even,
  s[1]*((s[1]^(n^2-1) + s[2]^((n^2-1)/2) + 2*s[4]^((n^2-1)/4))/8) + s[1]^n*s[2]^(n*(n-1)/2)/2 if n is odd.
See the above comment by Geoffrey Critzer for n=2..5.
The figure counting series is c(x) = 1 + x for coloring, say black and white.
Therefore the counting series is C(n,x) = G(n) with substitution s[2^j] = c(x^(2*j)) = 1 + x^(2^j) for j=0,1,2. Row n gives the coefficients of C(n,x) in rising (or falling) order.  This follows from Pólya's counting theorem.  See the Harary-Palmer reference, p. 42, eq. (2.4.6), and eq. (2.2.11) with n=4 on p. 37 for the cycle index of D_4.
(End)

			T(3,2) = 8 because there are 8 nonisomorphic 3 X 3 binary matrices with two ones under action of D_4:
  [0 0 0] [0 0 0] [0 0 0] [0 0 0]
  [0 0 0] [0 0 0] [0 0 1] [0 0 1]
  [0 1 1] [1 0 1] [0 1 0] [1 0 0]
---------------------------------
  [0 0 0] [0 0 0] [0 0 0] [0 0 1]
  [0 1 0] [0 1 0] [1 0 1] [0 0 0]
  [0 0 1] [0 1 0] [0 0 0] [1 0 0]
Triangle T(n,k) begins:
1;
1, 1;
1, 1, 2,  1,  1;
1, 3, 8, 16, 23, 23, 16, 8, 3, 1;

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 42, (2.4.6), p. 37, (2.2.11).

Heinrich Ludwig, Rows n = 0..16, flattened
Index entries for sequences related to groups

Cf. A014409, A019318, A054247 (row sums), A054772.

(* As a triangle *) Prepend[Prepend[Table[CoefficientList[CycleIndexPolynomial[
GraphData[{"Grid", {n, n}}, "AutomorphismGroup"],Table[Subscript[s, i], {i, 1, 4}]] /. Table[Subscript[s, i] -> 1 + x^i, {i, 1, 4}], x], {n, 2, 10}], {1, 1}], {1}] // Grid (* Geoffrey Critzer, Aug 09 2016 *)

def T(n, k):
    if n == 0 or k == 0 or k == n*n:
        return 1
    grid = graphs.Grid2dGraph(n, n)
    m = grid.automorphism_group().cycle_index().expand(2, 'b, w')
    b, w = m.variables()
    return m.coefficient({b: k, w: n*n-k})
[T(n, k) for n in range(6) for k in range(n*n + 1)] # Freddy Barrera, Nov 23 2018

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.

Original entry on oeis.org

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

Yosu Yurramendi, May 16 2013

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).

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.

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

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 *)

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)).

A343097 Array read by antidiagonals: T(n,k) is the number of k-colorings of an n X n grid, up to rotations and reflections.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 3, 6, 1, 0, 1, 4, 21, 102, 1, 0, 1, 5, 55, 2862, 8548, 1, 0, 1, 6, 120, 34960, 5398083, 4211744, 1, 0, 1, 7, 231, 252375, 537157696, 105918450471, 8590557312, 1, 0, 1, 8, 406, 1284066, 19076074375, 140738033618944, 18761832172500795, 70368882591744, 1, 0

Offset: 0

Andrew Howroyd, Apr 14 2021

			Array begins:
====================================================================
n\k | 0 1       2            3               4                 5
----+---------------------------------------------------------------
  0 | 1 1       1            1               1                 1 ...
  1 | 0 1       2            3               4                 5 ...
  2 | 0 1       6           21              55               120 ...
  3 | 0 1     102         2862           34960            252375 ...
  4 | 0 1    8548      5398083       537157696       19076074375 ...
  5 | 0 1 4211744 105918450471 140738033618944 37252918396015625 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..860

Rows 0..5 are A000012, A001477, A002817, A217331, A217338, A283033.
Columns 0..10 are A000007, A000012, A054247, A054739, A054751, A054752, A286392, A286393, A286394, A286396, A286397.
Main diagonal is A001326.
Cf. A246106, A343095, A343875.

T(n,k) = {(k^(n^2) + 2*k^((n^2 + 3*(n%2))/4) + k^((n^2 + (n%2))/2) + 2*k^(n*(n+1)/2) + 2*k^(n*(n+n%2)/2) )/8}

T(n,k) = (k^(n^2) + 2*k^((n^2 + 3*(n mod 2))/4) + k^((n^2 + (n mod 2))/2) + 2*k^(n*(n+1)/2) + 2*k^(n*(n + n mod 2)/2) )/8.

A047937 Number of 2-colorings of an n X n grid, up to rotational symmetry.

Original entry on oeis.org

1, 2, 6, 140, 16456, 8390720, 17179934976, 140737496748032, 4611686019501162496, 604462909807864344215552, 316912650057057631849169289216, 664613997892457937028364283517337600, 5575186299632655785385110159782842147536896, 187072209578355573530071668259090783437390809661440

Offset: 0

Rob Pratt

Cycle index = 1/4(s_1^(n^2)+ 2 s_4^floor(n^2/4)s_1^(n mod 2)+s_2^floor(n^2/2)s_1^(n mod 2)). - Geoffrey Critzer, Oct 28 2011

			a(2)=6 from
00 10 11 10 11 11
00 00 00 01 10 11

Andrew Howroyd, Table of n, a(n) for n = 0..50
Peter Kagey, Illustration of a(3)=140
Peter Kagey and William Keehn, Counting tilings of the n X m grid, cylinder, and torus, arXiv:2311.13072 [math.CO], 2023.

Column k=2 of A343095.
Other columns are A047938, A047939, A047940, A047941, A047942, A047943, A047944, A047945.
Cf. A054247.

Table[(2^(n^2)+2*2^Floor[n^2/4]*2^Mod[n,2]+2^Floor[n^2/2]*2^Mod[n,2])/4,{n,0,10}]  (* Geoffrey Critzer, Oct 28 2011 *)

a(n) = (m^(n^2) + 2*m^((n^2 + 3*(n mod 2))/4) + m^((n^2 + (n mod 2))/2))/4, with m = 2.

Terms a(12) and beyond from Andrew Howroyd, Apr 14 2021

A082963 Number of n X n 0-1 matrices with half 1's and half 0's (rounded up/down if odd).

Original entry on oeis.org

1, 1, 2, 23, 1674, 652048, 1134460910, 7900674292378, 229078019084673798, 26549036304190836144544, 12611418068196090318131968752, 23955745839516317585042064530077352, 185026624806098273753009169783707528668060

Offset: 0

Vladeta Jovovic, May 27 2003

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..50
James Grime, Maths Problem: Complete Noughts and Crosses (Burnside's Lemma)

Cf. A054247, A054252, A014409, A019318.

C(n,f)={(f(1)^(n^2) + 2*f(1)^((n%2)*n)*f(2)^((n\2)*n) + 2*f(1)^n*f(2)^binomial(n,2) + f(1)^(n%2)*f(2)^(n^2\2) + 2*f(1)^(n%2)*f(4)^(floor(n/2)*ceil(n/2)))/8}
a(n)={polcoef(C(n, k->1 + x^k), n^2\2)} \\ Andrew Howroyd, Feb 01 2020

a(n) = A054252(n, floor(n^2/2)).

Terms a(12) and beyond from Andrew Howroyd, Feb 01 2020

A255016 Number of toroidal n X n binary arrays, allowing rotation and/or reflection of rows and/or columns as well as matrix transposition.

Original entry on oeis.org

1, 2, 6, 26, 805, 172112, 239123150, 1436120190288, 36028817512382026, 3731252531904348833632, 1584563250300891724601560272, 2746338834266358751489231123956672, 19358285762613388352671214587818634041520

Offset: 0

Jiyeon Lee, Feb 12 2015

nonn

Michael De Vlieger, Table of n, a(n) for n = 0..57
S. N. Ethier and Jiyeon Lee, Counting toroidal binary arrays, II, arXiv:1502.03792 [math.CO], Feb 12, 2015 and J. Int. Seq. 18 (2015) # 15.8.3.
S. N. Ethier and Jiyeon Lee, Parrondo games with two-dimensional spatial dependence, arXiv preprint arXiv:1510.06947 [math.PR], 2015.
Peter Kagey and William Keehn, Counting tilings of the n X m grid, cylinder, and torus, arXiv:2311.13072 [math.CO], 2023. See p. 3.
Wikipedia, Pólya enumeration theorem.

Cf. A184271 (number of m X n binary arrays allowing rotation of rows/columns), A179043 (main diagonal of A184271), A222188 (number of m X n binary arrays allowing rotation/reflection of rows/columns), A209251 (main diagonal of A222188), A255015 (number of n X n binary arrays allowing rotation of rows/columns as well as matrix transposition).

Cf. A054247.

a[n_] := (8 n^2)^(-1) Sum[If[Mod[n, c] == 0, Sum[If[Mod[n, d] == 0, EulerPhi[c] EulerPhi[d] 2^(n^2/ LCM[c, d]), 0], {d, 1, n}], 0], {c, 1, n}] + (4 n)^(-1) Sum[If[Mod[n, d] == 0, EulerPhi[d] 2^(n^2/d), 0], {d, 1, n}] + If[Mod[n, 2] == 1, (4 n)^(-1) Sum[If[Mod[n, d] == 0 && Mod[d, 2] == 1, EulerPhi[d] (2^(n (n + 1)/(2 d)) - 2^(n^2/d)), 0], {d, 1, n}],(8 n)^(-1) Sum[If[Mod[n, d] == 0 && Mod[d, 2] == 1, EulerPhi[d] (2^(n^2/(2 d)) + 2^(n (n + 2)/(2 d)) - 2 2^(n^2/d)), 0], {d, 1, n}]] + (1/2) If[Mod[n, 2] == 1, 2^((n^2 - 3)/2), 7 2^(n^2/2 - 4)] + (4 n)^(-1) Sum[If[Mod[n, d] == 0, EulerPhi[d] 2^(n (n + d - 2 IntegerPart[d/2])/(2 d)), 0], {d, 1, n}] + If[Mod[n, 2] == 1, 2^((n^2 - 5)/4), 5 2^(n^2/4 - 3)];

a(0)=1 from Alois P. Heinz, Feb 19 2015

A268311 Number of free polyominoes that form a continuous path of edge joined cells spanning an n X n square in both dimensions.

Original entry on oeis.org

1, 2, 24, 1051, 238048, 195284973, 577169894573, 6200686124225191

Offset: 1

Craig Knecht, Jan 31 2016

This idea originated from the water retention model for mathematical surfaces and is identical to the concept of a "lake". A lake is body of water that has dimensions of (n-2) X (n-2) when the square size is n X n. All other bodies of water are "ponds".

Iwan Jensen with his transfer matrix algorithm provided the number of symmetrically redundant solutions. Walter Trump enumerated the symmetrically unique solutions.

			The cells with value 1 show the smallest possible lake in this 4 X 4 square:
1 1 1 1
0 0 0 1
0 0 0 1
0 0 0 1
a(3)=24 = 6+7+7+3+1: There fit 6 5-ominoes in a 3x3 square, 7 6-ominoes in a 3x3 square, 7 7-ominoes in a 3x3 square, 3 8-ominoes in a 3x3 square, a 1 9-omino in a 3x3 square. - _R. J. Mathar_, Jun 07 2020

Craig Knecht, Polyominoes enumeration
Craig Knecht, Connective polyominoes 3x3
R. J. Mathar, Corrigendum to "Polyomino Enumeration Results (Parkin et al, SIAM Fall Meeting 1967)" viXra:1905.0474 (2019)
R. Parkin, L. J. Lander, and D. R. Parkin, Polyomino Enumeration Results, presented at SIAM Fall Meeting, 1967, and accompanying letter from T. J. Lander (annotated scanned copy) page 9 (incorrect at n=15).
Wikipedia, Connective Polyominoes 4x4
Wikipedia, Connective Polyominoes 5x5
Wikipedia, Connective polyominoes with 4 sym-axis
Wikipedia, Pond larger than a lake
Wikipedia, Water Retention on Mathematical Surfaces
Index entries for sequences related to polyominoes

Cf. A054247 (all unique water retention patterns). Diagonal of A268371.

Cf. A259088.

a(6) corrected. Craig Knecht, May 25 2020

A054739 Number of inequivalent n X n matrices over GF(3) under action of dihedral group of the square D_4.

Original entry on oeis.org

1, 3, 21, 2862, 5398083, 105918450471, 18761832172500795, 29912416165371498901002, 429210477536602279123636967061, 55428311030379722725246681652572022523, 64422190091501416379601522735200323789074174081, 673878862467911703904942451533575765568815772023224550102

Offset: 0

Vladeta Jovovic, May 15 2000

Andrew Howroyd, Table of n, a(n) for n = 0..25

Column k=3 of A343097.

Cf. A054247.

Join[{1, 3}, Table[CycleIndexPolynomial[
    GraphData[{"Grid", {n, n}}, "AutomorphismGroup"],
    Table[Subscript[s, i], {i, 1, 4}]] /.
Table[Subscript[s, i] -> 3, {i, 1, 4}], {n, 2, 10}]]
(* Geoffrey Critzer, Aug 09 2016 *)

a(n) = (1/8)*(3^(n^2) + 2*3^(n^2/4) + 3*3^(n^2/2) + 2*3^((n^2+n)/2)) if n is even;

a(n) = (1/8)*(3^(n^2) + 2*3^((n^2+3)/4) + 3^((n^2+1)/2) + 4*3^((n^2+n)/2)) if n is odd. [corrected by Chris Hallstrom, Mar 22 2021]

Terms a(10) and beyond from Andrew Howroyd, Apr 15 2021

cp's OEIS Frontend

A177793 Partial sums of A054247.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

Extensions

A014409 Number of inequivalent ways (mod D_4) a pair of checkers can be placed on an n X n board.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions

A054252 Triangle T(n,k) of n X n binary matrices with k=0..n^2 ones under action of dihedral group of the square D_4.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Sage

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.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

Formula

A343097 Array read by antidiagonals: T(n,k) is the number of k-colorings of an n X n grid, up to rotations and reflections.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A047937 Number of 2-colorings of an n X n grid, up to rotational symmetry.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A082963 Number of n X n 0-1 matrices with half 1's and half 0's (rounded up/down if odd).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

Extensions

A255016 Number of toroidal n X n binary arrays, allowing rotation and/or reflection of rows and/or columns as well as matrix transposition.