OFFSET
1,2
COMMENTS
"Adjacent" is meant in the sense of von Neumann neighborhoods (4 neighbors for "interior" nodes, 3 resp. 2 for nodes on the borders resp. in the corners).
Alternate definition: Number of permutations of an n X n array with each element moving exactly one step horizontally or vertically. (Suggested by R. H. Hardin.)
From Adam P. Goucher, Aug 01 2013: (Start)
Also the permanent of the adjacency matrix of the n X n grid graph, which is the determinant of the modified adjacency matrix where vertical and horizontal edges have weights of 1 and i, respectively.
Also the square of the number of domino tilings of an n X n chessboard.
(End)
LINKS
Alois P. Heinz, Table of n, a(n) for n = 1..50 (terms n = 1..30 from Adam P. Goucher)
Project Euler, Problem 393: Migrating ants.
FORMULA
a(2n) = A004003(n)^2; a(2n + 1) = 0. - Adam P. Goucher, Aug 01 2013
EXAMPLE
For a 1 X 1 grid, there is no such possibility.
For a 2 X 2 grid, on can draw arrows between 2 pairs of nodes in horizontal or vertical sense, and the clockwise and counterclockwise cyclic "permutation" of the 4 nodes.
For a 3 X 3 grid, there is no possibility, neither for a 5 X 5 grid.
MATHEMATICA
Table[If[Mod[n, 2]==0, Det[MapIndexed[(#1 I^Mod[Total[#2], 2])&, Normal[AdjacencyMatrix[GridGraph[{n, n}]]], {2}]], 0], {n, 1, 20}] (* Adam P. Goucher, Aug 01 2013 *)
PROG
(Python)
from sympy.abc import x
from sympy import resultant, chebyshevu, I
def A216675(n): return 0 if n&1 else resultant(chebyshevu(n, x/2), chebyshevu(n, I*x/2)) # Chai Wah Wu, Nov 07 2023
CROSSREFS
KEYWORD
nonn
AUTHOR
M. F. Hasler, Sep 13 2012
EXTENSIONS
Terms beyond a(5) from R. H. Hardin, Sep 15 2012
Terms beyond a(8) from Adam P. Goucher, Aug 01 2013
STATUS
approved