A286868 -id:A286868 - cp's OEIS frontend

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

1, 2, 2, 2, 6, 2, 4, 7, 7, 4, 4, 18, 16, 18, 4, 7, 39, 53, 53, 39, 7, 9, 75, 154, 306, 154, 75, 9, 13, 155, 436, 1167, 1167, 436, 155, 13, 18, 310, 1268, 4939, 6958, 4939, 1268, 310, 18, 25, 638, 3660, 21313, 40931, 40931, 21313, 3660, 638, 25

Offset: 1

Andrew Howroyd, Aug 01 2017

			Table begins:
===============================================================
m\n|  1   2    3     4       5        6         7          8
---|-----------------------------------------------------------
1  |  1   2    2     4       4        7         9         13...
2  |  2   6    7    18      39       75       155        310...
3  |  2   7   16    53     154      436      1268       3660...
4  |  4  18   53   306    1167     4939     21313      88161...
5  |  4  39  154  1167    6958    40931    254754    1519544...
6  |  7  75  436  4939   40931   349178   3118754   26797630...
7  |  9 155 1268 21313  254754  3118754  40307167  497709474...
8  | 13 310 3660 88161 1519544 26797630 497709474 8863408138...
...

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, Minimal Dominating Set

Rows 1-3 are A253412, A290379, A286848.
Main diagonal is A290382.
Cf. A218354 (dominating sets), A089934 (independent), A286868 (irredundant).
Cf. A286849 (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).

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

A286869 Number of irredundant sets in the grid graph P_n X P_n.

Original entry on oeis.org

2, 11, 113, 4481, 425926, 116003176, 84850904785, 169727130490809, 923777353698065520, 13700760654444668547510

Offset: 1

Andrew Howroyd, Aug 02 2017

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

Main diagonal of A286868.

Cf. A286871 (king graph).

a(10) from Christian Sievers, Nov 23 2023

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

Original entry on oeis.org

1, 2, 2, 2, 6, 2, 4, 9, 9, 4, 6, 18, 32, 18, 6, 8, 54, 103, 103, 54, 8, 13, 99, 383, 590, 383, 99, 13, 17, 216, 1280, 2807, 2807, 1280, 216, 17, 27, 512, 4247, 13138, 21555, 13138, 4247, 512, 27, 40, 1079, 14354, 67564, 150063, 150063, 67564, 14354, 1079, 40

Offset: 1

Andrew Howroyd, Aug 23 2017

			Array begins:
=================================================
m\n|  1   2    3     4       5       6       7
---|---------------------------------------------
1  |  1   2    2     4       6       8      13...
2  |  2   6    9    18      54      99     216...
3  |  2   9   32   103     383    1280    4247...
4  |  4  18  103   590    2807   13138   67564...
5  |  6  54  383  2807   21555  150063 1122252...
6  |  8  99 1280 13138  150063 1598353
7  | 13 216 4247 67564 1122252
...

Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Maximal Irredundant Set

Rows 1-2 are A291055, A291100.
Main diagonal is A290790.
Cf. A286847, A286868.

A290513 Number of irredundant sets in the n-ladder graph.

Original entry on oeis.org

3, 11, 26, 79, 224, 640, 1828, 5225, 14928, 42654, 121873, 348232, 995003, 2843014, 8123337, 23210809, 66320216, 189496620, 541448364, 1547079580, 4420468031, 12630596045, 36089381477, 103118131368, 294639269914, 841872308017, 2405480380385, 6873175192304

Offset: 1

Eric W. Weisstein, Aug 04 2017

nonn

Row 2 of A286868.

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, Ladder Graph
Index entries for linear recurrences with constant coefficients, signature (2, 1, 3, 5, -2, -6, -5, -4, -4, -3, -2, -2).

Cf. A286868 (irredundant sets in m X n grid graph).

Table[RootSum[2 + 2 # + 3 #^2 + 4 #^3 + 4 #^4 + 5 #^5 + 6 #^6 + 2 #^7 - 5 #^8 - 3 #^9 - #^10 - 2 #^11 + #^12 &, -105577159431355949 #^n - 389671420034091247 #^(n + 1) + 29241021604101932 #^(n + 2) + 551171239538727862 #^(n + 3) - 835076245333578054 #^(n + 4) - 823168743731791895 #^(n + 5) + 1288188291747539683 #^(n + 6) + 114497498217658607 #^(n + 7) - 529545500369064866 #^(n + 8) + 763912087212707104 #^(n + 9) - 593709228550713556 #^(n + 10) + 130400048784652699 #^(n + 11) &]/2485579507903393779, {n, 20}] (* Eric W. Weisstein, Aug 05 2017 *)
LinearRecurrence[{2, 1, 3, 5, -2, -6, -5, -4, -4, -3, -2, -2}, {3, 11, 26, 79, 224, 640, 1828, 5225, 14928, 42654, 121873, 348232}, 20] (* Eric W. Weisstein, Aug 05 2017 *)
CoefficientList[Series[(3 + 5 x + x^2 + 7 x^3 - 8 x^4 - 14 x^5 - 3 x^6 - 5 x^7 - 9 x^8 - 3 x^9 - 2 x^10 - 2 x^11)/(1 - 2 x - x^2 - 3 x^3 - 5 x^4 + 2 x^5 + 6 x^6 + 5 x^7 + 4 x^8 + 4 x^9 + 3 x^10 + 2 x^11 + 2 x^12), {x, 0, 20}], x] (* Eric W. Weisstein, Aug 05 2017 *)

Vec((3+5*x+x^2+7*x^3-8*x^4-14*x^5-3*x^6-5*x^7-9*x^8-3*x^9-2*x^10-2*x^11)/(1-2*x-x^2-3*x^3-5*x^4+2*x^5+6*x^6+5*x^7+4*x^8+4*x^9+3*x^10+2*x^11+2*x^12)+O(x^30)) \\ Andrew Howroyd, Aug 04 2017

From Andrew Howroyd, Aug 04 2017: (Start)
a(n) = 2*a(n-1) + a(n-2) + 3*a(n-3) + 5*a(n-4) - 2*a(n-5) - 6*a(n-6) - 5*a(n-7) - 4*a(n-8) - 4*a(n-9) - 3*a(n-10) - 2*a(n-11) - 2*a(n-12).
G.f.: x*(3 + 5*x + x^2 + 7*x^3 - 8*x^4 - 14*x^5 - 3*x^6 - 5*x^7 - 9*x^8 - 3*x^9 - 2*x^10 - 2*x^11) / (1 - 2*x - x^2 - 3*x^3 - 5*x^4 + 2*x^5 + 6*x^6 + 5*x^7 + 4*x^8 + 4*x^9 + 3*x^10 + 2*x^11 + 2*x^12).
(End)

Terms a(11) and beyond from Andrew Howroyd, Aug 04 2017

cp's OEIS Frontend

A286847 Array read by antidiagonals: T(m,n) = number of minimal dominating 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

A286887 Number of irredundant sets in the path graph P_n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A286869 Number of irredundant sets in the grid graph P_n X P_n.

Views

Author

Keywords

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Examples

Links

Crossrefs

A290513 Number of irredundant sets in the n-ladder graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions