A286954 Number of maximal irredundant sets in the n-cycle graph.

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

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

Row sums of A291044.

Cf. A290493, A291048.

Sequence in context: A342766 A048633 A225175 * A047402 A088196 A112925

Adjacent sequences: A286951 A286952 A286953 * A286955 A286956 A286957

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