|
|
A291055
|
|
Number of maximal irredundant sets in the n-path graph.
|
|
4
|
|
|
1, 2, 2, 4, 6, 8, 13, 17, 27, 40, 57, 86, 122, 184, 269, 395, 582, 849, 1255, 1843, 2708, 3982, 5841, 8597, 12631, 18566, 27286, 40082, 58929, 86598, 127279, 187052, 274872, 404001, 593732, 872606, 1282416, 1884660, 2769856, 4070718, 5982611, 8792345
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
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
|
Index entries for linear recurrences with constant coefficients, signature (0, 1, 1, 1, 1, 0, -1, -2, -1, 2, 1, 0, 0, -1).
|
|
FORMULA
|
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
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|