OFFSET
0,3
COMMENTS
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
LINKS
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).
FORMULA
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
EXAMPLE
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.
MATHEMATICA
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 *)
PROG
(Python)
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
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Steven Finch, Dec 31 2014
EXTENSIONS
Terms a(21) and beyond from Andrew Woods, Jan 02 2015
a(0)=1 prepended by Alois P. Heinz, Oct 26 2022
STATUS
approved