A333581 -id:A333581 - cp's OEIS frontend

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

Seiichi Manyama, Mar 27 2020

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

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

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.

# 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)])

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

A333602 Number of directed Hamiltonian walks from NW to SW corners of a 6 X n grid.

Original entry on oeis.org

1, 1, 16, 47, 397, 1770, 11658, 59946, 359962, 1958968, 11341696, 63142224, 360314940, 2024278172, 11485023624, 64758162416, 366573071464, 2069908196378, 11706322628832, 66139560111600, 373914808423830, 2113066820134474, 11944325099736622, 67505931650135578

Offset: 1

Seiichi Manyama, Mar 28 2020

Andrew Howroyd, Table of n, a(n) for n = 1..500
Index entries for linear recurrences with constant coefficients, signature (5,14,-63,12,90,-35,-66,118,-8,-82,42,28,-4,2).

Row n=6 of A271592.

Cf. A333581.

# 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()
def A333602(n):
    return A271592(6, n)
print([A333602(n) for n in range(1, 10)])

a(n) = 5*a(n-1) + 14*a(n-2) - 63*a(n-3) + 12*a(n-4) + 90*a(n-5) - 35*a(n-6) - 66*a(n-7) + 118*a(n-8) - 8*a(n-9) - 82*a(n-10) + 42*a(n-11) + 28*a(n-12) - 4*a(n-13) + 2*a(n-14), n > 14. - Michael Gray, Jan 30 2022

G.f.: x*(1 - x)*(1 - 3*x - 6*x^2 + 10*x^3 - x^4 + 32*x^5 - 4*x^6 - 20*x^7 + 24*x^8 + 13*x^9 + 2*x^10 + 2*x^11)/(1 - 5*x - 14*x^2 + 63*x^3 - 12*x^4 - 90*x^5 + 35*x^6 + 66*x^7 - 118*x^8 + 8*x^9 + 82*x^10 - 42*x^11 - 28*x^12 + 4*x^13 - 2*x^14). - Andrew Howroyd, Jan 31 2022

a(20)-a(24) from Michael Gray, Jan 31 2022

cp's OEIS Frontend

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.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Python

Formula