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

%I #72 Aug 06 2024 10:54:29

%S 1,1,2,2,4,4,7,9,13,18,25,36,49,70,97,137,191,268,376,526,738,1033,

%T 1449,2029,2844,3985,5584,7825,10964,15365,21529,30169,42274,59238,

%U 83008,116316,162991,228393,320041,448462,628417,880580,1233929,1729066,2422885,3395113,4757463

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

%C An n-bit binary word is legal if every 1 has an adjacent 0.

%C 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 In other words, the number of minimal dominating sets in the n-path graph P_n. - _Eric W. Weisstein_, Jul 24 2017

%H 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 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 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 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MinimalDominatingSet.html">Minimal Dominating Set</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PathGraph.html">Path Graph</a>

%H <a href="/index/Rec#order_06">Index entries for linear recurrences with constant coefficients</a>, signature (0,1,1,1,0,-1).

%F 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 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 a(n) = sqrt(A303072(n)). - _Eric W. Weisstein_, Apr 18 2018

%e The only legal words with maximal set of 1s are:

%e 0 if n = 1;

%e 01 & 10 if n = 2;

%e 010 & 101 if n = 3;

%e 0110, 1001, 0101 & 1010 if n = 4;

%e 01010, 01101, 10101 & 10110 if n = 5; and

%e 010101, 010110, 011001, 011010, 100110, 101010 & 101101 if n = 6.

%t LinearRecurrence[{0, 1, 1, 1, 0, -1}, {1, 2, 2, 4, 4, 7}, 50] (* _Harvey P. Dale_, May 08 2017 *)

%t 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 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 (Python)

%o def A253412(n):

%o c, fs = 0, '0'+str(n)+'b'

%o for i in range(2**n):

%o s = '01'+format(i,fs)+'10'

%o for j in range(n):

%o 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 break

%o else:

%o c += 1

%o return c # _Chai Wah Wu_, Jan 02 2015

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

%Y Linear analog of A253413.

%Y Cf. A303072.

%K nonn,easy

%O 0,3

%A _Steven Finch_, Dec 31 2014

%E Terms a(21) and beyond from _Andrew Woods_, Jan 02 2015

%E a(0)=1 prepended by _Alois P. Heinz_, Oct 26 2022