A106369 Number of circular compositions of n such that no two adjacent parts are equal.

1, 1, 2, 2, 3, 6, 7, 11, 18, 29, 42, 73, 111, 183, 299, 491, 796, 1333, 2188, 3652, 6073, 10155, 16959, 28500, 47813, 80508, 135621, 228967, 386749, 654535, 1108353, 1879478, 3189495, 5418556, 9212099, 15676275, 26694509, 45493327, 77580915

Offset

1,3

Comments

By "circular compositions" here we mean equivalence classes of compositions with parts on a circle such that two compositions are equivalent if one is a cyclic shift of the other. - Petros Hadjicostas, Oct 15 2017

Links

Vaclav Kotesovec, Table of n, a(n) for n = 1..1000

P. Hadjicostas, Cyclic, dihedral and symmetric Carlitz compositions of a positive integer, Journal of Integer Sequences, 20 (2017), Article 17.8.5.

Petros Hadjicostas, Proof of an explicit formula for Bower's CycleBG transform

Index entries for sequences related to necklaces

Formula

CycleBG transform of (1, 1, 1, 1, ...).

CycleBG transform T(A) = invMOEBIUS(invEULER(Carlitz(A)) + A(x^2) - A) + A.

Carlitz transform T(A(x)) has g.f. 1/(1 - Sum_{k>0} (-1)^(k+1)*A(x^k)).

G.f.: x/(1-x) - Sum_{s>=1} (phi(s)/s)*f(x^s), where f(x) = log(1 - Sum_{n>=1} x^n/(1 + x^n)) + Sum_{n>=1} log(1 + x^n) and phi(s)=A000010 is Euler's totient function. - Petros Hadjicostas, Sep 06 2017

Conjecture: a(n) ~ A241902^n / n. - Vaclav Kotesovec, Sep 06 2017

General formula for the CycleBG transform: T(A)(x) = A(x) - Sum_{k>=0} A(x^(2k+1)) + Sum_{k>=1} (phi(k)/k)*log(Carlitz(A)(x^k)). For a proof, see the links above. (For this sequence, A(x) = x/(1-x).) - Petros Hadjicostas, Oct 08 2017

G.f.: -Sum_{s>=1} x^(2s+1)/(1-x^(2s+1)) - Sum_{s>=1} (phi(s)/s)*g(x^s), where g(x) = log(1 + Sum_{n>=1} (-x)^n/(1 - x^n)). (This formula can be proved from the general formula for the CycleBG transform given above.) - Petros Hadjicostas, Oct 10 2017

Example

a(6) = 6 because the 6 circular compositions of 6: 6, 5+1, 4+2, 3+2+1, 3+1+2, 2+1+2+1.

Mathematica

nmax = 40; Rest[CoefficientList[Series[x/(1-x) - Sum[EulerPhi[s]/s*(Log[1 - Sum[x^(s*n)/(1 + x^(s*n)), {n, 1, nmax}]] + Sum[Log[1 + x^(s*n)], {n, 1, nmax}]), {s, 1, nmax}], {x, 0, nmax}], x]] (* Vaclav Kotesovec, Sep 06 2017, after Petros Hadjicostas *)

Crossrefs

Cf. A000031, A008965, A212322, A292906.

Sequence in context: A241744 A308514 A039866 * A298436 A228577 A032062

Adjacent sequences: A106366 A106367 A106368 * A106370 A106371 A106372

Keyword

nonn

Author

Christian G. Bower, Apr 29 2005

Extensions

Name clarified by Andrew Howroyd, Oct 12 2017

Status

approved