A286954 -id:A286954 - cp's OEIS frontend

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

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

A291044 Irregular triangle read by rows: number of maximal irredundant sets of size k in the n-cycle graph.

Original entry on oeis.org

0, 2, 0, 3, 0, 0, 6, 0, 0, 10, 0, 0, 9, 2, 0, 0, 0, 14, 0, 0, 0, 8, 6, 0, 0, 0, 3, 27, 0, 0, 0, 0, 60, 2, 0, 0, 0, 0, 33, 33, 0, 0, 0, 0, 9, 84, 6, 0, 0, 0, 0, 0, 91, 52, 0, 0, 0, 0, 0, 14, 196, 2, 0, 0, 0, 0, 0, 3, 280, 60, 0, 0, 0, 0, 0, 0, 200, 272, 6

Offset: 2

Andrew Howroyd, Aug 16 2017

For each row, k lies in the range 0..floor(n/2). The upper end of the range is the upper irredundance number of the graph.

			Triangle begins:
  0, 2;
  0, 3;
  0, 0, 6;
  0, 0, 10;
  0, 0,  9   2;
  0, 0,  0, 14;
  0, 0,  0,  8,  6;
  0, 0,  0,  3, 27;
  0, 0,  0,  0, 60,  2;
  0, 0,  0,  0, 33, 33;
  0, 0,  0,  0,  9, 84,   6;
  0, 0,  0,  0,  0, 91,  52;
  0, 0,  0,  0,  0, 14, 196, 2;
  ...
As polynomials these are 2*x; 3*x; 6*x^2; 10*x^2; 9*x^2 + 2*x^3; etc.

Andrew Howroyd, Table of n, a(n) for n = 2..991
Eric Weisstein's World of Mathematics, Cycle Graph.
Eric Weisstein's World of Mathematics, Maximal Irredundant Set.

Row sums are A286954.

T(n,k) = 0 for k < ceiling(n/3).

Sum_{k=0..floor(n/2)} T(n,k) = A286954(n). - Eric W. Weisstein, Jun 11 2021

A291048 Number of nonequivalent maximal irredundant sets in the n-cycle graph up to rotation.

Original entry on oeis.org

0, 1, 1, 2, 2, 3, 2, 3, 4, 8, 6, 11, 11, 17, 25, 32, 41, 59, 79, 118, 157, 221, 303, 436, 610, 864, 1215, 1724, 2436, 3484, 4926, 7029, 9990, 14270, 20354, 29113, 41572, 59517, 85186, 122127, 175018, 251176, 360404, 517758, 743895, 1069633, 1538313, 2213894

Offset: 1

Andrew Howroyd, Aug 16 2017

nonn

Equivalently, the number of n-bead binary necklaces (with turnover not allowed) avoiding the patterns 111, 1101, 1011, 00000, 000010, 010000, 000100, 001000, 0100010.

			Case n=7: admissible nonequivalent words are 0010011 and 0010101, so a(7)=2.

Andrew Howroyd, Table of n, a(n) for n = 1..200
Eric Weisstein's World of Mathematics, Cycle Graph.
Eric Weisstein's World of Mathematics, Maximal Irredundant Set.

Cf. A286954.

Table[(1/n) Sum[EulerPhi[n/d] SeriesCoefficient[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), {x, 0, d}], {d, Divisors@ n}], {n, 48}] (* Michael De Vlieger, Aug 17 2017 *)

{my (v=concat([0],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^50))));
vector(length(v), n, sumdiv(n,d,eulerphi(n/d)*v[d])/n)}

a(n) = (1/n) * Sum_{d|n} phi(n/d) * A286954(d).

A291063 Number of maximal irredundant sets in the n-wheel graph.

Original entry on oeis.org

1, 3, 4, 7, 11, 12, 15, 15, 31, 63, 67, 100, 144, 213, 344, 479, 698, 993, 1502, 2247, 3252, 4777, 6970, 10284, 15211, 22298, 32728, 47985, 70645, 103962, 152707, 224383, 329509, 484452, 712275, 1046737, 1538165, 2260110, 3321933, 4882575, 7175739

Offset: 2

Eric W. Weisstein, Aug 17 2017

nonn

The wheel graph is well defined for n >= 4. Sequence extended to n=2 using formula. - Andrew Howroyd, Aug 19 2017

Colin Barker, Table of n, a(n) for n = 2..1000
Eric Weisstein's World of Mathematics, Maximal Irredundant Set
Eric Weisstein's World of Mathematics, Wheel Graph
Index entries for linear recurrences with constant coefficients, signature (1,1,0,0,0,-1,-1,-1,1,3,-1,-1,0,-1,1).

Cf. A286954, A290494.

