A253413 - OEIS

%I #67 Oct 26 2022 19:57:03

%S 1,1,2,3,6,5,5,14,14,21,27,44,57,78,114,158,222,306,437,608,851,1193,

%T 1674,2346,3281,4605,6450,9039,12662,17748,24870,34844,48830,68423,

%U 95882,134349,188265,263810,369666,518001,725859,1017128,1425261,1997178,2798582

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

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

%C 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

%H Alois P. Heinz, <a href="/A253413/b253413.txt">Table of n, a(n) for n = 0..2500</a> (terms n = 1..1000 from Colin Barker)

%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="http://www.csis.pace.edu/~ctappert/srd2005/b3.pdf">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/CycleGraph.html">Cycle Graph</a>

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

%F 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

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

%e 0 if n = 1; 01 & 10 if n = 2; 011, 101 & 110 if n = 3;

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

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

%e 010101, 011011, 101010, 101101 & 110110 if n = 6.

%e From _Eric W. Weisstein_, Jul 24 2017 (Start)

%e Minimal dominating sets of cycle graph C_n:

%e C_1: {1}

%e C_2: {{1}, {2}}

%e C_3: {{1}, {2}, {3}}

%e C_4: {{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}}

%e C_5: {{1, 3}, {1, 4}, {2, 4}}, {2, 5}, {3, 5}}

%e C_6: {{1, 4}, {2, 5}, {3, 6}, {1, 3, 5}, {2, 4, 6}} (End)

%t Join[{1}, Table[RootSum[1 - #^2 - #^3 - #^4 + #^6 &, #^n &], {n, 2, 20}]]  (* _Eric W. Weisstein_, Jul 24 2017 *)

%t Join[{1}, LinearRecurrence[{0, 1, 1, 1, 0, -1}, {0, 2, 3, 6, 5, 5}, {2, 20}]] (* _Eric W. Weisstein_, Jul 24 2017 *)

%t 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 *)

%o (Python)

%o def A253413(n):

%o ....if n > 1:

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

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

%o ............s = format(i,fs)

%o ............s = s[-2:]+s+s[:2]

%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

%o ....else:

%o ........return 1 # _Chai Wah Wu_, Jan 02 2015

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

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

%Y Circular analog of A253412.

%K nonn,easy

%O 0,3

%A _Steven Finch_, Dec 31 2014

%E a(21)-a(28) from _Chai Wah Wu_, Jan 02 2015

%E More terms from _Colin Barker_, Jul 26 2017

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