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

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

Author

Seiichi Manyama, Mar 28 2020

Keywords

• nonn
• easy
• walk

Links

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

Crossrefs

Row n=6 of A271592.

Cf. A333581.

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

Formula

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

Extensions

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