login
A286954
Number of maximal irredundant sets in the n-cycle graph.
6
0, 2, 3, 6, 10, 11, 14, 14, 30, 62, 66, 99, 143, 212, 343, 478, 697, 992, 1501, 2246, 3251, 4776, 6969, 10283, 15210, 22297, 32727, 47984, 70644, 103961, 152706, 224382, 329508, 484451, 712274, 1046736, 1538164, 2260109, 3321932, 4882574, 7175738, 10545581
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
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
Row sums of A291044.
Sequence in context: A342766 A048633 A225175 * A047402 A088196 A112925
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