login
A239576
Number of non-equivalent (mod D_4) binary n X n matrices with 4 pairwise nonadjacent 1's.
4
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,2
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.
LINKS
Index entries for linear recurrences with constant coefficients, signature (4,-1,-16,19,20,-45,0,45,-20,-19,16,1,-4,1)
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
EXAMPLE
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]
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 *)
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Heinrich Ludwig, Mar 28 2014
STATUS
approved