cp's OEIS Frontend

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.

%I A216675 #32 Nov 08 2023 01:47:10
%S A216675 0,4,0,1296,0,45265984,0,168709341081856,0,66865709036047973991424,0,
%T A216675 2815414274858422422282241600000000,0,
%U A216675 12589335654221209921194197564847684000000000000,0,5977481098898922857923760209743284068237948337696882106105856,0
%N 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.
%C A216675 "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).
%C A216675 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_.)
%C A216675 From _Adam P. Goucher_, Aug 01 2013: (Start)
%C A216675 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.
%C A216675 Also the square of the number of domino tilings of an n X n chessboard.
%C A216675 (End)
%H A216675 Alois P. Heinz, <a href="/A216675/b216675.txt">Table of n, a(n) for n = 1..50</a> (terms n = 1..30 from Adam P. Goucher)
%H A216675 Project Euler, <a href="http://projecteuler.net/problem=393">Problem 393: Migrating ants</a>.
%F A216675 a(2n) = A004003(n)^2; a(2n + 1) = 0. - _Adam P. Goucher_, Aug 01 2013
%e A216675 For a 1 X 1 grid, there is no such possibility.
%e A216675 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.
%e A216675 For a 3 X 3 grid, there is no possibility, neither for a 5 X 5 grid.
%t A216675 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 *)
%o A216675 (Python)
%o A216675 from sympy.abc import x
%o A216675 from sympy import resultant, chebyshevu, I
%o A216675 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
%Y A216675 See A216678 for the same problem with an additional constraint ("no 2-loops").
%Y A216675 Cf. A216796-A216800 for more general n X k grids.
%K A216675 nonn
%O A216675 1,2
%A A216675 _M. F. Hasler_, Sep 13 2012
%E A216675 Terms beyond a(5) from _R. H. Hardin_, Sep 15 2012
%E A216675 Terms beyond a(8) from _Adam P. Goucher_, Aug 01 2013