|
|
A006864
|
|
Number of Hamiltonian cycles in P_4 X P_n.
(Formerly M1603)
|
|
6
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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).
Tosic R., Bodroza O., Harris Kwong Y. H. and Joseph Straight H., On the number of Hamiltonian cycles of P4 X Pn, Indian J. Pure Appl. Math. 21 (5) (1990), 403-409.
|
|
LINKS
|
|
|
FORMULA
|
a(n) = 2*a(n-1) + 2*a(n-2) - 2*a(n-3) + a(n-4).
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
|
|
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
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|