The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006864 Number of Hamiltonian cycles in P_4 X P_n.
(Formerly M1603)

%I M1603

%S 0,1,2,6,14,37,92,236,596,1517,3846,9770,24794,62953,159800,405688,

%T 1029864,2614457,6637066,16849006,42773094,108584525,275654292,

%U 699780452,1776473532,4509783909,11448608270,29063617746,73781357746,187302518353,475489124976

%N Number of Hamiltonian cycles in P_4 X P_n.

%C 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

%D F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.

%D 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.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D 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.

%H F. Faase, <a href="http://www.iwriteiam.nl/Cpaper.zip">On the number of specific spanning subgraphs of the graphs G X P_n</a>, Preliminary version of paper that appeared in Ars Combin. 49 (1998), 129-154.

%H F. Faase, <a href="http://www.iwriteiam.nl/counting.html">Counting Hamiltonian cycles in product graphs</a>

%H F. Faase, <a href="http://www.iwriteiam.nl/Cresults.html">Results from the counting program</a>

%H C. Flye Sainte-Marie, <a href="https://archive.org/details/lintermdiairede02lemogoog/page/n109">Manières différentes de tracer une route fermée ...</a>, L'Intermédiaire des Mathématiciens, vol. 11 (1904), pp. 86-88 (in French).

%H George Jelliss, <a href="http://www.mayhematics.com/t/pw.htm">Wazir Wanderings</a>

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (2, 2, -2, 1).

%F a(n) = 2*a(n-1) + 2*a(n-2) - 2*a(n-3) + a(n-4).

%F G.f.: x^2/(1-2x-2x^2+2x^3-x^4). - _R. J. Mathar_, Dec 16 2008

%F 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

%F a(n) = Sum_{k=1..n-1} A181688(k). - _Kevin McShane_, Aug 04 2019

%o (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 */

%K easy,nonn

%O 1,3

%A kwong(AT)cs.fredonia.edu (Harris Kwong), _N. J. A. Sloane_, _Simon Plouffe_ and _Frans J. Faase_

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 5 14:29 EDT 2021. Contains 346469 sequences. (Running on oeis4.)