A271592 Array read by antidiagonals: T(n,m) = number of directed Hamiltonian walks from NW to SW corners on a grid with n rows and m columns.

1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 2, 1, 1, 0, 1, 0, 4, 0, 1, 0, 1, 4, 8, 8, 1, 1, 0, 1, 0, 23, 0, 16, 0, 1, 0, 1, 8, 55, 86, 47, 32, 1, 1, 0, 1, 0, 144, 0, 397, 0, 64, 0, 1, 0, 1, 16, 360, 948, 1770, 1584, 264, 128, 1, 1, 0, 1, 0, 921, 0, 11658, 0, 6820, 0, 256, 0, 1

Offset: 1

Author

Andrew Howroyd, Apr 10 2016

Keywords

• nonn
• tabl

Examples

			The start of the sequence as table:
* 1 0   0   0     0     0       0       0          0 ...
* 1 1   1   1     1     1       1       1          1 ...
* 1 0   2   0     4     0       8       0         16 ...
* 1 1   4   8    23    55     144     360        921 ...
* 1 0   8   0    86     0     948       0      10444 ...
* 1 1  16  47   397  1770   11658   59946     359962 ...
* 1 0  32   0  1584     0   88418       0    4999752 ...
* 1 1  64 264  6820 52387  909009 8934966  130373192 ...
* 1 0 128   0 28002     0 7503654       0 2087813834 ...
* ...
		

Links

• Andrew Howroyd, Antidiagonals n = 1..27, flattened

Crossrefs

Column 4 is aerated A014524, column 5 is A014585.

Rows include A181688, A181689.

Main diagonal is A000532.

Cf. A333580.

Programs

Python

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

Formula

T(n,m)=0 for n odd and m even, T(1,n)=0 for n>1.

T(2,n)=T(n,1)=T(2*n,2)=1, T(3,2*n+1)=T(n+1,3)=2^n.