%I M1603 #50 Sep 09 2019 10:25:58
%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_
|