login
A229430
Number of ways to label the cells of a 2 X n grid such that no (orthogonally) adjacent cells have adjacent labels.
4
1, 0, 0, 24, 1660, 160524, 21914632, 4065598248, 987830372684, 304870528356476, 116578000930637000, 54116343193686469960, 29984241542575292762940, 19548555813018460134901516, 14815308073366437897483622056, 12915964646307201385492841052040
OFFSET
0,4
COMMENTS
a(n) is the number of Hamiltonian paths in the complement of the n-ladder graph. - Andrew Howroyd, Feb 14 2020
LINKS
F. C. Holroyd and W. J. G. Wingate, Cycles in the complement of a tree or other graph, Discrete Math., 55 (1985), 267-282.
Eric Weisstein's World of Mathematics, Ladder Graph
Eric Weisstein's World of Mathematics, Hamiltonian Path
EXAMPLE
The A(3) = 24 valid labelings of a 2 X 3 grid are
153 163 135 513 415 416
426 425 462 246 263 253
together with their 18 reflections and rotations.
PROG
(PARI) seq(n)={my(gf=(1 - x)*(1 + (3*y - 2)*x + (y + 1)*x^2)/(1 + (-y^2 + 5*y - 3)*x + (y^3 - 3*y^2 + 3)*x^2 + (-2*y^3 + 5*y^2 - 3*y - 1)*x^3 + (y^3 - y^2 + 2*y)*x^4)); [subst(serlaplace(p*y^0), y, 1) | p <- Vec(gf + O(x*x^n))]} \\ Andrew Howroyd, Feb 16 2020
CROSSREFS
Row n=2 of A229429.
Cf. A002464.
Sequence in context: A333042 A112389 A187634 * A054777 A301392 A084224
KEYWORD
nonn
AUTHOR
Jens Voß, Sep 23 2013
EXTENSIONS
Terms a(9) and beyond from Andrew Howroyd, Feb 14 2020
STATUS
approved