A093305 Number of binary necklaces of length n with no subsequence 000.

1, 2, 3, 4, 5, 9, 11, 19, 29, 48, 75, 132, 213, 369, 627, 1083, 1857, 3244, 5619, 9844, 17205, 30229, 53115, 93701, 165313, 292464, 517831, 918578, 1630933, 2900109, 5161443, 9197251, 16402841, 29283026, 52319379, 93558968, 167427845, 299846737, 537358107, 963651447, 1729192433

Offset: 1

Author

Philippe Deléham, Apr 24 2004

Keywords

• easy
• nonn

References

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

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..500
• P. Flajolet and M. Soria, The Cycle Construction, SIAM J. Discr. Math., vol. 4 (1), 1991, pp. 58-60.
• P. Flajolet and M. Soria, The Cycle Construction, SIAM J. Discr. Math., vol. 4 (1), 1991, pp. 58-60.
• Petros Hadjicostas, Cyclic Compositions of a Positive Integer with Parts Avoiding an Arithmetic Sequence, Journal of Integer Sequences, 19 (2016), #16.8.2.
• Silvana Ramaj, New Results on Cyclic Compositions and Multicompositions, Master's Thesis, Georgia Southern Univ., 2021. See p. 57.
• L. Zhang and P. Hadjicostas, On sequences of independent Bernoulli trials avoiding the pattern '11..1', Math. Scientist, 40 (2015), 89-96.

Crossrefs

Row 3 of A322057.

Cf. A000358, A001644, A280218, A280303.

Programs

Mathematica

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

PARI

N=66;  x='x+O('x^N);
B(x)=x*(1+x+x^2);
A=sum(k=1, N, eulerphi(k)/k*log(1/(1-B(x^k))));
Vec(A)
/* Joerg Arndt, Aug 06 2012 */

Formula

a(n) = (1/n) * Sum_{d divides n} totient(n/d)*A001644(d).

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

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