A286887 -id:A286887 - cp's OEIS frontend

A286868 Array read by antidiagonals: T(m,n) = number of irredundant sets in the grid graph P_m X P_n.

2, 3, 3, 5, 11, 5, 9, 26, 26, 9, 15, 79, 113, 79, 15, 26, 224, 548, 548, 224, 26, 44, 640, 2513, 4481, 2513, 640, 44, 76, 1828, 11826, 34049, 34049, 11826, 1828, 76, 130, 5225, 55136, 265227, 425926, 265227, 55136, 5225, 130

Offset: 1

Andrew Howroyd, Aug 02 2017

			Array begins:
=============================================================
m\n|  1    2     3       4        5          6           7
---|---------------------------------------------------------
1  |  2    3     5       9       15         26          44...
2  |  3   11    26      79      224        640        1828...
3  |  5   26   113     548     2513      11826       55136...
4  |  9   79   548    4481    34049     265227     2052725...
5  | 15  224  2513   34049   425926    5467052    69724154...
6  | 26  640 11826  265227  5467052  116003176  2441933224...
7  | 44 1828 55136 2052725 69724154 2441933224 84850904785...
...

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

Row 1 is A286887.
Main diagonal is A286869.
Cf. A286847 (minimal dominating sets).
Cf. A286870 (king graph).

A286870 Array read by antidiagonals: T(m,n) = number of irredundant sets in the m X n king graph.

Original entry on oeis.org

2, 3, 3, 5, 5, 5, 9, 11, 11, 9, 15, 25, 43, 25, 15, 26, 51, 133, 133, 51, 26, 44, 113, 463, 647, 463, 113, 44, 76, 235, 1493, 2945, 2945, 1493, 235, 76, 130, 521, 5011, 14217, 22049, 14217, 5011, 521, 130, 223, 1107, 16659, 65627, 147672, 147672, 65627, 16659, 1107, 223

Offset: 1

Andrew Howroyd, Aug 02 2017

			Array begins:
====================================================================
m\n|  1   2     3      4       5         6          7           8
---|----------------------------------------------------------------
1  |  2   3     5      9      15        26         44          76...
2  |  3   5    11     25      51       113        235         521...
3  |  5  11    43    133     463      1493       5011       16659...
4  |  9  25   133    647    2945     14217      65627      322163...
5  | 15  51   463   2945   22049    147672    1043127     7365740...
6  | 26 113  1493  14217  147672   1455385   14656628   151865727...
7  | 44 235  5011  65627 1043127  14656628  218691097  3287831848...
8  | 76 521 16659 322163 7365740 151865727 3287831848 72877697369...
...

Andrew Howroyd, Table of n, a(n) for n = 1..153
Matthew D. Kearse and Peter B. Gibbons, Computational Methods and New Results for Chessboard Problems, CDMTCS Research Reports CDMTCS-133 (2000).
Eric Weisstein's World of Mathematics, King Graph
Eric Weisstein's World of Mathematics, Irredundant Set

Row 1 is A286887.
Main diagonal is A286871.
Cf. A218663 (dominating sets), A286849 (minimal dominating sets).
Cf. A286868 (grid graph).

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

Original entry on oeis.org

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

A286868 Array read by antidiagonals: T(m,n) = number of irredundant sets in the grid graph P_m X P_n.

Views

Author

Keywords

Examples

Links

Crossrefs

A286870 Array read by antidiagonals: T(m,n) = number of irredundant sets in the m X n king graph.

Views

Author

Keywords

Examples

Links

Crossrefs

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions