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

11, 65, 265, 1005, 3749, 13927, 51683, 191735, 711243, 2638305, 9786545, 36302213, 134659381, 499505271, 1852863915, 6873009871, 25494729643, 94570101217, 350798151929, 1301249991357, 4826854219941, 17904723777319, 66415748007763, 246362448161159, 913856392265003

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.: z(1+z)(11+10z+6z^2+4z^3+z^4)/((1-z)(1-3z-2z^2-2z^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}, {11, 65, 265, 1005, 3749, 13927}, 20] (* Jinyuan Wang, Feb 22 2020 *)

Prog

(PARI) Vec(z*(1+z)*(11+10*z+6*z^2+4*z^3+z^4)/((1-z)*(1-3*z-2*z^2-2*z^3-z^4-z^5)) + O(z^30)) \\ Jinyuan Wang, Feb 22 2020

Crossrefs

Cf. A332751 (number of flips from beta_n to gamma_n, same growth rate).

Sequence in context: A233164 A215445 A184055 * A161459 A162288 A161776

Adjacent sequences: A332747 A332748 A332749 * A332751 A332752 A332753

Keyword

nonn,easy

Author

Filip Stappers, Feb 22 2020

Extensions

More terms from Jinyuan Wang, Feb 22 2020

Status

approved