OFFSET
1,3
COMMENTS
Wazir tours on a 4 X n grid. There are two closed loops for a 4x4 board, appearing as an H and a C, for example. - Ed Pegg Jr, Sep 07 2010
REFERENCES
F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.
Kwong, Y. H. H.; Enumeration of Hamiltonian cycles in P_4 X P_n and P_5 X P_n. Ars Combin. 33 (1992), 87-96.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
Huaide Cheng, Table of n, a(n) for n = 1..2473
Pablo Blanco and Doron Zeilberger, Counting (and Randomly Generating) Hamiltonian Cycles in Rectangular Grids, arXiv:2603.24315 [math.CO], 2026. See p. 2.
Frans Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Preliminary version of paper that appeared in Ars Combin. 49 (1998), 129-154.
Frans Faase, Counting Hamiltonian cycles in product graphs.
Frans Faase, Results from the counting program.
C. Flye Sainte-Marie, Manières différentes de tracer une route fermée ..., L'Intermédiaire des Mathématiciens, vol. 11 (1904), pp. 86-88 (in French).
George Jelliss, Wazir Wanderings
Ratko Tosic, Olga Bodroža-Pantić, Y. H. Harris Kwong, and H. Joseph Straight, On the number of Hamiltonian cycles of P4 X Pn, Indian J. Pure Appl. Math. 21(5) (1990), 403-409.
Index entries for linear recurrences with constant coefficients, signature (2,2,-2,1).
FORMULA
a(n) = 2*a(n-1) + 2*a(n-2) - 2*a(n-3) + a(n-4).
G.f.: x^2/(1-2x-2x^2+2x^3-x^4). - R. J. Mathar, Dec 16 2008
a(n)=sum ( sum ( binomial(k,j) * sum (binomial(j, i-j)*2^j *binomial(k-j,n-i-3*(k-j))*(-2)^(4*(k-j)-(n-i)), i,j,n-k+j) , j,0,k) , k,1,n ), n>0. - Vladimir Kruchinin, Aug 04 2010
a(n) = Sum_{k=1..n-1} A181688(k). - Kevin McShane, Aug 04 2019
MATHEMATICA
LinearRecurrence[{2, 2, -2, 1}, {0, 1, 2, 6}, 50] (* Paolo Xausa, Jul 01 2025 *)
PROG
(Maxima) a(n):=sum ( sum ( binomial(k, j) *sum (binomial(j, i-j)*2^j *binomial(k-j, n-i-3*(k-j))*(-2)^(4*(k-j)-(n-i)), i, j, n-k+j) , j, 0, k) , k, 1, n ); /* Vladimir Kruchinin, Aug 04 2010 */
CROSSREFS
KEYWORD
easy,nonn,changed
AUTHOR
STATUS
approved