A003764 Number of 2-factors in W_4 X P_n.

1, 13, 85, 673, 5021, 38237, 289089, 2191309, 16594837, 125714929, 952245373, 7213225309, 54639088433, 413885098253, 3135127983381, 23748220228801, 179889887447581, 1362644200671133, 10321865130390817

Offset

1,2

References

F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.

Links

Table of n, a(n) for n=1..19.

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

Formula

a(1) = 1,

a(2) = 13,

a(3) = 85,

a(4) = 673,

a(5) = 5021 and

a(n) = 6a(n-1) + 16a(n-2) - 29a(n-3) - 16a(n-4) + 16a(n-5).

G.f.: x(1+7x-9x^2-16x^3+16x^4)/(1-6x-16x^2+29x^3+16x^4-16x^5). [From R. J. Mathar, Dec 16 2008]

Crossrefs

Sequence in context: A055843 A296647 A233325 * A221338 A322720 A082036

Adjacent sequences: A003761 A003762 A003763 * A003765 A003766 A003767

Keyword

nonn

Author

Frans J. Faase

Extensions

Added recurrence from Faase's web page. - N. J. A. Sloane, Feb 03 2009

Status

approved