A216675 Number of ways one can draw arrows between adjacent nodes of an n X n grid such that each node has one outgoing and one incoming arrow.

0, 4, 0, 1296, 0, 45265984, 0, 168709341081856, 0, 66865709036047973991424, 0, 2815414274858422422282241600000000, 0, 12589335654221209921194197564847684000000000000, 0, 5977481098898922857923760209743284068237948337696882106105856, 0

Offset: 1

Author

M. F. Hasler, Sep 13 2012

Keywords

• nonn

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)

Examples

			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.
		

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.

Crossrefs

See A216678 for the same problem with an additional constraint ("no 2-loops").

Cf. A216796-A216800 for more general n X k grids.

Programs

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

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

Formula

a(2n) = A004003(n)^2; a(2n + 1) = 0. - Adam P. Goucher, Aug 01 2013

Extensions

Terms beyond a(5) from R. H. Hardin, Sep 15 2012

Terms beyond a(8) from Adam P. Goucher, Aug 01 2013