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

Author

Frans J. Faase

Keywords

• nonn
• easy

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).

Crossrefs

Column k=4 of A359855.

First differences of A052530 and A071954.

Cf. A001353, A001835.

Programs

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

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

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 *)

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 */

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

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