A253413 Number of n-bit legal circular binary words with maximal set of 1's.

1, 1, 2, 3, 6, 5, 5, 14, 14, 21, 27, 44, 57, 78, 114, 158, 222, 306, 437, 608, 851, 1193, 1674, 2346, 3281, 4605, 6450, 9039, 12662, 17748, 24870, 34844, 48830, 68423, 95882, 134349, 188265, 263810, 369666, 518001, 725859, 1017128, 1425261, 1997178, 2798582

Offset: 0

Author

Steven Finch, Dec 31 2014

Keywords

• nonn
• easy

Comments

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

In other words, a(n) is the number of minimal dominating sets in the n-cycle graph C_n. - Eric W. Weisstein, Jul 24 2017

Examples

			The only legal circular words with maximal set of 1's are
  0 if n = 1;
  01 & 10 if n = 2;
  011, 101 & 110 if n = 3;
  0011, 0101, 0110, 1001, 1010 & 1100 if n = 4;
  01011, 01101, 10101, 10110 & 11010 if n = 5; and
  010101, 011011, 101010, 101101 & 110110 if n = 6.
From _Eric W. Weisstein_, Jul 24 2017 (Start)
Minimal dominating sets of cycle graph C_n:
  C_1: {1}
  C_2: {{1}, {2}}
  C_3: {{1}, {2}, {3}}
  C_4: {{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}}
  C_5: {{1, 3}, {1, 4}, {2, 4}, {2, 5}, {3, 5}}
  C_6: {{1, 4}, {2, 5}, {3, 6}, {1, 3, 5}, {2, 4, 6}} (End)
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..2500 (terms n = 1..1000 from Colin Barker)
• 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, Cycle Graph
• Eric Weisstein's World of Mathematics, Minimal Dominating Set
• Index entries for linear recurrences with constant coefficients, signature (0,1,1,1,0,-1).

Crossrefs

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

Circular analog of A253412.

Programs

Mathematica

Join[{1}, Table[RootSum[1 - #^2 - #^3 - #^4 + #^6 &, #^n &], {n, 2, 20}]]  (* Eric W. Weisstein, Jul 24 2017 *)
Join[{1}, LinearRecurrence[{0, 1, 1, 1, 0, -1}, {0, 2, 3, 6, 5, 5}, {2, 20}]] (* Eric W. Weisstein, Jul 24 2017 *)
CoefficientList[Series[(1 + 2 x + 2 x^2 + 3 x^3 - x^4 - 6 x^5 + x^6)/(1 - x^2 - x^3 - x^4 + x^6), {x, 0, 20}], x] (* Eric W. Weisstein, Jul 24 2017 *)

PARI

Vec(x*(1 + 2*x + 2*x^2 + 3*x^3 - x^4 - 6*x^5 + x^6) / (1 - x^2 - x^3 - x^4 + x^6) + O(x^100)) \\ Colin Barker, Jul 26 2017

Python

def A253413(n):
    if n > 1:
        c, fs = 0, '0'+str(n)+'b'
        for i in range(2**n):
            s = format(i,fs)
            s = s[-2:]+s+s[:2]
            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
    else:
        return 1 # Chai Wah Wu, Jan 02 2015

Formula

a(n) = a(n-2) + a(n-3) + a(n-4) - a(n-6) for n>7. - Chai Wah Wu, Jan 02 2015

G.f.: (1 + x + x^2 + x^3 + 2*x^4 - x^5 - 5*x^6 + x^7) / (1 - x^2 - x^3 - x^4 + x^6). - Paul D. Hanna, Jan 02 2015

Extensions

a(21)-a(28) from Chai Wah Wu, Jan 02 2015

More terms from Colin Barker, Jul 26 2017

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