A291048 Number of nonequivalent maximal irredundant sets in the n-cycle graph up to rotation.

0, 1, 1, 2, 2, 3, 2, 3, 4, 8, 6, 11, 11, 17, 25, 32, 41, 59, 79, 118, 157, 221, 303, 436, 610, 864, 1215, 1724, 2436, 3484, 4926, 7029, 9990, 14270, 20354, 29113, 41572, 59517, 85186, 122127, 175018, 251176, 360404, 517758, 743895, 1069633, 1538313, 2213894

Offset: 1

Author

Andrew Howroyd, Aug 16 2017

Keywords

• nonn

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.

Examples

			Case n=7: admissible nonequivalent words are 0010011 and 0010101, so a(7)=2.
		

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, Maximal Irredundant Set.

Crossrefs

Cf. A286954.

Programs

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 *)

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)}

Formula

a(n) = (1/n) * Sum_{d|n} phi(n/d) * A286954(d).