A286870 -id:A286870 - cp's OEIS frontend

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

1, 2, 2, 2, 4, 2, 4, 6, 6, 4, 4, 16, 12, 16, 4, 7, 20, 36, 36, 20, 7, 9, 52, 64, 256, 64, 52, 9, 13, 80, 204, 400, 400, 204, 80, 13, 18, 176, 446, 2704, 971, 2704, 446, 176, 18, 25, 296, 1184, 6400, 6486, 6486, 6400, 1184, 296, 25

Offset: 1

Andrew Howroyd, Aug 01 2017

			Array begins:
===========================================================
m\n|  1   2    3     4      5       6        7         8
---|-------------------------------------------------------
1  |  1   2    2     4      4       7        9        13...
2  |  2   4    6    16     20      52       80       176...
3  |  2   6   12    36     64     204      446      1184...
4  |  4  16   36   256    400    2704     6400     30976...
5  |  4  20   64   400    971    6486    22177    112317...
6  |  7  52  204  2704   6486   85405   351503   3082745...
7  |  9  80  446  6400  22177  351503  1997448  21587536...
8  | 13 176 1184 30976 112317 3082745 21587536 360584008...
...

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

Rows 1-2 are A253413, A286850.
Main diagonal is A286881.
Cf. A218663 (dominating sets), A245013 (independent), A286870 (irredundant).
Cf. A286847 (grid graph).

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

Original entry on oeis.org

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

A286887 Number of irredundant sets in the path graph P_n.

Original entry on oeis.org

2, 3, 5, 9, 15, 26, 44, 76, 130, 223, 382, 655, 1123, 1925, 3300, 5657, 9698, 16625, 28500, 48857, 83755, 143580, 246137, 421949, 723341, 1240013, 2125736, 3644118, 6247058, 10709240, 18358693, 31472038, 53952053, 92489213, 158552901, 271804912, 465951173

Offset: 1

Andrew Howroyd, Aug 02 2017

Equivalently, the number of binary words of length n that don't start or end with 11 (the outside 1 is redundant) and don't contain 111, 1101 or 1011 (the middle 1 is redundant).

			Case n=5: irredundant words are {00000, 00001, 00010, 00100, 01000, 10000, 00110, 01100, 10001, 00101, 01010, 10100, 01001, 10010, 10101}, so a(5)=15.

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

Row 1 of A286868 and A286870.

RootSum[1 - #^2 - #^4 - #^5 + #^6 &, 3191 #^n + 4752 #^(1 + n) - 4234 #^(2 + n) + 11985 #^(3 + n) - 2369 #^(4 + n) + 3536 #^(5 + n) &]/89653 (* Eric W. Weisstein, Aug 04 2017 *)
LinearRecurrence[{1, 1, 0, 1, 0, -1}, {2, 3, 5, 9, 15, 26}, 20] (* Eric W. Weisstein, Aug 04 2017 *)
CoefficientList[Series[(2 + x + x^3 - x^4 - x^5)/(1 - x - x^2 - x^4 + x^6), {x, 0, 20}], x] (* Eric W. Weisstein, Aug 04 2017 *)

Vec((1 + x)*(2 - x + x^2 - x^4)/(1 - x - x^2 - x^4 + x^6) + O(x^40))

a(n) = a(n-1) + a(n-2) + a(n-4) - a(n-6) for n > 6.

G.f.: x*(1 + x)*(2 - x + x^2 - x^4)/(1 - x - x^2 - x^4 + x^6).

A286871 Number of irredundant sets in the n X n king graph.

Original entry on oeis.org

2, 5, 43, 647, 22049, 1455385, 218691097, 72877697369, 51489351108548, 76986419992442614, 244445556617038272066, 1683765308911934025295376

Offset: 1

Andrew Howroyd, Aug 02 2017

Eric Weisstein's World of Mathematics, Irredundant Set
Eric Weisstein's World of Mathematics, King Graph

Main diagonal of A286870.

Cf. A075550, A075709.

A286870 = Import["https://oeis.org/A286870/b286870.txt", "Table"][[All, 2]];
a[n_] := A286870[[2 n^2 - 2 n + 1]];
Table[a[n], {n, 1, 9}] (* Jean-François Alcover, Sep 23 2019 *)

a(10)-a(12) from Christian Sievers, Nov 22 2023

cp's OEIS Frontend

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

Views

Author

Keywords

Examples

Links

Crossrefs

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

A286887 Number of irredundant sets in the path graph P_n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A286871 Number of irredundant sets in the n X n king graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Extensions