A253412 -id:A253412 - cp's OEIS frontend

A264569 T(n,k)=Number of (n+1)X(k+1) arrays of permutations of 0..(n+1)*(k+1)-1 with each element having directed index change 1,0 1,1 0,-1 or -1,1.

1, 1, 1, 1, 2, 1, 2, 4, 4, 2, 2, 8, 10, 8, 2, 4, 24, 44, 31, 16, 3, 4, 64, 143, 192, 79, 32, 4, 7, 160, 633, 1130, 888, 224, 64, 5, 9, 384, 2172, 8356, 7808, 4104, 646, 128, 7, 13, 960, 8409, 47571, 96429, 57265, 18540, 1784, 256, 9, 18, 2432, 32046, 305844, 868613

Offset: 1

R. H. Hardin, Nov 17 2015

Table starts
.1...1.....1.......2.........2...........4.............4...............7
.1...2.....4.......8........24..........64...........160.............384
.1...4....10......44.......143.........633..........2172............8409
.2...8....31.....192......1130........8356.........47571..........305844
.2..16....79.....888......7808.......96429........868613.........8968735
.3..32...224....4104.....57265.....1133040......16284544.......273793368
.4..64...646...18540....403872....13182464.....298587595......8004883334
.5.128..1784...85752...2873739...152082304....5442431797....235814997396
.7.256..5010..389340..20432891..1755041376...99386232806...6882481295560
.9.512.14026.1787832.144677017.20212718576.1803702025944.200087118615516

			Some solutions for n=4 k=4
..1..2..3..4..8....1..5..6..4..8....1..5..3..4..8....1..2..3..4..8
..0..7.11..9.13....0..7..2..9..3....0..7..2..9.13....0.10.11.12.13
..5..6.16.17.18...11.15.16.17.18...11..6.16.17.18....5..6..7.14..9
.10.20.21.12.14...10.20.12.13.14...10.20.21.12.14...16.20.21.19.23
.15.22.23.24.19...21.22.23.24.19...15.22.23.24.19...15.22.17.24.18

R. H. Hardin, Table of n, a(n) for n = 1..179

Column 1 is A000931(n+4).
Column 2 is A000079(n-1).
Row 1 is A253412(n-2).

Empirical for column k:
k=1: a(n) = a(n-2) +a(n-3)
k=2: a(n) = 2*a(n-1)
k=3: [order 15]
k=4: a(n) = 18*a(n-2) +36*a(n-3) -45*a(n-4) -216*a(n-5) -243*a(n-6) for n>7
k=5: [order 84]
k=6: [order 36] for n>40
Empirical for row n:
n=1: a(n) = a(n-2) +a(n-3) +a(n-4) -a(n-6)
n=2: a(n) = 2*a(n-1) +8*a(n-4)
n=3: [order 70]
n=4: [order 56]

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

Original entry on oeis.org

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

A253413 Number of n-bit legal circular binary words with maximal set of 1's.

Original entry on oeis.org

1, 1, 2, 3, 6, 5, 5, 14, 14, 21, 27, 44, 57, 78, 114, 158, 222, 306, 437, 608, 851, 1193, 1674, 2346, 3281, 4605, 6450, 9039, 12662, 17748, 24870, 34844, 48830, 68423, 95882, 134349, 188265, 263810, 369666, 518001, 725859, 1017128, 1425261, 1997178, 2798582

Offset: 0

Steven Finch, Dec 31 2014

An n-bit circular binary word is legal if every 1 has an adjacent 0.

In other words, a(n) is the number of minimal dominating sets in the n-cycle graph C_n. - Eric W. Weisstein, Jul 24 2017

			The only legal circular words with maximal set of 1's are
  0 if n = 1;
  01 & 10 if n = 2;
  011, 101 & 110 if n = 3;
  0011, 0101, 0110, 1001, 1010 & 1100 if n = 4;
  01011, 01101, 10101, 10110 & 11010 if n = 5; and
  010101, 011011, 101010, 101101 & 110110 if n = 6.
From _Eric W. Weisstein_, Jul 24 2017 (Start)
Minimal dominating sets of cycle graph C_n:
  C_1: {1}
  C_2: {{1}, {2}}
  C_3: {{1}, {2}, {3}}
  C_4: {{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}}
  C_5: {{1, 3}, {1, 4}, {2, 4}, {2, 5}, {3, 5}}
  C_6: {{1, 4}, {2, 5}, {3, 6}, {1, 3, 5}, {2, 4, 6}} (End)

Alois P. Heinz, Table of n, a(n) for n = 0..2500 (terms n = 1..1000 from Colin Barker)
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, Cycle Graph
Eric Weisstein's World of Mathematics, Minimal Dominating Set
Index entries for linear recurrences with constant coefficients, signature (0,1,1,1,0,-1).

