A253413 -id:A253413 - 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).

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

A300738 Number of minimal total dominating sets in the n-cycle graph.

Original entry on oeis.org

0, 0, 3, 4, 5, 9, 7, 4, 12, 25, 22, 25, 39, 49, 68, 100, 119, 144, 209, 289, 367, 484, 644, 841, 1130, 1521, 1983, 2601, 3480, 4624, 6107, 8100, 10717, 14161, 18807, 24964, 33004, 43681, 57918, 76729, 101639, 134689, 178364, 236196, 313007, 414736, 549289

Offset: 1

Andrew Howroyd, Apr 15 2018

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

Cf. A001608, A001638 (total dominating sets), A253413, A302653, A302655, A302918.

Table[RootSum[-1 - # + #^3 &, #^n &] + (1 + (-1)^n) RootSum[-1 + #^2 + #^3 &, #^(n/2) &], {n, 20}]
Perrin[n_] := RootSum[-1 - # + #^3 &, #^n &]; Table[With[{b = Mod[n, 2, 1]}, Perrin[n/b]^b], {n, 20}]
LinearRecurrence[{0, 0, 1, 1, 1, 1, 0, -1, -1}, {0, 0, 3, 4, 5, 9, 7, 4, 12}, 20]
CoefficientList[Series[x^2 (3 + 4 x + 5 x^2 + 6 x^3 - 8 x^5 - 9 x^6)/(1 - x^3 - x^4 - x^5 - x^6 + x^8 + x^9), {x, 0, 20}], x]

concat([0,0], Vec((3 + 4*x + 5*x^2 + 6*x^3 - 8*x^5 - 9*x^6)/((1 - x^2 - x^3)*(1 + x^2 - x^6)) + O(x^50)))

a(n) = a(n-3) + a(n-4) + a(n-5) + a(n-6) - a(n-8) - a(n-9) for n > 9.
G.f.: x^3*(3 + 4*x + 5*x^2 + 6*x^3 - 8*x^5 - 9*x^6)/((1 - x^2 - x^3)*(1 + x^2 - x^6)).
a(2*n) = A001608(n)^2.
a(2*n-1) = A001608(2*n-1), where A001608 are the Perrin numbers.

A290270 Number of minimal dominating sets in the n-wheel graph.

Original entry on oeis.org

3, 4, 7, 6, 6, 15, 15, 22, 28, 45, 58, 79, 115, 159, 223, 307, 438, 609, 852, 1194, 1675, 2347, 3282, 4606, 6451, 9040, 12663, 17749, 24871, 34845, 48831, 68424, 95883, 134350, 188266, 263811, 369667, 518002, 725860, 1017129, 1425262, 1997179, 2798583

Offset: 3

Eric W. Weisstein, Jul 25 2017

nonn

The n-wheel graph is well defined for n >= 4. If the sequence is extended to n=1 using A253413 then the initial terms are 1,2,3,4,... If the sequence is extended using the recurrence the initial terms are 7,1,3,4,... - Andrew Howroyd, Jul 27 2017

Vincenzo Librandi, Table of n, a(n) for n = 3..1000
Eric Weisstein's World of Mathematics, Minimal Dominating Set
Eric Weisstein's World of Mathematics, Wheel Graph
Index entries for linear recurrences with constant coefficients, signature (1, 1, 0, 0, -1, -1, 1).

Cf. A253413.

I:=[3,4,7,6,6,15,15,22,28]; [n le 9 select I[n] else Self(n-2)+Self(n-3)+Self(n-4)-Self(n-6)-1: n in [1..50]]; // Vincenzo Librandi, Aug 04 2017

Table[1 + RootSum[1 - #1^2 - #1^3 - #1^4 + #1^6 &, #^(n - 1) &], {n, 3, 20}] (* Eric W. Weisstein, Aug 04 2017 *)
LinearRecurrence[{1, 1, 0, 0, -1, -1, 1}, {3, 4, 7, 6, 6, 15, 15}, 20] (* Eric W. Weisstein, Aug 04 2017 *)
CoefficientList[Series[(3 + x - 5 x^3 - 7 x^4 + 6 x^5 + x^6)/((1 - x^2 - x^3 - x^4 + x^6) (1-x)), {x, 0,33}], x] (* Vincenzo Librandi, Aug 04 2017 *)

Vec(((7-6*x-5*x^2+2*x^5+x^6)) / ((1-x^2-x^3-x^4+x^6)*(1-x)) + O(x^40)) \\ Andrew Howroyd, Jul 27 2017

From Andrew Howroyd, Jul 27 2017: (Start)
a(n) = A253413(n-1) + 1 for n > 2.
a(n) = a(n-2) + a(n-3) + a(n-4) - a(n-6) - 1 for n>8.
G.f.: x*(7 - 6*x - 5*x^2 + 2*x^5 + x^6) / ((1 - x^2 - x^3 -x^4 + x^6)*(1 - x)).
(End)
G.f.: x^3*(3+x-5*x^3-7*x^4+6*x^5+x^6)/((1-x^2-x^3-x^4+x^6)*(1-x)). - Vincenzo Librandi, Aug 04 2017

a(3) and a(16)-a(45) from Andrew Howroyd, Jul 27 2017

A347638 Number of minimal dominating sets in the n-dipyramidal graph (for n > 3).

Original entry on oeis.org

3, 7, 10, 15, 16, 18, 29, 31, 40, 48, 67, 82, 105, 143, 189, 255, 341, 474, 647, 892, 1236, 1719, 2393, 3330, 4656, 6503, 9094, 12719, 17807, 24931, 34907, 48895, 68490, 95951, 134420, 188338, 263885, 369743, 518080, 725940, 1017211, 1425346, 1997265, 2798671

Offset: 1

Eric W. Weisstein, Sep 09 2021

The 3-dipyramidal graph deviates from this sequence because it has 4 minimal dominating sets while a(3) = 10.

Eric Weisstein's World of Mathematics, Dipyramidal Graph
Eric Weisstein's World of Mathematics, Minimal Dominating Set
Index entries for linear recurrences with constant coefficients, signature (2,0,-1,0,-1,0,2,-1).

Cf. A253413.

Table[2 n + 1 + RootSum[1 - #^2 - #^3 - #^4 + #^6 &, #^n &], {n, 20}]
LinearRecurrence[{2, 0, -1, 0, -1, 0, 2, -1}, {3, 7, 10, 15, 16, 18, 29, 31}, 20]
CoefficientList[Series[(3 + x - 4 x^2 - 2 x^3 - 7 x^4 - x^5 + 15 x^6 - 7 x^7)/((-1 + x)^2 (1 - x^2 - x^3 - x^4 + x^6)), {x, 0, 20}], x]

a(n) = A253413(n)+2*n+1.
a(n) = 2*a(n-1)-a(n-3)-a(n-5)+2*a(n-7)-a(n-8).
G.f.: x*(3+x-4*x^2-2*x^3-7*x^4-x^5+15*x^6-7*x^7)/((-1+x)^2*(1-x^2-x^3-x^4+x^6)).

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

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

A300738 Number of minimal total dominating sets in the n-cycle graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A290270 Number of minimal dominating sets in the n-wheel graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions

A347638 Number of minimal dominating sets in the n-dipyramidal graph (for n > 3).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula