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

Author

Jens Voß, Sep 23 2013

Keywords

• nonn

Comments

a(n) is the number of Hamiltonian paths in the complement of the n-ladder graph. - Andrew Howroyd, Feb 14 2020

Examples

			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.
		

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

Crossrefs

Row n=2 of A229429.

Cf. A002464.

Programs

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

Extensions

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