|
%I #35 Jan 25 2024 17:03:20
%S 1,2,3,5,7,12,17,31,51,91,155,287,505,930,1695,3129,5759,10724,19913,
%T 37239,69643,130745,245715,463099,873705,1651838,3126707,5927817,
%U 11251031,21382558,40679233,77475673,147694719,281822847,538213671,1028714071,1967728553
%N Number of binary necklaces of length n with no subsequence 00000.
%C a(n) is the number of cyclic sequences of length n consisting of zeros and ones that do not contain five consecutive zeros provided we consider as equivalent those sequences that are cyclic shifts of each other.
%H Andrew Howroyd, <a href="/A280303/b280303.txt">Table of n, a(n) for n = 1..1000</a>
%H P. Flajolet and M. Soria, <a href="http://dx.doi.org/10.1137/0404006">The Cycle Construction</a>, SIAM J. Discr. Math., vol. 4 (1), 1991, pp. 58-60.
%H Petros Hadjicostas, <a href="/A280303/a280303.pdf">Proof of the formula for the generating function from the formula for a(n)</a>
%H F. Ruskey, <a href="http://combos.org/necklace">Necklaces, Lyndon words, De Bruijn sequences, etc.</a>
%H F. Ruskey, <a href="/A000011/a000011.pdf">Necklaces, Lyndon words, De Bruijn sequences, etc.</a> [Cached copy, with permission, pdf format only]
%H L. Zhang and P. Hadjicostas, <a href="http://www.appliedprobability.org/data/files/TMS%20articles/40_2_3.pdf">On sequences of independent Bernoulli trials avoiding the pattern '11..1'</a>, Math. Scientist, 40 (2015), 89-96.
%F a(n) = (1/n) * Sum_{d divides n} totient(n/d) * A074048(d).
%F G.f.: Sum_{k>=1} (phi(k)/k) * log(1/(1-B(x^k))) where B(x) = x*(1+x+x^2+x^3+x^4).
%e a(5)=7 because we have seven binary cyclic sequences (necklaces) of length 5 that avoid five consecutive zeros: 00001, 00011, 00101, 00111, 01101, 01111, 11111.
%Y Row 5 of A322057.
%Y Cf. A000358, A093305, A280218, A074048.
%K nonn
%O 1,2
%A _Petros Hadjicostas_ and Lingyun Zhang, Dec 31 2016
%E a(34) onwards from _Andrew Howroyd_, Jan 25 2024
|
