A332751 The number of flips to go from Hamiltonian cycle beta_n to gamma_n in the Cameron graph of size n using Thomason's algorithm.

6, 28, 108, 400, 1486, 5516, 20464, 75912, 281590, 1044532, 3874588, 14372392, 53312926, 197758868, 733566368, 2721089680, 10093604838, 37441198412, 138884309516, 515177191104, 1910997283694, 7088649655580, 26294623424272, 97537225651992, 361804397590486, 1342076537863268

Offset

1,1

Links

Colin Barker, Table of n, a(n) for n = 1..1000

K. Cameron, Thomason's algorithm for finding a second hamiltonian circuit through a given edge in a cubic graph is exponential on Krawczyk's graphs, Discrete Mathematics (235), 2001, pp. 69-77.

Donald Knuth, The Art of Computer Programming, Pre-fascicle 8a, Hamiltonian paths and cycles, exercise 77, pp. 16, 26-27 (retrieved Feb 22 2020).

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

Formula

G.f.: 2*z*(3+2*z+z^2-2*z^3) / ((1-z)*(1-3*z-2*z^2-2*z^3-z^4-z^5)).

a(n) = 4*a(n-1) - a(n-2) - a(n-4) - a(n-6) for n>6. - Colin Barker, Feb 22 2020

Mathematica

LinearRecurrence[{4, -1, 0, -1, 0, -1}, {6, 28, 108, 400, 1486, 5516}, 20] (* Jinyuan Wang, Feb 22 2020 *)

Prog

(PARI) Vec(2*z*(3 + 2*z + z^2 - 2*z^3) / ((1 - z)*(1 - 3*z - 2*z^2 - 2*z^3 - z^4 - z^5)) + O(z^30)) \\ Colin Barker, Feb 22 2020

Crossrefs

Cf. A332750 (number of flips from alpha_n to beta_n, same growth rate).

Sequence in context: A117999 A234617 A028379 * A263942 A326138 A326131

Adjacent sequences: A332748 A332749 A332750 * A332752 A332753 A332754

Keyword

nonn,easy

Author

Filip Stappers, Feb 22 2020

Extensions

More terms from Jinyuan Wang, Feb 22 2020

Status

approved