|
|
A253412
|
|
Number of n-bit legal binary words with maximal set of 1s.
|
|
5
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
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.
|
|
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
|
|
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)
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
|
|
CROSSREFS
|
Asymmetric analog of A000931 (no consecutive 1s but maximal).
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|