A019318 -id:A019318 - cp's OEIS frontend

A173799 Partial sums of A019318.

1, 3, 19, 271, 7085, 251429, 10997806, 564316854, 33175912910, 2196968168590, 161790768056642, 13114202824936638, 1160158996141467678, 111226473580172327222, 11486922450679555836573

Offset: 1

Jonathan Vos Post, Feb 25 2010

nonn

Partial sums of number of inequivalent ways of choosing n squares from an n X n board, considering rotations and reflections to be the same.The subsequence of primes in this partial sum (unexpectedly dense at first) begins: 3, 19, 271, 251429, no more through a(20) yet 4 of the first 5 values after a(1).

			a(6) = 1 + 2 + 16 + 252 + 6814 + 244344 = 251429 is prime.

Cf. A019318, A054252, A014409.

a(n) = SUM[i=1..n] A019318(i) = SUM[i=1..n] {number of inequivalent ways of choosing i squares from an i X i board, considering rotations and reflections to be the same}.

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

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

A242279 Number of inequivalent (mod D_4) ways four checkers can be placed on an n X n board.

Original entry on oeis.org

1, 23, 252, 1666, 7509, 26865, 79920, 209096, 491425, 1064575, 2150076, 4104738, 7458437, 13005041, 21857984, 35598880, 56353185, 87019191, 131364700, 194364050, 282314901, 403316353, 567402672, 787201416, 1078078209, 1459020095, 1952782300, 2587048786, 3394568325

Offset: 2

Heinrich Ludwig, May 10 2014

Heinrich Ludwig, Table of n, a(n) for n = 2..1000
Index entries for linear recurrences with constant coefficients, signature (4,-1,-16,19,20,-45,0,45,-20,-19,16,1,-4,1).

Cf. A054252, A008805, A014409, A082966, A242358, A019318, A054772.

CoefficientList[Series[x^2*(1 + 19*x + 161*x^2 + 697*x^3 + 1446*x^4 + 2070*x^5 + 1422*x^6 + 766*x^7 + 105*x^8 + 31*x^9 + x^10 + x^11) / ((1-x)^9 * (1+x)^5), {x, 0, 20}], x] (* Vaclav Kotesovec, May 10 2014 *)
LinearRecurrence[{4,-1,-16,19,20,-45,0,45,-20,-19,16,1,-4,1},{0,0,1,23,252,1666,7509,26865,79920,209096,491425,1064575,2150076,4104738},40] (* Harvey P. Dale, May 06 2018 *)

a(n) = (n^8 - 6*n^6 + 40*n^4 - 48*n^3 + 16*n^2 + IF(MOD(n, 2) = 1)*(14*n^4 - 48*n^3 + 34*n^2 - 3))/192.
G.f.: x^2*(1 + 19*x + 161*x^2 + 697*x^3 + 1446*x^4 + 2070*x^5 + 1422*x^6 + 766*x^7 + 105*x^8 + 31*x^9 + x^10 + x^11) / ((1-x)^9 * (1+x)^5). - Vaclav Kotesovec, May 10 2014
a(n) = A054772(n, 4), n >= 2. - Wolfdieter Lang, Oct 03 2016

cp's OEIS Frontend

A173799 Partial sums of A019318.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

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

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

A242279 Number of inequivalent (mod D_4) ways four checkers can be placed on an n X n board.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula