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,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

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

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

Sequence in context: A013452 A013453 A012688 * A012502 A130105 A013463

Adjacent sequences: A216672 A216673 A216674 * A216676 A216677 A216678

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