login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A003699 Number of Hamiltonian cycles in C_4 X P_n. 7
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 (list; graph; refs; listen; history; text; internal format)
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

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) = -x - 2 + (-6*x + 2)/(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)

MATHEMATICA

Join[{1}, LinearRecurrence[{4, -1}, {6, 22}, 30]] (* Harvey P. Dale, Jul 19 2011 *)

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

CROSSREFS

First differences of A052530 and A071954.

Equals 2 * A001835(n), n > 1.

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 20 12:57 EST 2019. Contains 320327 sequences. (Running on oeis4.)