The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A253412 Number of n-bit legal binary words with maximal set of 1s. 5
 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 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,2 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 Andrew Woods, Table of n, a(n) for n = 1..100 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(1) = 1, a(2) = a(3) = 2, a(4) = a(5) = 4, a(6) = 7. - Andrew Woods, Jan 02 2015 G.f.: x*(1 + 2*x + x^2 + x^3 - x^4 - x^5) / (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 Asymmetric analog of A000931 (no consecutive 1s but maximal). Linear analog of A253413. Cf. A303072. Sequence in context: A183566 A222709 A034396 * A291148 A032190 A222737 Adjacent sequences:  A253409 A253410 A253411 * A253413 A253414 A253415 KEYWORD nonn AUTHOR Steven Finch, Dec 31 2014 EXTENSIONS Terms a(21) and beyond from Andrew Woods, Jan 02 2015 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified May 26 13:49 EDT 2020. Contains 334626 sequences. (Running on oeis4.)