A047937 -id:A047937 - cp's OEIS frontend

A343095 Array read by antidiagonals: T(n,k) is the number of k-colorings of an n X n grid, up to rotational symmetry.

1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 3, 6, 1, 0, 1, 4, 24, 140, 1, 0, 1, 5, 70, 4995, 16456, 1, 0, 1, 6, 165, 65824, 10763361, 8390720, 1, 0, 1, 7, 336, 489125, 1073758336, 211822552035, 17179934976, 1, 0, 1, 8, 616, 2521476, 38147070625, 281474993496064, 37523658921114744, 140737496748032, 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           24              70               165 ...
  3 | 0 1     140         4995           65824            489125 ...
  4 | 0 1   16456     10763361      1073758336       38147070625 ...
  5 | 0 1 8390720 211822552035 281474993496064 74505806274453125 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..860
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.

Rows 0..5 are A000012, A001477, A006528, A282613, A283027, A283031.
Columns 0..10 are A000007, A000012, A047937, A047938, A047939, A047940, A047941, A047942, A047943, A047944, A047945.
Main diagonal is A343096.
Cf. A182406, A246106, A343097, A343874.

{{1}}~Join~Table[Function[n, (k^(n^2) + 2*k^((n^2 + 3 #)/4) + k^((n^2 + #)/2))/4 &[Mod[n, 2] ] ][m - k + 1], {m, 0, 8}, {k, m + 1, 0, -1}] // Flatten (* Michael De Vlieger, Nov 30 2023 *)

T(n,k) = (k^(n^2) + 2*k^((n^2 + 3*(n%2))/4) + k^((n^2 + (n%2))/2))/4

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

A054772 Triangle T(n,k) of n X n binary matrices with k=0..n^2 ones, up to rotational symmetry.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 10, 22, 34, 34, 22, 10, 3, 1, 1, 4, 32, 140, 464, 1092, 2016, 2860, 3238, 2860, 2016, 1092, 464, 140, 32, 4, 1, 1, 7, 78, 578, 3182, 13302, 44330, 120230, 270525, 510875, 817388, 1114548, 1300316, 1300316, 1114548, 817388

Offset: 0

Vladeta Jovovic, May 18 2000

Row sums give A047937.
From Wolfdieter Lang, Oct 01 2016: (Start)
The formula is obtained from Pólya's counting theorem. See, e.g., the Harary-Palmer reference.
The cycle index for a square grid of n X n  squares G(n), n >= 1, under the cyclic group C_4 is
  (s[1]^(n^2)+s[2]^(n^2/2)+2*s[4]^(n^2/4))/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))/4 if n is odd. (Numerate the squares from 1 .. n^2 and compute for the C_4 rotations the cycle structure of the permutation from the symmetric group S(n^2)).
The figure counting series is c(x) = 1+x for coloring, say black and white (in the matrix case binary entries).
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. (End)
A pedantic note: One should not use 0,1 matrices for this T(n,k) model because 1 (also |) is not C_4 invariant. Square grids with coloring of the squares, say black and white, or central entries o and + are better suited. - Wolfdieter Lang, Oct 02 2016

			[1],[1,1],[1,1,2,1,1],[1,3,10,22,34,34,22,10,3,1],...;
There are 10 inequivalent 3 X 3 binary matrices with 2 ones, up to rotational symmetry:
[0 0 0] [0 0 0] [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] [1 1 0] [0 1 0] [1 0 0]
-------
[0 0 0] [0 0 0] [0 0 0] [0 0 0] [0 0 1]
[0 1 0] [0 1 0] [1 0 0] [1 0 1] [0 0 0]
[0 0 1] [0 1 0] [0 0 1] [0 0 0] [1 0 0].
- reformatted. _Wolfdieter Lang_, Oct 01 2016
See a remark above: use o for 0 and + for 1.
n=3: Cycle index G(3) = s[1]*(s[1]^8 + s[2]^4 + 2*s[4]^2)/4. C(3,x) = (1+x)*((1+x)^8 + (1+x^2)^4 + 2*(1+x^4)^2)/4 = 1 + 3*x + 10*x^2 + 22*x^3 + 34*x^4 + 34*x^5 + 22*x^6 + 10*x^7 + 3*x^8 + x^9. - _Wolfdieter Lang_, Oct 01 2016

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

Cf. A054252, columns k=0..4: A000012, A004652, A212714, A011863, A275799.

See the comment above: T(n,k) = [x^k]C(n,x), with the counting series C(n,x) obtained from the cycle index for the n X n grid under C_4 rotations G(n;s[1],s[2],s[4]) with s[2^j] = 1 + x^(2^j) for j=0,1,2. - Wolfdieter Lang, Oct 01 2016

A047938 Number of ways to label points of an n X n grid with 3 colors, up to rotational symmetry.

Original entry on oeis.org

1, 3, 24, 4995, 10763361, 211822552035, 37523658921114744, 59824832307866205347043, 858420955073128584419531008641, 110856622060759442496180656754310346403, 128844380183002832759115461915902241562318377784, 1347757724935823407809884872163997148505019182125807296675

Offset: 0

Rob Pratt

nonn

Labels of adjacent points need not be distinct.

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

Column k=3 of A343095.
See A068253 for number of proper colorings.
Cf. A054739, A047937, A047939.

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

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

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

Original entry on oeis.org

2, 23, 5605504, 768614338020786176, 1772303994379887844373479205703254016, 4388012152856549445746584486819723041078276071004502223505850368, 746581580725934736852480760189481426040548499078234470565449222456544381939194522144498021170453413888

Offset: 1

Paul Oelkers, Sep 08 2020

nonn

The cycle index of the permutation group is given by:
Even n: (1/24)*(s_1^n^3 + 8*s_1^n*s_3^((n^3-n)/3) + 6*s_2^(n^3/2) + 6*s_4^(n^3/4) + 3*s_2^(n^3/2));
Odd n: (1/24)*(s_1^n^3 + 8*s_1^n*s_3^((n^3-n)/3) + 6*s_1^n*s_2^((n^3-n)/2) + 6*s_1^n*s_4^((n^3-n)/4) + 3*s_1^n*s_2^((n^3-n)/2)).

			a(2)=23 from:
  00 00
  00 00
------------------------------------------
  10 00
  00 00
------------------------------------------
  11 00   10 00   10 01   10 00
  00 00   01 00   00 00   00 01
------------------------------------------
  11 00   11 00   01 10
  10 00   00 10   10 00
------------------------------------------
  11 00   11 00   01 10   11 00   11 10
  11 00   10 01   10 01   00 11   10 00
------------------------------------------
  00 11   00 11   10 01
  01 11   11 01   01 11
------------------------------------------
  00 11   01 11   01 10   01 11
  11 11   10 11   11 11   11 10
------------------------------------------
  01 11
  11 11
------------------------------------------
  11 11
  11 11
------------------------------------------
An example for the 2-coloring of the 3 X 3 X 3 grid can be written as:
  110 000 111
  100 000 111
  100 000 111
This coloring is equivalent to:
  111 000 111
  001 000 111
  000 000 111
  because you can get this configuration by rotating the first coloring by 90 degrees.
But it is different from:
  011 000 111
  001 000 111
  001 000 111
  because reflections are not considered.

Wikipedia, Cycle index
Paul Oelkers, Hand written notes and sketches

This is the three-dimensional version of A047937.

Cf. A000543.

a(n) = (1/24)*(2^n^3 + 6*2^((n^3)/4) + 9*2^((n^3)/2) + 8*2^((n^3-n)/3+n)) for n even;

a(n) = (1/24)*(2^n^3 + 6*2^(((n^3)-n)/4+n) + 9*2^(((n^3)-n)/2+n) + 8*2^(((n^3-n)/3)+n)) for n odd.

More terms from Stefano Spezia, Sep 09 2020

A047939 Number of 4-colorings of an n X n grid, up to rotational symmetry.

Original entry on oeis.org

1, 4, 70, 65824, 1073758336, 281474993496064, 1180591620734591303680, 79228162514264619068554215424, 85070591730234615870455337878516924416, 1461501637330902918203686041642102636484130504704, 401734511064747568885490523085607563280607806359022338048000

Offset: 0

Rob Pratt

nonn

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

Column k=4 of A343095.

Cf. A054751, A047937.

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

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

A047940 Number of 5-colorings of an n X n grid, up to rotational symmetry.

Original entry on oeis.org

1, 5, 165, 489125, 38147070625, 74505806274453125, 3637978807092666626953125, 4440892098500626236200333251953125, 135525271560688054250937420874834136962890625, 103397576569128459358926086520114040467888355255126953125

Offset: 0

Rob Pratt

nonn

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

Column k=5 of A343095.

Cf. A054752, A047937.

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

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

A047941 Number of 6-colorings of an n X n grid, up to rotational symmetry.

Original entry on oeis.org

1, 6, 336, 2521476, 705277897416, 7107572010747738816, 2578606199622659276537193216, 33678386561031835867238388699701784576, 15835071665743319426540573726368249140484891508736, 268034865369025581797148715934176748584236925114472848300179456

Offset: 0

Rob Pratt

nonn

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

Column k=6 of A343095.

Cf. A047937.

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

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

A047942 Number of 7-colorings of an n X n grid, up to rotational symmetry.

Original entry on oeis.org

1, 7, 616, 10092775, 8308234084801, 335267154940213889575, 662932711464913775048175499816, 64230894380264719522488136461023341060807, 304940121908958925034643465916849873749900601574419201, 70938377295002676956115265690779190293441720530070400876280330568007

Offset: 0

Rob Pratt

nonn

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

Column k=7 of A343095.

Cf. A047937.

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

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

A047943 Number of 8-colorings of an n X n grid, up to rotational symmetry.

Original entry on oeis.org

1, 8, 1044, 33562880, 70368748374016, 9444732965876730429440, 81129638414606686199388699623424, 44601490397061246283080881278262737180295168, 1569275433846670190958947355821723644654155086251882971136

Offset: 0

Rob Pratt

nonn

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

Column k=8 of A343095.

Cf. A047937.

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

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

A047944 Number of 9-colorings of an n X n grid, up to rotational symmetry.

Original entry on oeis.org

1, 9, 1665, 96870249, 463255057977921, 179474496923598616041129, 5632099886234793640483695986653185, 14316042242555870306568544190208626253583093449, 2947546144434645792880218215353988087374626027116634833972481

Offset: 0

Rob Pratt

nonn

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

Column k=9 of A343095.

Cf. A047937.

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

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

cp's OEIS Frontend

A343095 Array read by antidiagonals: T(n,k) is the number of k-colorings of an n X n grid, up to rotational symmetry.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A054772 Triangle T(n,k) of n X n binary matrices with k=0..n^2 ones, up to rotational symmetry.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Formula

A047938 Number of ways to label points of an n X n grid with 3 colors, up to rotational symmetry.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A047939 Number of 4-colorings of an n X n grid, up to rotational symmetry.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A047940 Number of 5-colorings of an n X n grid, up to rotational symmetry.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A047941 Number of 6-colorings of an n X n grid, up to rotational symmetry.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A047942 Number of 7-colorings of an n X n grid, up to rotational symmetry.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A047943 Number of 8-colorings of an n X n grid, up to rotational symmetry.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions