A006864 Number of Hamiltonian cycles in P_4 X P_n.

0, 1, 2, 6, 14, 37, 92, 236, 596, 1517, 3846, 9770, 24794, 62953, 159800, 405688, 1029864, 2614457, 6637066, 16849006, 42773094, 108584525, 275654292, 699780452, 1776473532, 4509783909, 11448608270, 29063617746, 73781357746, 187302518353, 475489124976, 1207084188912

Offset: 1

Author

kwong(AT)cs.fredonia.edu (Harris Kwong), N. J. A. Sloane, Simon Plouffe and Frans J. Faase

Keywords

• easy
• nonn

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
• F. 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.
• F. Faase, Counting Hamiltonian cycles in product graphs
• F. 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
• R. Tosic, O. Bodroza, 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).

Crossrefs

Row/column 4 of A321172.

Programs

Mathematica

LinearRecurrence[{2, 2, -2, 1}, {0, 1, 2, 6}, 50] (* Paolo Xausa, Jul 01 2025 *)

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 */

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