cp's OEIS Frontend

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

%I A253412 #73 Feb 16 2025 08:33:24
%S A253412 1,1,2,2,4,4,7,9,13,18,25,36,49,70,97,137,191,268,376,526,738,1033,
%T A253412 1449,2029,2844,3985,5584,7825,10964,15365,21529,30169,42274,59238,
%U A253412 83008,116316,162991,228393,320041,448462,628417,880580,1233929,1729066,2422885,3395113,4757463
%N A253412 Number of n-bit legal binary words with maximal set of 1s.
%C A253412 An n-bit binary word is legal if every 1 has an adjacent 0.
%C A253412 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
%C A253412 In other words, the number of minimal dominating sets in the n-path graph P_n. - _Eric W. Weisstein_, Jul 24 2017
%H A253412 Alois P. Heinz, <a href="/A253412/b253412.txt">Table of n, a(n) for n = 0..2500</a> (terms n = 1..100 from Andrew Woods)
%H A253412 Tomislav Došlić, Mate Puljiz, Stjepan Šebek, and Josip Žubrinić, <a href="https://arxiv.org/abs/2210.12411">On a variant of Flory model</a>, arXiv:2210.12411 [math.CO], 2022.
%H A253412 M. L. Gargano, A. Weisenseel, J. Malerba and M. Lewinter, <a href="https://citeseerx.ist.psu.edu/pdf/be85da9afe6c6838031af1e5a94897214fbf5be5">Discrete Renyi parking constants</a>, 36th Southeastern Conf. on Combinatorics, Graph Theory, and Computing, Boca Raton, 2005, Congr. Numer. 176 (2005) 43-48.
%H A253412 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/MinimalDominatingSet.html">Minimal Dominating Set</a>
%H A253412 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PathGraph.html">Path Graph</a>
%H A253412 <a href="/index/Rec#order_06">Index entries for linear recurrences with constant coefficients</a>, signature (0,1,1,1,0,-1).
%F A253412 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
%F A253412 G.f.: (1 + x^2)*(1 + x -x^3) / (1 - x^2 - x^3 - x^4 + x^6). - _Paul D. Hanna_, Jan 02 2015
%F A253412 a(n) = sqrt(A303072(n)). - _Eric W. Weisstein_, Apr 18 2018
%e A253412 The only legal words with maximal set of 1s are:
%e A253412 0 if n = 1;
%e A253412 01 & 10 if n = 2;
%e A253412 010 & 101 if n = 3;
%e A253412 0110, 1001, 0101 & 1010 if n = 4;
%e A253412 01010, 01101, 10101 & 10110 if n = 5; and
%e A253412 010101, 010110, 011001, 011010, 100110, 101010 & 101101 if n = 6.
%t A253412 LinearRecurrence[{0, 1, 1, 1, 0, -1}, {1, 2, 2, 4, 4, 7}, 50] (* _Harvey P. Dale_, May 08 2017 *)
%t A253412 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 *)
%t A253412 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 *)
%o A253412 (Python)
%o A253412 def A253412(n):
%o A253412     c, fs = 0, '0'+str(n)+'b'
%o A253412     for i in range(2**n):
%o A253412         s = '01'+format(i,fs)+'10'
%o A253412         for j in range(n):
%o A253412             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':
%o A253412                 break
%o A253412         else:
%o A253412             c += 1
%o A253412     return c # _Chai Wah Wu_, Jan 02 2015
%Y A253412 Asymmetric analog of A000931 (no consecutive 1s but maximal).
%Y A253412 Linear analog of A253413.
%Y A253412 Cf. A303072.
%K A253412 nonn,easy
%O A253412 0,3
%A A253412 _Steven Finch_, Dec 31 2014
%E A253412 Terms a(21) and beyond from _Andrew Woods_, Jan 02 2015
%E A253412 a(0)=1 prepended by _Alois P. Heinz_, Oct 26 2022