OFFSET
0,3
COMMENTS
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
LINKS
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).
FORMULA
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
EXAMPLE
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)
MATHEMATICA
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 *)
PROG
(Python)
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
(PARI) 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
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Steven Finch, Dec 31 2014
EXTENSIONS
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
STATUS
approved