A216800 -id:A216800 - cp's OEIS frontend

A216678 On an n X n grid, number of ways to draw arrows between adjacent nodes such that each node has one outgoing and one incoming arrow, of which the one is not the opposite of the other (i.e., without 2-loops).

0, 2, 0, 88, 0, 207408, 0, 22902801416, 0, 112398351350823112, 0, 24075116871728596710774372

Offset: 1

M. F. Hasler, Sep 13 2012

"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).

Or: Number of permutations of an n X n array, with each element moving exactly one horizontally or vertically and without 2-loops.

			For a 1 X 1 grid, there is no such permutation or possibility.
For a 2 X 2 grid, on has the clockwise and counterclockwise cyclic "permutation" of the 4 nodes. (It is not allowed to draw arrows between 2 pairs of nodes in horizontal or vertical sense since, e.g., the arrow from the first to the second node is the opposite of the arrow from the second to the first node.)
For a 3 X 3 grid, there is no possibility, neither for a 5 X 5 grid.

Project Euler, Problem 393: Migrating ants.

See A216675 for the same problem without the additional restriction.

Cf. A216796, A216797, A216798, A216799, A216800 for more general n X k grids.

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

A216796 Number of permutations of an n X 4 array with each element moving exactly one horizontally or vertically and without 2-loops.

Original entry on oeis.org

0, 6, 8, 88, 292, 1774, 7676, 39844, 186996, 927134, 4460016, 21812696, 105716132, 514912230, 2501152692, 12167375908, 59142175940, 287602784246, 1398239939960, 6798750327544, 33055539575012, 160722650037822, 781448253270316

Offset: 1

R. H. Hardin, Sep 17 2012

nonn

Column 4 of A216800.

			Some solutions for n=4:
..4..0..3..7....4..0..3..7....1..2..3..7....1..5..3..7....4..0..1..2
..5..1..2.11....5..1..2.11....0..9..5..6....0..4..2.11....8..6..7..3
.12..8..6.15....9.13..6.15....4.10.11.15....9.10..6.15...12..5.11.15
.13..9.10.14....8.12.10.14....8.12.13.14....8.12.13.14...13..9.10.14

R. H. Hardin, Table of n, a(n) for n = 1..210

Cf. A216800.

Empirical: a(n) = 4*a(n-1) +10*a(n-2) -28*a(n-3) -7*a(n-4) +30*a(n-5) -8*a(n-6).

Empirical g.f.: 2*x^2*(1 - 2*x)*(3 - 2*x - 6*x^2 + 2*x^3) / ((1 - x)*(1 - 3*x - 13*x^2 + 15*x^3 + 22*x^4 - 8*x^5)). - Colin Barker, Feb 23 2018

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.

Original entry on oeis.org

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

Offset: 1

M. F. Hasler, Sep 13 2012

nonn

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

			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.

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.

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

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

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

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

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

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

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

A216797 Number of permutations of an n X 5 array with each element moving exactly one horizontally or vertically and without 2-loops.

Original entry on oeis.org

0, 10, 0, 292, 0, 10140, 0, 361200, 0, 12911864, 0, 461788640, 0, 16516859104, 0, 590766585904, 0, 21130267285488, 0, 755777826856944, 0, 27032319708816080, 0, 966879797484085808, 0, 34582919761038885136, 0, 1236946249622251150000, 0

Offset: 1

R. H. Hardin, Sep 17 2012

nonn

Column 5 of A216800.

			Some solutions for n=4:
..1..2..7..8..3....5..0..1..4..9....5..0..3..4..9....1..6..7..2..3
..0..5..6..9..4...10..7..2..3.14....6..1..2.13..8....0..5..8..9..4
.11.12.13.14.19...15..6.13..8.19...11.12..7.14.19...15.10.11.14.19
.10.15.16.17.18...16.11.12.17.18...10.15.16.17.18...16.17.12.13.18

R. H. Hardin, Table of n, a(n) for n = 1..210

Cf. A216800.

Empirical: a(n) = 49*a(n-2) - 524*a(n-4) + 1862*a(n-6) - 1728*a(n-8).

Empirical g.f.: 2*x^2*(5 - 99*x^2 + 536*x^4 - 636*x^6) / (1 - 49*x^2 + 524*x^4 - 1862*x^6 + 1728*x^8). - Colin Barker, Mar 09 2018

A216798 Number of permutations of an nX6 array with each element moving exactly one horizontally or vertically and without 2-loops.

Original entry on oeis.org

0, 22, 32, 1774, 10140, 207408, 1879040, 27918806, 302667484, 3991662992, 46492284664, 585384941184, 7016484369112, 86745644666352, 1051690689056356, 12908451995027824, 157213197102215752, 1924102649175445120

Offset: 1

R. H. Hardin Sep 17 2012

nonn

Column 6 of A216800

			Some solutions for n=4
..6..0..3..9..5.11....1..7..3..4..5.11....6..0..1..9..3..4....6..0..1..2..3..4
.12..1..2..8..4.10....0..6..2..8..9.10....7..8..2.10.16..5...12.13..7.10.16..5
.18..7.13.14.15.16...13.19.15.21.22.16...18.12.20.14.22.11...18.14..8..9.15.11
.19.20.21.22.23.17...12.18.14.20.23.17...19.13.21.15.23.17...19.20.21.22.23.17

R. H. Hardin, Table of n, a(n) for n = 1..210

Empirical: a(n) = 9*a(n-1) +126*a(n-2) -895*a(n-3) -4784*a(n-4) +31216*a(n-5) +75941*a(n-6) -508196*a(n-7) -548324*a(n-8) +4278056*a(n-9) +1798234*a(n-10) -19820128*a(n-11) -2095562*a(n-12) +51982908*a(n-13) -985124*a(n-14) -76511412*a(n-15) +2082320*a(n-16) +59525536*a(n-17) +1713536*a(n-18) -20262336*a(n-19) -1935616*a(n-20) +1498112*a(n-21) +94208*a(n-22) -32768*a(n-23)

A216799 Number of permutations of an n X 7 array with each element moving exactly one horizontally or vertically and without 2-loops.

Original entry on oeis.org

0, 42, 0, 7676, 0, 1879040, 0, 489300384, 0, 129127695440, 0, 34175930646380, 0, 9050948918328308, 0, 2397326535775801848, 0, 634999208667955702740, 0, 168198450029830487388264, 0, 44552431219619052902569084, 0

Offset: 1

R. H. Hardin, Sep 17 2012

nonn

Column 7 of A216800.

			Some solutions for n=4
..1..8..3..4..5..6.13....1..2..3..4.11.12..5....1..8..9..2..3.12..5
..0.15..2..9.10.11.12....0..7..8..9.10.19..6....0.15.10.11..4.19..6
..7.22.17.18.19.20.27...21.14.23.16.25.18.13....7.16.23.18.25.26.13
.14.21.16.23.24.25.26...22.15.24.17.26.27.20...14.21.22.17.24.27.20

R. H. Hardin, Table of n, a(n) for n = 1..210

Cf. A216800.

Empirical: a(n) = 567*a(n-2) -120178*a(n-4) +13765393*a(n-6) -990066780*a(n-8) +48491990634*a(n-10) -1700436524889*a(n-12) +44139613837223*a(n-14) -868138294952960*a(n-16) +13155428910825628*a(n-18) -155474518995038360*a(n-20) +1445657923554944027*a(n-22) -10640770515808065716*a(n-24) +62235780900370087070*a(n-26) -289748793743203750198*a(n-28) +1073469281138893045876*a(n-30) -3157120155190134617652*a(n-32) +7335560093801386722256*a(n-34) -13361939270615901600944*a(n-36) +18863902560832510398528*a(n-38) -20300073543284335116288*a(n-40) +16250247406671839253504*a(n-42) -9322542476450257133568*a(n-44) +3605527632911325986816*a(n-46) -838344981073030021120*a(n-48) +88164689346167832576*a(n-50).

cp's OEIS Frontend

A216678 On an n X n grid, number of ways to draw arrows between adjacent nodes such that each node has one outgoing and one incoming arrow, of which the one is not the opposite of the other (i.e., without 2-loops).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A216796 Number of permutations of an n X 4 array with each element moving exactly one horizontally or vertically and without 2-loops.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A216797 Number of permutations of an n X 5 array with each element moving exactly one horizontally or vertically and without 2-loops.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A216798 Number of permutations of an nX6 array with each element moving exactly one horizontally or vertically and without 2-loops.

Views

Author

Keywords

Comments

Examples

Links

Formula

A216799 Number of permutations of an n X 7 array with each element moving exactly one horizontally or vertically and without 2-loops.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula