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

Author

Eric W. Weisstein, Aug 15 2017

Keywords

• nonn

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)

Examples

			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)
		

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).

Crossrefs

Row sums of A291044.

Cf. A290493, A291048.

Programs

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] &]

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

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)

Extensions

a(1)-a(2) and terms a(21) and beyond from Andrew Howroyd, Aug 16 2017