Table[1 + RootSum[1 - #^3 - 2 #^4 + #^5 + 2 #^6 + #^7 - #^9 - #^10 - #^11 - #^12 + #^14 &, #^(n - 1) &], {n, 2, 20}]
1 + RootSum[1 - #^3 - 2 #^4 + #^5 + 2 #^6 + #^7 - #^9 - #^10 - #^11 - #^12 + #^14 &, #^Range[20] &]
LinearRecurrence[{1, 1, 0, 0, 0, -1, -1, -1, 1, 3, -1, -1, 0, -1, 1}, {1, 3, 4, 7, 11, 12, 15, 15, 31, 63, 67, 100, 144, 213, 344}, 20]
CoefficientList[
Series[(1 + 2 x - 6 x^5 - 7 x^6 - 8 x^7 + 9 x^8 + 30 x^9 - 11 x^10 - 12 x^11 - 14 x^13 + 15 x^14)/((1 - x) (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]

Vec(x^2*(1 + 2*x - 6*x^5 - 7*x^6 - 8*x^7 + 9*x^8 + 30*x^9 - 11*x^10 - 12*x^11 - 14*x^13 + 15*x^14) / ((1 - x)*(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^60)) \\ Colin Barker, Aug 20 2017

a(n) = A286954(n-1) + 1. - Andrew Howroyd, Aug 19 2017

G.f.: x^2*(1 + 2*x - 6*x^5 - 7*x^6 - 8*x^7 + 9*x^8 + 30*x^9 - 11*x^10 - 12*x^11 - 14*x^13 + 15*x^14) / ((1 - x)*(1 - x^2 - x^3 - x^4 - x^5 + x^7 + 2*x^8 + x^9 - 2*x^10 - x^11 + x^14)). - Colin Barker, Aug 20 2017

a(2)-a(3) and a(21)-a(42) from Andrew Howroyd, Aug 19 2017

A291102 Number of maximal irredundant sets in the n-pan graph.

Original entry on oeis.org

2, 2, 3, 7, 9, 13, 19, 24, 39, 63, 87, 124, 183, 272, 405, 593, 867, 1261, 1869, 2760, 4046, 5936, 8712, 12817, 18861, 27720, 40711, 59792, 87915, 129250, 189946, 279118, 410135, 602803, 886008, 1302157, 1913622, 2812220, 4133091, 6074385, 8927330, 13119959

Offset: 1

Eric W. Weisstein, Aug 17 2017

nonn

Sequence extended to a(1)-a(2) using the formula/recurrence. - Andrew Howroyd, Aug 23 2017

Andrew Howroyd, Table of n, a(n) for n = 1..500
Eric Weisstein's World of Mathematics, Maximal Irredundant Set
Eric Weisstein's World of Mathematics, Pan Graph
Index entries for linear recurrences with constant coefficients, signature (0, 1, 1, 1, 1, 0, -1, -2, -1, 2, 1, 0, 0, -1).

Cf. A286954, A291107.

Table[-RootSum[1 - #^3 - 2 #^4 + #^5 + 2 #^6 + #^7 - #^9 - #^10 - #^11 - #^12 + #^14 &, 500851004670498 #^(n+1) - 3689002954543242 #^(n+2) - 4674357321032747 #^(n+3) - 11682114439256677 #^(n+4) + 4235991226348286 #^(n+5) + 7038537508218316 #^(n+6) + 7181640141870472 #^(n+7) + 1546373234795414 #^(n+8) - 8648457478830123 #^(n+9) - 8135065519248445 #^(n+10) - 4540890555566032 #^(n+11) - 5314826024895471 #^(n+12) - 1546564184442276 #^(n+13) + 6933486092556085 #^(n+14) &]/47617929706047629, {n, 20}]
LinearRecurrence[{0, 1, 1, 1, 1, 0, -1, -2, -1, 2, 1, 0, 0, -1}, {2, 2, 3, 7, 9, 13, 19, 24, 39, 63, 87, 124, 183, 272}, 20]
CoefficientList[Series[(2 + 2 x + x^2 + 3 x^3 + 2 x^4 - x^5 - 2 x^6 - 6 x^7 - 3 x^8 + 7 x^9 + 3 x^10 - x^11 - 4 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, 20}], x]

Vec((2 + 2*x + x^2 + 3*x^3 + 2*x^4 - x^5 - 2*x^6 - 6*x^7 - 3*x^8 + 7*x^9 + 3*x^10 - x^11 - 4*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*(2 + 2*x + x^2 + 3*x^3 + 2*x^4 - x^5 - 2*x^6 - 6*x^7 - 3*x^8 + 7*x^9 + 3*x^10 - x^11 - 4*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)

a(1)-a(2) and 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

A291044 Irregular triangle read by rows: number of maximal irredundant sets of size k in the n-cycle graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A291048 Number of nonequivalent maximal irredundant sets in the n-cycle graph up to rotation.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A291063 Number of maximal irredundant sets in the n-wheel graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A291102 Number of maximal irredundant sets in the n-pan graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions