A291439 -id:A291439 - cp's OEIS frontend

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

Offset: 1

Eric W. Weisstein, Aug 17 2017

nonn

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)

			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

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

Row 1 of A291439.
Row sums of A291375.
Cf. A286887, A286954, A291444.

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

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

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)

Terms a(21) and beyond from Andrew Howroyd, Aug 23 2017

cp's OEIS Frontend

A291055 Number of maximal irredundant sets in the n-path graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions