A115114 Asymmetric rhythm cycles (patterns): binary necklaces of length 2n subject to the restriction that for any k if the k-th bead is of color 1 then the (k+n)-th bead (modulo 2n) is of color 0.

2, 3, 6, 11, 26, 63, 158, 411, 1098, 2955, 8054, 22151, 61322, 170823, 478318, 1345211, 3798242, 10761723, 30585830, 87169619, 249056138, 713205903, 2046590846, 5883948951, 16945772210, 48882035163, 141214768974

Offset

1,1

Links

Table of n, a(n) for n=1..27.

R. W. Hall and P. Klingsberg, Asymmetric Rhythms, Tiling Canons and Burnside's Lemma, Bridges Proceedings, pp. 189-194, 2004 (Winfield, Kansas).

R. W. Hall and P. Klingsberg, Asymmetric Rhythms and Tiling Canons, Preprint, 2004; The American Mathematical Monthly, Volume 113, 2006 - Issue 10, [alternative link].

Formula

a(n) = (Sum_{d|n}phi(2d)+Sum_{d|n, d odd}phi(d)3^(n/d))/(2n), where phi(n) is the Euler function A000010.

Example

For n=3, the 27=3^3 admissible words are separated into 6 shift-equivalence classes (necklaces) containing, resp., the words 000000, 100000, 110000, 101000, 111000 and 101010. Thus a(3)=6.

Mathematica

a[n_] := Sum[EulerPhi[2d] + Boole[OddQ[d]] EulerPhi[d] 3^(n/d), {d, Divisors[n]}]/(2n);
Array[a, 27] (* Jean-François Alcover, Aug 29 2019 *)

Crossrefs

Cf. A000016, A006575.

Sequence in context: A051603 A094927 A024423 * A356715 A324768 A086209

Adjacent sequences: A115111 A115112 A115113 * A115115 A115116 A115117

Keyword

easy,nonn

Author

Valery A. Liskovets, Jan 17 2006

Status

approved