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

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

Author

Steven Finch, Dec 31 2014

Keywords

• nonn
• easy

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

Examples

			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.
		

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

Crossrefs

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

Linear analog of A253413.

Cf. A303072.

Programs

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

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

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

Extensions

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

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