login
A291048
Number of nonequivalent maximal irredundant sets in the n-cycle graph up to rotation.
2
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,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
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
Cf. A286954.
Sequence in context: A059896 A079542 A220370 * A022467 A306894 A169614
KEYWORD
nonn
AUTHOR
Andrew Howroyd, Aug 16 2017
STATUS
approved