OFFSET
1,4
COMMENTS
Equivalently, the number of n-bead binary necklaces (with turnover not allowed) avoiding the patterns 111, 1101, 1011, 00000, 000010, 010000, 000100, 001000, 0100010.
LINKS
Andrew Howroyd, Table of n, a(n) for n = 1..200
Eric Weisstein's World of Mathematics, Cycle Graph
Eric Weisstein's World of Mathematics, Irredundant Set
FORMULA
a(n) = (1/n) * Sum_{d|n} phi(n/d) * A286954(d).
EXAMPLE
Case n=7: admissible nonequivalent words are 0010011 and 0010101, so a(7)=2.
MATHEMATICA
Table[(1/n) Sum[EulerPhi[n/d] SeriesCoefficient[x^2*(2 + 3 x + 4 x^2 + 5 x^3 - 7 x^5 - 16 x^6 - 9 x^7 + 20 x^8 + 11 x^9 - 14 x^12)/(1 - x^2 - x^3 - x^4 - x^5 + x^7 + 2 x^8 + x^9 - 2 x^10 - x^11 + x^14), {x, 0, d}], {d, Divisors@ n}], {n, 48}] (* Michael De Vlieger, Aug 17 2017 *)
PROG
(PARI)
{my (v=concat([0], Vec((2 + 3*x + 4*x^2 + 5*x^3 - 7*x^5 - 16*x^6 - 9*x^7 + 20*x^8 + 11*x^9 - 14*x^12)/(1 - x^2 - x^3 - x^4 - x^5 + x^7 + 2*x^8 + x^9 - 2*x^10 - x^11 + x^14) + O(x^50))));
vector(length(v), n, sumdiv(n, d, eulerphi(n/d)*v[d])/n)}
CROSSREFS
KEYWORD
nonn
AUTHOR
Andrew Howroyd, Aug 16 2017
STATUS
approved