|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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
|
|
|
STATUS
|
approved
|
|
|
|