OFFSET
1,2
COMMENTS
From Andrew Howroyd, Aug 23 2017: (Start)
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 second if n is a multiple of 3, otherwise starting with the first.
The maximum size of an irredundant set, the upper irredundance number, is given by ceiling(n/2). A suitable construction for such a set is every second vertex starting with the first.
(End)
LINKS
Andrew Howroyd, Table of n, a(n) for n = 1..500
Eric Weisstein's World of Mathematics, Path 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 23 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*(1 + 2*x + x^2 + x^3 + x^4 - x^5 - x^6 - 2*x^7 + 3*x^9 - x^12 - x^13)/(1 - x^2 - x^3 - x^4 - x^5 + x^7 + 2*x^8 + x^9 - 2*x^10 - x^11 + x^14).
(End)
EXAMPLE
Case n=5: maximal irredundant sets represented as binary words are {00110, 01001, 01010, 01100, 10010, 10101}, so a(5)=6. - Andrew Howroyd, Aug 23 2017
MATHEMATICA
Rest @ CoefficientList[Series[x (1 + 2 x + x^2 + x^3 + x^4 - x^5 - x^6 - 2 x^7 + 3 x^9 - x^12 - x^13)/(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, 42}], x] (* Michael De Vlieger, Aug 24 2017 *)
LinearRecurrence[{0, 1, 1, 1, 1, 0, -1, -2, -1, 2, 1, 0, 0, -1}, {1, 2, 2, 4, 6, 8, 13, 17, 27, 40, 57, 86, 122, 184}, 20] (* Eric W. Weisstein, Aug 28 2017 *)
RootSum[1 - #^3 - 2 #^4 + #^5 + 2 #^6 + #^7 - #^9 - #^10 - #^11 - #^12 + #^14 &, -4480566127993567 #^n + 2115784835595702 #^(n+1) - 8803686900182082 #^(n+2) + 12438105918248674 #^(n+3) + 9975829435558087 #^(n+4) + 32647411155695559 #^(n+5) + 921201586573742 #^(n+6) - 12400355965941932 #^(n+7) - 18709447182799197 #^(n+8) - 16194871035876814 #^(n+9) - 8478829128434826 #^(n+10) - 3824486277258301 #^(n+11) + 902031297001609 #^(n+12) + 11119370357865554 #^(n+13) &]/333325507942333403 (* Eric W. Weisstein, Aug 28 2017 *)
PROG
(PARI) Vec((1 + 2*x + x^2 + x^3 + x^4 - x^5 - x^6 - 2*x^7 + 3*x^9 - x^12 - x^13)/(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 23 2017
CROSSREFS
KEYWORD
nonn
AUTHOR
Eric W. Weisstein, Aug 17 2017
EXTENSIONS
Terms a(21) and beyond from Andrew Howroyd, Aug 23 2017
STATUS
approved