A303072 -id:A303072 - cp's OEIS frontend

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

0, 1, 1, 2, 4, 2, 1, 4, 4, 1, 2, 16, 6, 16, 2, 4, 16, 49, 49, 16, 4, 3, 49, 66, 169, 66, 49, 3, 4, 81, 225, 576, 576, 225, 81, 4, 8, 169, 640, 2601, 2622, 2601, 640, 169, 8, 9, 324, 1681, 10000, 14400, 14400, 10000, 1681, 324, 9, 10, 625, 4641, 38416, 81055, 137641, 81055, 38416, 4641, 625, 10

Offset: 1

Andrew Howroyd, Apr 18 2018

			Table begins:
=============================================================
m\n| 1   2    3     4      5       6         7          8
---+---------------------------------------------------------
1  | 0   1    2     1      2       4         3          4 ...
2  | 1   4    4    16     16      49        81        169 ...
3  | 2   4    6    49     66     225       640       1681 ...
4  | 1  16   49   169    576    2601     10000      38416 ...
5  | 2  16   66   576   2622   14400     81055     440896 ...
6  | 4  49  225  2601  14400  137641   1081600    8185321 ...
7  | 3  81  640 10000  81055 1081600  11458758  125955729 ...
8  | 4 169 1681 38416 440896 8185321 125955729 1944369025 ...
...

Andrew Howroyd, Table of n, a(n) for n = 1..435 (first 29 antidiagonals)
Eric Weisstein's World of Mathematics, Grid Graph.
Eric Weisstein's World of Mathematics, Minimal Total Dominating Set.

Rows 1..2 are A302655, A303072.
Main diagonal is A303161.
Cf. A300358, A303111, A303293.

A253412 Number of n-bit legal binary words with maximal set of 1s.

Original entry on oeis.org

1, 1, 2, 2, 4, 4, 7, 9, 13, 18, 25, 36, 49, 70, 97, 137, 191, 268, 376, 526, 738, 1033, 1449, 2029, 2844, 3985, 5584, 7825, 10964, 15365, 21529, 30169, 42274, 59238, 83008, 116316, 162991, 228393, 320041, 448462, 628417, 880580, 1233929, 1729066, 2422885, 3395113, 4757463

Offset: 0

Steven Finch, Dec 31 2014

An n-bit binary word is legal if every 1 has an adjacent 0.
The set of 1s is maximal if changing any 0 to a 1 makes the word illegal. For example, a maximal word cannot contain 000, 0100, or 0010, and cannot start or end with 00. - Andrew Woods, Jan 02 2015
In other words, the number of minimal dominating sets in the n-path graph P_n. - Eric W. Weisstein, Jul 24 2017

			The only legal words with maximal set of 1s are:
0 if n = 1;
01 & 10 if n = 2;
010 & 101 if n = 3;
0110, 1001, 0101 & 1010 if n = 4;
01010, 01101, 10101 & 10110 if n = 5; and
010101, 010110, 011001, 011010, 100110, 101010 & 101101 if n = 6.

Alois P. Heinz, Table of n, a(n) for n = 0..2500 (terms n = 1..100 from Andrew Woods)
Tomislav Došlić, Mate Puljiz, Stjepan Šebek, and Josip Žubrinić, On a variant of Flory model, arXiv:2210.12411 [math.CO], 2022.
M. L. Gargano, A. Weisenseel, J. Malerba and M. Lewinter, Discrete Renyi parking constants, 36th Southeastern Conf. on Combinatorics, Graph Theory, and Computing, Boca Raton, 2005, Congr. Numer. 176 (2005) 43-48.
Eric Weisstein's World of Mathematics, Minimal Dominating Set
Eric Weisstein's World of Mathematics, Path Graph
Index entries for linear recurrences with constant coefficients, signature (0,1,1,1,0,-1).

Asymmetric analog of A000931 (no consecutive 1s but maximal).
Linear analog of A253413.
Cf. A303072.

