login
Square array T(n,k), n >= 1, k >= 1, read by antidiagonals, where T(n,k) is the number of Hamiltonian paths in an n X k grid starting at the lower left corner and finishing in the upper right corner.
10

%I #27 Jan 31 2022 15:51:21

%S 1,1,1,1,0,1,1,1,1,1,1,0,2,0,1,1,1,4,4,1,1,1,0,8,0,8,0,1,1,1,16,20,20,

%T 16,1,1,1,0,32,0,104,0,32,0,1,1,1,64,111,378,378,111,64,1,1,1,0,128,0,

%U 1670,0,1670,0,128,0,1,1,1,256,624,6706,10204,10204,6706,624,256,1,1

%N Square array T(n,k), n >= 1, k >= 1, read by antidiagonals, where T(n,k) is the number of Hamiltonian paths in an n X k grid starting at the lower left corner and finishing in the upper right corner.

%H Andrew Howroyd, <a href="/A333580/b333580.txt">Table of n, a(n) for n = 1..378</a>

%H <a href="/index/Gra#graphs">Index entries for sequences related to graphs, Hamiltonian</a>

%F T(n,k) = T(k,n).

%e Square array T(n,k) begins:

%e 1, 1, 1, 1, 1, 1, 1, 1, ...

%e 1, 0, 1, 0, 1, 0, 1, 0, ...

%e 1, 1, 2, 4, 8, 16, 32, 64, ...

%e 1, 0, 4, 0, 20, 0, 111, 0, ...

%e 1, 1, 8, 20, 104, 378, 1670, 6706, ...

%e 1, 0, 16, 0, 378, 0, 10204, 0, ...

%e 1, 1, 32, 111, 1670, 10204, 111712, 851073, ...

%e 1, 0, 64, 0, 6706, 0, 851073, 0, ...

%o (Python)

%o # Using graphillion

%o from graphillion import GraphSet

%o import graphillion.tutorial as tl

%o def A333580(n, k):

%o if n == 1 or k == 1: return 1

%o universe = tl.grid(n - 1, k - 1)

%o GraphSet.set_universe(universe)

%o start, goal = 1, k * n

%o paths = GraphSet.paths(start, goal, is_hamilton=True)

%o return paths.len()

%o print([A333580(j + 1, i - j + 1) for i in range(12) for j in range(i + 1)])

%Y Rows n=1..10 (with 0 omitted) give: A000012, A000035, A011782(n-1), A014523, A014584, A333581, A333582, A333583, A333584, A333585.

%Y T(2*n-1,2*n-1) gives A001184(n-1).

%Y Cf. A271592.

%K nonn,tabl

%O 1,13

%A _Seiichi Manyama_, Mar 27 2020