A229430 Number of ways to label the cells of a 2 X n grid such that no (orthogonally) adjacent cells have adjacent labels.

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

Andrew Howroyd, Table of n, a(n) for n = 0..100

F. C. Holroyd and W. J. G. Wingate, Cycles in the complement of a tree or other graph, Discrete Math., 55 (1985), 267-282.

Andrew Howroyd, Worked Solution and Formula

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

Adjacent sequences: A229427 A229428 A229429 * A229431 A229432 A229433

Keyword

nonn

Author

Jens Voß, Sep 23 2013

Extensions

Terms a(9) and beyond from Andrew Howroyd, Feb 14 2020

Status

approved