A003699 Number of Hamiltonian cycles in C_4 X P_n.

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

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

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.

F. Faase, Counting Hamiltonian cycles in product graphs

F. Faase, Results from the counting program

Ville H. Pettersson, Enumerating Hamiltonian Cycles, The Electronic Journal of Combinatorics, Volume 21, Issue 4, 2014.

Index entries for linear recurrences with constant coefficients, signature (4,-1).

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.

Cf. A001353, A001835.

Sequence in context: A051945 A253070 A255461 * A047124 A046365 A266184

Adjacent sequences: A003696 A003697 A003698 * A003700 A003701 A003702

Keyword

nonn,easy

Author

Frans J. Faase

Status

approved