A093305 - OEIS

%I #60 Jan 25 2024 17:02:56

%S 1,2,3,4,5,9,11,19,29,48,75,132,213,369,627,1083,1857,3244,5619,9844,

%T 17205,30229,53115,93701,165313,292464,517831,918578,1630933,2900109,

%U 5161443,9197251,16402841,29283026,52319379,93558968,167427845,299846737,537358107,963651447,1729192433

%N Number of binary necklaces of length n with no subsequence 000.

%D Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 500.

%H Michael De Vlieger, <a href="/A093305/b093305.txt">Table of n, a(n) for n = 1..500</a>

%H P. Flajolet and M. Soria, <a href="/A093305/a093305.pdf">The Cycle Construction</a>, SIAM J. Discr. Math., vol. 4 (1), 1991, pp. 58-60.

%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="https://cs.uwaterloo.ca/journals/JIS/VOL19/Hadjicostas/hadji2.html">Cyclic Compositions of a Positive Integer with Parts Avoiding an Arithmetic Sequence</a>, Journal of Integer Sequences, 19 (2016), #16.8.2.

%H Silvana Ramaj, <a href="https://digitalcommons.georgiasouthern.edu/cgi/viewcontent.cgi?article=3464&amp;context=etd">New Results on Cyclic Compositions and Multicompositions</a>, Master's Thesis, Georgia Southern Univ., 2021. See p. 57.

%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)*A001644(d).

%F G.f.: Sum_{k>=1} phi(k)/k * log( 1/(1-B(x^k)) ) where B(x) = x*(1+x+x^2). - _Joerg Arndt_, Aug 06 2012

%F a(n) ~ d^n / n, where d = (19 + 3*sqrt(33))^(1/3)/3 + 4/(3*(19 + 3*sqrt(33))^(1/3)) + 1/3 = A058265 = 1.8392867552141611325518... - _Vaclav Kotesovec_, Jul 13 2019

%t Table[1/n * Sum[EulerPhi[n/d] (d Sum[Sum[Binomial[j, d - 3 k + 2 j] Binomial[k, j], {j, d - 3 k, k}]/k, {k, d}]), {d, Divisors@ n}], {n, 41}] (* _Michael De Vlieger_, Dec 28 2016, after _Vladimir Joseph Stephan Orlovsky_ at A001644 *)

%o (PARI)

%o N=66;  x='x+O('x^N);

%o B(x)=x*(1+x+x^2);

%o A=sum(k=1, N, eulerphi(k)/k*log(1/(1-B(x^k))));

%o Vec(A)

%o /* _Joerg Arndt_, Aug 06 2012 */

%Y Row 3 of A322057.

%Y Cf. A000358, A001644, A280218, A280303.

%K easy,nonn

%O 1,2

%A _Philippe Deléham_, Apr 24 2004