login
A003699
Number of Hamiltonian cycles in C_4 X P_n.
12
1, 6, 22, 82, 306, 1142, 4262, 15906, 59362, 221542, 826806, 3085682, 11515922, 42978006, 160396102, 598606402, 2234029506, 8337511622, 31116016982, 116126556306, 433390208242, 1617434276662, 6036346898406, 22527953316962, 84075466369442, 313773912160806
OFFSET
1,2
COMMENTS
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
Is this the same as the sequence visible in Table 5 of Pettersson, 2014? - N. J. A. Sloane, Jun 05 2015
REFERENCES
F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.
LINKS
W. K. Alt, Enumeration of Domino Tilings on the Projective Grid Graph, A Thesis Presented to The Division of Mathematics and Natural Sciences, Reed College, May 2013.
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.
Ville H. Pettersson, Enumerating Hamiltonian Cycles, The Electronic Journal of Combinatorics, Volume 21, Issue 4, 2014.
FORMULA
a(n) = 2 * A001835(n), n > 1.
From Benoit Cloitre, Mar 28 2003: (Start)
a(n) = ceiling((1 - sqrt(1/3))*(2 + sqrt(3))^n) for n > 1.
a(1) = 1, a(2) = 6, a(3) = 22 and for n > 3, a(n) = 4*a(n-1) - a(n-2). (End)
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
From Franck Maminirina Ramaharo, Nov 12 2018: (Start)
a(n) = ((1 + sqrt(3))*(2 - sqrt(3))^n - (1 - sqrt(3))*(2 + sqrt(3))^n)/sqrt(3), n > 1.
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)
a(n) = 2*(ChebyshevU(n-1, 2) - ChebyshevU(n-2, 2)) for n >1, with a(1)=1. - G. C. Greubel, Dec 23 2019
MAPLE
seq( simplify( `if`(n=1, 1, 2*(ChebyshevU(n-1, 2) - ChebyshevU(n-2, 2))) ), n=1..30); # G. C. Greubel, Dec 23 2019
MATHEMATICA
Join[{1}, LinearRecurrence[{4, -1}, {6, 22}, 30]] (* Harvey P. Dale, Jul 19 2011 *)
Table[If[n<2, n, 2*(ChebyshevU[n-1, 2] - ChebyshevU[n-2, 2])], {n, 30}] (* G. C. Greubel, Dec 23 2019 *)
PROG
(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 */
(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
(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
(Sage) [1]+[2*(chebyshev_U(n-1, 2) - chebyshev_U(n-2, 2)) for n in (2..30)] # G. C. Greubel, Dec 23 2019
(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
CROSSREFS
First differences of A052530 and A071954.
Sequence in context: A051945 A253070 A255461 * A047124 A046365 A266184
KEYWORD
nonn,easy
STATUS
approved