LinearRecurrence[{0, 1, 1, 1, 0, -1}, {1, 2, 2, 4, 4, 7}, 50] (* Harvey P. Dale, May 08 2017 *)
CoefficientList[Series[(1 + 2 x + x^2 + x^3 - x^4 - x^5)/(1 - x^2 - x^3 - x^4 + x^6), {x, 0, 20}], x] (* Eric W. Weisstein, Jul 24 2017 *)
Table[RootSum[1 - #^2 - #^3 - #^4 + #^6 &, 9 #^n - 18 #^(n + 2) + 23 #^(n + 3) - 3 #^(n + 4) + 32 #^(n + 5) &]/229, {n, 20}] (* Eric W. Weisstein, Aug 04 2017 *)

def A253412(n):
    c, fs = 0, '0'+str(n)+'b'
    for i in range(2**n):
        s = '01'+format(i,fs)+'10'
        for j in range(n):
            if s[j:j+4] == '0100' or s[j+1:j+5] == '0010' or s[j+1:j+4] == '000' or s[j+1:j+4] == '111':
                break
        else:
            c += 1
    return c # Chai Wah Wu, Jan 02 2015

a(n) = a(n-2) + a(n-3) + a(n-4) - a(n-6), for n >= 6, with a(0) = a(1) = 1, a(2) = a(3) = 2, a(4) = a(5) = 4, a(6) = 7. - Andrew Woods, Jan 02 2015
G.f.: (1 + x^2)*(1 + x -x^3) / (1 - x^2 - x^3 - x^4 + x^6). - Paul D. Hanna, Jan 02 2015
a(n) = sqrt(A303072(n)). - Eric W. Weisstein, Apr 18 2018

Terms a(21) and beyond from Andrew Woods, Jan 02 2015

a(0)=1 prepended by Alois P. Heinz, Oct 26 2022

A303054 Number of minimum total dominating sets in the n-ladder graph.

Original entry on oeis.org

1, 4, 1, 16, 9, 1, 64, 16, 1, 169, 25, 1, 361, 36, 1, 676, 49, 1, 1156, 64, 1, 1849, 81, 1, 2809, 100, 1, 4096, 121, 1, 5776, 144, 1, 7921, 169, 1, 10609, 196, 1, 13924, 225, 1, 17956, 256, 1, 22801, 289, 1, 28561, 324, 1, 35344, 361, 1, 43264, 400, 1, 52441

Offset: 1

Eric W. Weisstein, Apr 17 2018

Each vertex can dominate up to three others. A ladder with a length that is an exact multiple of three can be dominated in only one way with 2n/3 vertices. - Andrew Howroyd, Apr 21 2018

			From _Andrew Howroyd_, Apr 21 2018: (Start)
a(9) = 1 because there is only one arrangement of 6 vertices that is totally dominating and no set with fewer vertices can be totally dominating:
  .__o__.__.__o__.__.__o__.
     |        |        |
  .__o__.__.__o__.__.__o__.
(End)

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

Row 2 of A303293.

Cf. A302402, A303072.

Table[Piecewise[{{1, Mod[n, 3] == 0}, {((n^2 + 13 n + 4)/18)^2, Mod[n, 3] == 1}, {((n + 4)/3)^2, Mod[n, 3] == 2}}], {n, 58}] (* Eric W. Weisstein, Apr 23 2018 and Michael De Vlieger, Apr 21 2018 *)
Table[(916 + 392 n + 213 n^2 + 26 n^3 + n^4 - (-56 + 392 n + 213 n^2 + 26 n^3 + n^4) Cos[2 n Pi/3] + Sqrt[3] (-20 + 7 n + n^2) (28 + 19 n + n^2) Sin[2 n Pi/3])/972, {n, 20}] (* Eric W. Weisstein, Apr 23 2018 *)
LinearRecurrence[{0, 0, 5, 0, 0, -10, 0, 0, 10, 0, 0, -5, 0, 0, 1}, {1, 4, 1, 16, 9, 1, 64, 16, 1, 169, 25, 1, 361, 36, 1}, 20] (* Eric W. Weisstein, Apr 23 2018 *)
CoefficientList[Series[(-1 - 4 x - x^2 - 11 x^3 + 11 x^4 + 4 x^5 + 6 x^6 - 11 x^7 - 6 x^8 + x^9 + 5 x^10 + 4 x^11 - x^12 - x^13 - x^14)/(-1 + x^3)^5, {x, 0, 20}], x] (* Eric W. Weisstein, Apr 23 2018 *)

a(n)={if(n%3==0, 1, if(n%3==1, (n^2 + 13*n + 4)/18, (n + 4)/3))^2} \\ Andrew Howroyd, Apr 21 2018

Vec(x*(1 + 4*x + x^2 + 11*x^3 - 11*x^4 - 4*x^5 - 6*x^6 + 11*x^7 + 6*x^8 - x^9 - 5*x^10 - 4*x^11 + x^12 + x^13 + x^14) / ((1 - x)^5*(1 + x + x^2)^5) + O(x^60)) \\ Colin Barker, Apr 23 2018

a(n) = 1 for n mod 3 = 0
     = ((n^2 + 13*n + 4)/18)^2 for n mod 3 = 1
     = ((n + 4)/3)^2 for n mod 3 = 2.
G.f.: x*(-1 - 4*x - x^2 - 11*x^3 + 11*x^4 + 4*x^5 + 6*x^6 - 11*x^7 - 6*x^8 + x^9 + 5*x^10 + 4*x^11 - x^12 - x^13 - x^14)/(-1 + x^3)^5.
a(n) = 5*a(n-3) - 10*a(n-6) + 10*a(n-9) - 5*a(n-12) + a(n-15) for n>15. - Colin Barker, Apr 23 2018

Terms a(14) and beyond from Andrew Howroyd, Apr 21 2018

cp's OEIS Frontend

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

Views

Author

Keywords

Examples

Links

Crossrefs

A253412 Number of n-bit legal binary words with maximal set of 1s.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A303054 Number of minimum total dominating sets in the n-ladder graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions