cp's OEIS Frontend

A003699 Number of Hamiltonian cycles in C_4 X P_n.

%I A003699 #49 Feb 18 2025 17:39:05
%S A003699 1,6,22,82,306,1142,4262,15906,59362,221542,826806,3085682,11515922,
%T A003699 42978006,160396102,598606402,2234029506,8337511622,31116016982,
%U A003699 116126556306,433390208242,1617434276662,6036346898406,22527953316962,84075466369442,313773912160806
%N A003699 Number of Hamiltonian cycles in C_4 X P_n.
%C A003699 a(n) is the number of generalized compositions of n when there are i^2+i-1 different types of i, (i = 1, 2, ...). - _Milan Janjic_, Sep 24 2010
%C A003699 Is this the same as the sequence visible in Table 5 of Pettersson, 2014? - _N. J. A. Sloane_, Jun 05 2015
%D A003699 F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.
%H A003699 Vincenzo Librandi, <a href="/A003699/b003699.txt">Table of n, a(n) for n = 1..1000</a>
%H A003699 W. K. Alt, <a href="http://people.reed.edu/~davidp/homepage/students/alt.pdf">Enumeration of Domino Tilings on the Projective Grid Graph</a>, A Thesis Presented to The Division of Mathematics and Natural Sciences, Reed College, May 2013.
%H A003699 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 A003699 F. Faase, <a href="http://www.iwriteiam.nl/counting.html">Counting Hamiltonian cycles in product graphs</a>
%H A003699 F. Faase, <a href="http://www.iwriteiam.nl/Cresults.html">Results from the counting program</a>
%H A003699 Ville H. Pettersson, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p7">Enumerating Hamiltonian Cycles</a>, The Electronic Journal of Combinatorics, Volume 21, Issue 4, 2014.
%H A003699 <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (4,-1).
%F A003699 a(n) = 2 * A001835(n), n > 1.
%F A003699 From _Benoit Cloitre_, Mar 28 2003: (Start)
%F A003699 a(n) = ceiling((1 - sqrt(1/3))*(2 + sqrt(3))^n) for n > 1.
%F A003699 a(1) = 1, a(2) = 6, a(3) = 22 and for n > 3, a(n) = 4*a(n-1) - a(n-2). (End)
%F A003699 O.g.f.: x*(1 + 2*x - x^2)/(1-4*x+x^2) = -2 - x + 2*(1 - 3*x)/(1-4*x+x^2). - _R. J. Mathar_, Nov 23 2007
%F A003699 From _Franck Maminirina Ramaharo_, Nov 12 2018: (Start)
%F A003699 a(n) = ((1 + sqrt(3))*(2 - sqrt(3))^n - (1 - sqrt(3))*(2 + sqrt(3))^n)/sqrt(3), n > 1.
%F A003699 E.g.f.: ((1 + sqrt(3))*exp((2 - sqrt(3))*x) - (1 - sqrt(3))*exp((2 + sqrt(3))*x) - (2 + x)*sqrt(3))/sqrt(3). (End)
%F A003699 a(n) = 2*(ChebyshevU(n-1, 2) - ChebyshevU(n-2, 2)) for n >1, with a(1)=1. - _G. C. Greubel_, Dec 23 2019
%p A003699 seq( simplify( `if`(n=1, 1, 2*(ChebyshevU(n-1,2) - ChebyshevU(n-2,2))) ), n=1..30); # _G. C. Greubel_, Dec 23 2019
%t A003699 Join[{1},LinearRecurrence[{4,-1},{6,22},30]] (* _Harvey P. Dale_, Jul 19 2011 *)
%t A003699 Table[If[n<2, n, 2*(ChebyshevU[n-1, 2] - ChebyshevU[n-2, 2])], {n,30}] (* _G. C. Greubel_, Dec 23 2019 *)
%o A003699 (Maxima) (a[1] : 1, a[2] : 6, a[3] : 22, a[n] := 4*a[n - 1] - a[n - 2], makelist(a[n], n, 1, 50)); /* _Franck Maminirina Ramaharo_, Nov 12 2018 */
%o A003699 (Magma) I:=[1,6,22]; [n le 3 select I[n] else 4*Self(n-1)-Self(n-2): n in [1..30]]; // _Vincenzo Librandi_, Nov 13 2018
%o A003699 (PARI) vector(30, n, if(n==1, 1, 2*(polchebyshev(n-1, 2, 2) - polchebyshev(n-2, 2, 2))) ) \\ _G. C. Greubel_, Dec 23 2019
%o A003699 (Sage) [1]+[2*(chebyshev_U(n-1,2) - chebyshev_U(n-2,2)) for n in (2..30)] # _G. C. Greubel_, Dec 23 2019
%o A003699 (GAP) a:=[6,22];; for n in [3..20] do a[n]:=4a[n-1]-a[n-2]; od; Concatenation([1], a); # _G. C. Greubel_, Dec 23 2019
%Y A003699 Column k=4 of A359855.
%Y A003699 First differences of A052530 and A071954.
%Y A003699 Cf. A001353, A001835.
%K A003699 nonn,easy
%O A003699 1,2
%A A003699 _Frans J. Faase_