A333580 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.

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, 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, 1670, 0, 1670, 0, 128, 0, 1, 1, 1, 256, 624, 6706, 10204, 10204, 6706, 624, 256, 1, 1

Offset: 1

Author

Seiichi Manyama, Mar 27 2020

Keywords

• nonn
• tabl

Examples

			Square array T(n,k) begins:
  1, 1,  1,   1,    1,     1,      1,      1, ...
  1, 0,  1,   0,    1,     0,      1,      0, ...
  1, 1,  2,   4,    8,    16,     32,     64, ...
  1, 0,  4,   0,   20,     0,    111,      0, ...
  1, 1,  8,  20,  104,   378,   1670,   6706, ...
  1, 0, 16,   0,  378,     0,  10204,      0, ...
  1, 1, 32, 111, 1670, 10204, 111712, 851073, ...
  1, 0, 64,   0, 6706,     0, 851073,      0, ...
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..378
• Index entries for sequences related to graphs, Hamiltonian

Crossrefs

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

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

Cf. A271592.

Programs

Python

# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A333580(n, k):
    if n == 1 or k == 1: return 1
    universe = tl.grid(n - 1, k - 1)
    GraphSet.set_universe(universe)
    start, goal = 1, k * n
    paths = GraphSet.paths(start, goal, is_hamilton=True)
    return paths.len()
print([A333580(j + 1, i - j + 1) for i in range(12) for j in range(i + 1)])

Formula

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