OFFSET
1,2
COMMENTS
From Andrew Howroyd, Aug 16 2017: (Start)
Equivalently, the number of binary words not cyclically containing a sub-word of 111, 1101, 1011, 00000, 000010, 010000, 000100, 001000, 0100010.
For n > 1, the minimum size of a maximal irredundant set, the irredundance number, is given by ceiling(n/3). A suitable construction for such a set is every third vertex starting with the first.
The maximum size of an irredundant set, the upper irredundance number, is given by floor(n/2). For n > 1, a suitable construction for such a set is every second vertex starting with the second.
(End)
LINKS
Andrew Howroyd, Table of n, a(n) for n = 1..500
Eric Weisstein's World of Mathematics, Cycle Graph.
Eric Weisstein's World of Mathematics, Maximal Irredundant Set.
Index entries for linear recurrences with constant coefficients, signature (0,1,1,1,1,0,-1,-2,-1,2,1,0,0,-1).
FORMULA
From Andrew Howroyd, Aug 16 2017: (Start)
a(n) = a(n-2) + a(n-3) + a(n-4) + a(n-5) - a(n-7) - 2*a(n-8) - a(n-9) + 2*a(n-10) + a(n-11) - a(n-14) for n > 14.
G.f.: 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).
a(p) = p * A291048(p) for p prime.
(End)
EXAMPLE
From Andrew Howroyd, Aug 16 2017: (Start)
Case n=2: admissible words are 01 and 10, so a(2)=2.
Case n=3: admissible words are 001, 010, 100, so a(3)=3.
Case n=7: up to rotation, admissible words are 0010011 and 0010101, so a(7) = 7*2 = 14.
(End)
MATHEMATICA
LinearRecurrence[{0, 1, 1, 1, 1, 0, -1, -2, -1, 2, 1, 0, 0, -1}, {0, 2, 3, 6, 10, 11, 14, 14, 30, 62, 66, 99, 143, 212}, 20]
CoefficientList[Series[(x (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, 20}], x]
Table[RootSum[1 - #^3 - 2 #^4 + #^5 + 2 #^6 + #^7 - #^9 - #^10 - #^11 - #^12 + #^14 &, #^n &], {n, 20}]
RootSum[1 - #^3 - 2 #^4 + #^5 + 2 #^6 + #^7 - #^9 - #^10 - #^11 - #^12 + #^14 &, #^Range[20] &]
PROG
(PARI)
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^40)) \\ Andrew Howroyd, Aug 16 2017
CROSSREFS
KEYWORD
nonn
AUTHOR
Eric W. Weisstein, Aug 15 2017
EXTENSIONS
a(1)-a(2) and terms a(21) and beyond from Andrew Howroyd, Aug 16 2017
STATUS
approved