Asymmetric analog of A001608 (no consecutive 1s but maximal).

Circular analog of A253412.

Join[{1}, Table[RootSum[1 - #^2 - #^3 - #^4 + #^6 &, #^n &], {n, 2, 20}]]  (* Eric W. Weisstein, Jul 24 2017 *)
Join[{1}, LinearRecurrence[{0, 1, 1, 1, 0, -1}, {0, 2, 3, 6, 5, 5}, {2, 20}]] (* Eric W. Weisstein, Jul 24 2017 *)
CoefficientList[Series[(1 + 2 x + 2 x^2 + 3 x^3 - x^4 - 6 x^5 + x^6)/(1 - x^2 - x^3 - x^4 + x^6), {x, 0, 20}], x] (* Eric W. Weisstein, Jul 24 2017 *)

Vec(x*(1 + 2*x + 2*x^2 + 3*x^3 - x^4 - 6*x^5 + x^6) / (1 - x^2 - x^3 - x^4 + x^6) + O(x^100)) \\ Colin Barker, Jul 26 2017

def A253413(n):
    if n > 1:
        c, fs = 0, '0'+str(n)+'b'
        for i in range(2**n):
            s = format(i,fs)
            s = s[-2:]+s+s[:2]
            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
    else:
        return 1 # Chai Wah Wu, Jan 02 2015

a(n) = a(n-2) + a(n-3) + a(n-4) - a(n-6) for n>7. - Chai Wah Wu, Jan 02 2015

G.f.: (1 + x + x^2 + x^3 + 2*x^4 - x^5 - 5*x^6 + x^7) / (1 - x^2 - x^3 - x^4 + x^6). - Paul D. Hanna, Jan 02 2015

a(21)-a(28) from Chai Wah Wu, Jan 02 2015
More terms from Colin Barker, Jul 26 2017
a(0)=1 prepended by Alois P. Heinz, Oct 26 2022

A303072 Number of minimal total dominating sets in the n-ladder graph.

Original entry on oeis.org

1, 4, 4, 16, 16, 49, 81, 169, 324, 625, 1296, 2401, 4900, 9409, 18769, 36481, 71824, 141376, 276676, 544644, 1067089, 2099601, 4116841, 8088336, 15880225, 31181056, 61230625, 120209296, 236083225, 463497841, 910168561, 1787091076, 3509140644, 6890328064, 13529411856

Offset: 1

Eric W. Weisstein, Apr 18 2018

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

Row 2 of A303118.

Cf. A290379, A302402, A303054.

Table[(RootSum[1 - #^2 - #^3 - #^4 + #^6 &, (9 - 18 #^2 + 23 #^3 - 3 #^4 + 32 #^5) #^n &]/229)^2, {n, 40}]
LinearRecurrence[{-1, 1, 3, 7, 8, 2, 6, 6, 0, 0, -6, -6, -2, -8, -7, -3, -1, 1, 1}, {1, 4, 4, 16, 16, 49, 81, 169,324, 625, 1296, 2401, 4900, 9409, 18769, 36481, 71824, 141376, 276676}, 40]
CoefficientList[Series[(-1 - 5 x - 7 x^2 - 13 x^3 - 9 x^4 - x^5 - 4 x^6 + 5 x^7 + 13 x^8 + 14 x^9 + 21 x^10 + 15 x^11 + 12 x^12 + 15 x^13 + 9 x^14 + 3 x^15 - 2 x^17 - x^18)/(-1 - x + x^2 + 3 x^3 + 7 x^4 + 8 x^5 + 2 x^6 + 6 x^7 + 6 x^8 - 6 x^11 - 6 x^12 - 2 x^13 - 8 x^14 - 7 x^15 - 3 x^16 - x^17 + x^18 + x^19), {x, 0, 40}], x]

a(n) = A253412(n)^2.

G.f.: x*(-1 - 5*x - 7*x^2 - 13*x^3 - 9*x^4 - x^5 - 4*x^6 + 5*x^7 + 13*x^8 + 14*x^9 + 21*x^10 + 15*x^11 + 12*x^12 + 15*x^13 + 9*x^14 + 3*x^15 - 2*x^17 - x^18)/(-1 - x + x^2 + 3*x^3 + 7*x^4 + 8*x^5 + 2*x^6 + 6*x^7 + 6*x^8 - 6*x^11 - 6*x^12 - 2*x^13 - 8*x^14 - 7*x^15 - 3*x^16 - x^17 + x^18 + x^19).

cp's OEIS Frontend

A264569 T(n,k)=Number of (n+1)X(k+1) arrays of permutations of 0..(n+1)*(k+1)-1 with each element having directed index change 1,0 1,1 0,-1 or -1,1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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

A253413 Number of n-bit legal circular binary words with maximal set of 1's.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

A303072 Number of minimal total dominating sets in the n-ladder graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula