A239576 Number of non-equivalent (mod D_4) binary n X n matrices with 4 pairwise nonadjacent 1's.

0, 3, 62, 683, 4015, 16989, 56196, 158271, 391917, 882683, 1836106, 3587103, 6638267, 11747613, 19985680, 32879339, 52490521, 81638211, 124000342, 184440963, 269135111, 386033453, 545007772, 758491143, 1041639045, 1413189339, 1895630946, 2516334551, 3307717267

Offset: 2

Author

Heinrich Ludwig, Mar 28 2014

Keywords

• nonn
• easy

Comments

Also number of non-equivalent ways to place 4 non-attacking wazirs on an n X n board.

Two matrix elements are considered adjacent, if the difference of their row indices is 1 and the column indices are equal, or vice versa (von Neumann neighborhood).

Without the restriction "non-equivalent (mod D_4)" numbers are given by A172227.

Examples

			There are a(3) = 3 non-equivalent binary 3 X 3 matrices with 4 pairwise nonadjacent 1s (x):
  [0 1 0]    [1 0 1]    [1 0 1]
  |1 0 1|    |0 1 0|    |0 0 0|
  [0 1 0]    [1 0 0]    [1 0 1]
		

Links

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

Crossrefs

Cf. A232569, A232568, A232567, A172227.

Programs

Mathematica

Flatten[{0,Table[(n^8-30*n^6+24*n^5+352*n^4-576*n^3-1280*n^2+3360*n-1536+If[EvenQ[n],0,(14*n^4-72*n^3+226*n^2-624*n+717)])/192,{n,3,20}]}] (* Vaclav Kotesovec after Heinrich Ludwig, Mar 28 2014 *)
Drop[CoefficientList[Series[-x^2 - x^2*(1 - x + 51*x^2 + 454*x^3 + 1374*x^4 + 2527*x^5 + 1990*x^6 + 634*x^7 - 347*x^8 - 49*x^9 + 87*x^10 + 16*x^11 - 20*x^12 + 3*x^13) / ((-1+x)^9*(1+x)^5), {x, 0, 20}], x],2] (* Vaclav Kotesovec, Mar 29 2014 *)

Formula

a(n) = (n^8 -30*n^6 +24*n^5 +352*n^4 -576*n^3 -1280*n^2 +3360*n -1536 + IF(n==1 mod 2)*(14*n^4 -72*n^3 +226*n^2 -624*n +717))/192; n>=3.

G.f.: -x^2 - x^2*(1 - x + 51*x^2 + 454*x^3 + 1374*x^4 + 2527*x^5 + 1990*x^6 + 634*x^7 - 347*x^8 - 49*x^9 + 87*x^10 + 16*x^11 - 20*x^12 + 3*x^13) / ((-1+x)^9*(1+x)^5). - Vaclav Kotesovec, Mar 29 2014