A133267 -id:A133267 - cp's OEIS frontend

A006575 Number of primitive (aperiodic, or Lyndon) asymmetric rhythm cycles: ones having no nontrivial shift automorphism.

1, 2, 4, 10, 24, 60, 156, 410, 1092, 2952, 8052, 22140, 61320, 170820, 478288, 1345210, 3798240, 10761660, 30585828, 87169608, 249055976, 713205900, 2046590844, 5883948540, 16945772184, 48882035160, 141214767876

Offset: 1

N. J. A. Sloane

nonn

Asymmetric rhythm cycles (A115114): 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. - Valery A. Liskovets, Jan 17 2006
This sequence differs from the Moebius transform of A115114 (for even n). Coincides with the second row (q=3) of array A098691. - Valery A. Liskovets, Jan 17 2006
This sequence is the number of Lyndon words on {1, 2, 3} with an odd number of 1's. Also, for even n, this sequence represents the differences between the number of Lyndon words on {1, 2, 3} with an odd number of 1's and the number of Lyndon words on {1, 2, 3} with an even number of 1's. - Jennifer Woodcock (jennifer.woodcock(AT)ugdsb.on.ca), Jan 03 2008

			Example. For n=3, out of 6=A115114(3) admissible rhythm cycles (necklaces) 000000, 100000, 110000, 101000, 111000 and 101010, only the first and the last ones are imprimitive. Thus a(3)=4.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Joerg Arndt, Table of n, a(n) for n = 1..200
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].
D. Shanks and M. Lal, Bateman's constants reconsidered and the distribution of cubic residues, Math. Comp., 26 (1972), 265-285.

Cf. A133267. Row q=3 of A098691.

a[n_] := DivisorSum[n, If[BitAnd[#, 1]==1, MoebiusMu[#]*(3^(n/#)-1), 0]&] / (2n); Array[a, 30] (* Jean-François Alcover, Dec 01 2015, after Joerg Arndt *)

a(n) = sumdiv( n, d, if ( bitand(d,1), moebius(d) * (3^(n/d)-1) , 0 ) ) / (2*n); /* Joerg Arndt, Dec 30 2012 */

From Valery A. Liskovets, Jan 17 2006: (Start)
a(n) = (Sum_{d|n, d odd} mu(d)*(3^(n/d)-1))/(2*n).
a(n) = (3^n-1)/(2*n) for n=2^k and a(n) = (Sum_{d|n, d odd} mu(d)*3^(n/d))/(2*n) otherwise. (End)

Edited and extended by Valery A. Liskovets, Jan 17 2006

A136704 Number of Lyndon words on {1,2,3} with an odd number of 1's and an odd number of 2's.

Original entry on oeis.org

0, 1, 2, 5, 12, 30, 78, 205, 546, 1476, 4026, 11070, 30660, 85410, 239144, 672605, 1899120, 5380830, 15292914, 43584804, 124527988, 356602950, 1023295422, 2941974270, 8472886092, 24441017580, 70607383938

Offset: 1

Jennifer Woodcock (jennifer.woodcock(AT)ugdsb.on.ca), Jan 16 2008

nonn

This sequence is also the number of Lyndon words on {1,2,3} with an even number of 1's and an odd number of 2's except that a(1) = 1 in this case.

Also, a Lyndon word is the aperiodic necklace representative which is lexicographically earliest among its cyclic shifts. Thus we can apply the fixed density formulas: L_k(n,d) = Sum L(n-d, n_1,..., n_(k-1)); n_1 + ... +n_(k-1) = d where L(n_0, n_1,...,n_(k-1)) = (1/n) Sum mu(j)*[(n/j)!/((n_0/j)!(n_1/j)!...(n_(k-1)/j)!)]; j|gcd(n_0, n_1,...,n_(k-1)). For this sequence, sum over n_0, n_1 = odd.

			For n = 3, out of 8 possible Lyndon words: 112, 113, 122, 123, 132, 133, 223, 233, only 123 and 132 have an odd number of both 1's and 2's. Thus a(3) = 2.

M. Lothaire, Combinatorics on Words, Addison-Wesley, Reading, MA, 1983.

Amiram Eldar, Table of n, a(n) for n = 1..1000
E. N. Gilbert and John Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
Frank Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
Frank Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]
Frank Ruskey and Joe Sawada, An Efficient Algorithm for Generating Necklaces with Fixed Density, SIAM J. Computing, 29 (1999), 671-684.
Mike Zabrocki, MATH5020 York University Course Website.

Cf. A006575, A027376, A133267, A136703.

Bisections: A253076, A253077.

a[1] = 0;
a[n_] := If[OddQ[n], Sum[MoebiusMu[d] * 3^(n/d), {d, Divisors[n]}], Sum[Boole[OddQ[d]] MoebiusMu[d] * (3^(n/d)-1), {d, Divisors[n]}]]/(4n);
Array[a, 27] (* Jean-François Alcover, Aug 26 2019 *)

a(n) = if (n==1, 0, if (n % 2, sumdiv(n, d, moebius(d)*3^(n/d))/(4*n), sumdiv(n, d, if (d%2, moebius(d)*(3^(n/d)-1)))/(4*n))); \\ Michel Marcus, Aug 26 2019

a(1) = 0; for n>1, if n = odd then a(n) = Sum_{d|n} (mu(d)*3^(n/d))/(4n). If n = even, then a(n) = Sum_{d|n, d odd} (mu(d)*(3^(n/d)-1))/(4n).

A136703 Number of Lyndon words on {1,2,3} with an even number of 1's and an even number of 2's.

Original entry on oeis.org

1, 0, 2, 3, 12, 26, 78, 195, 546, 1452, 4026, 11010, 30660, 85254, 239144, 672195, 1899120, 5379738, 15292914, 43581852, 124527988, 356594898, 1023295422, 2941952130, 8472886092, 24440956260, 70607383938

Offset: 1

Jennifer Woodcock (jennifer.woodcock(AT)ugdsb.on.ca), Jan 16 2008

nonn

A Lyndon word is the aperiodic necklace representative which is lexicographically earliest among its cyclic shifts. Thus we can apply the fixed density formulas: L_k(n,d)=sum L(n-d, n_1,..., n_(k-1)); n_1+...+n_(k-1)=d where L(n_0, n_1,...,n_(k-1))=(1/n)sum mu(j)*[(n/j)!/((n_0/j)!(n_1/j)!...(n_(k-1)/j)!)]; j|gcd(n_0, n_1,...,n_(k-1)). For this sequence, sum over n_0,n_1=even.

			For n=3, out of 8 possible Lyndon words: 112, 113, 122, 123, 132, 133, 223, 233, only 113 and 223 have an even number of both 1's and 2's. Thus a(3)=2.

M. Lothaire, Combinatorics on Words, Addison-Wesley, Reading, MA, 1983.

E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]
F. Ruskey and J. Sawada, An Efficient Algorithm for Generating Necklaces with Fixed Density, SIAM J. Computing, 29 (1999) 671-684.
M. Zabrocki, MATH5020 York University Course Website

Cf. A006575; A027376; A133267; A136704.

a(1)=1; for n>1, if n=odd then a(n)= sum(mu(d)*3^(n/d))/(4n); d|n. If n=even, then a(n)= sum(mu(d)*3^(n/d))/n; d|n -(3/4)*sum(mu(d)*(3^(n/d)-1))/n; d|n, d odd.

A304201 a(n) is the number of cyclic permutations of length n that admit a [1,-1,-1]-gridding.

Original entry on oeis.org

1, 1, 1, 2, 5, 15, 43, 120, 338, 952, 2672, 7494, 21035, 59115, 166433, 469560, 1327802, 3763545, 10692500, 30447858, 86894361, 248506757, 712109663, 2044402512, 5879579540, 16937048040, 48864612668, 141179970820, 408444645375, 1183143522435, 3431241484223, 9961919944284

Offset: 0

Kassie Archer, May 08 2018

nonn

a(n) is the number of permutations of length n that are composed of an increasing segment, followed by a decreasing segment, followed by another decreasing segment. In other words, these permutation have a descent set of the form {i, i+1, ..., n-1} for some i or {i, i+1, ..., n-1}\{j} for some i and j > i.

Cf. A027376, A303979, A133267.

t051168(n, k) = if (n==0, 1, (1/n) * sumdiv(gcd(n, k), d, moebius(d) * binomial(n/d, k/d)));
T303979(n, k) = my(t=sum(j=1, k-1, (-1)^(k+j+1)*t051168(n, j))); if (!(n % 2), t += (-1)^(k+1)*sum(j=1, k-1, if (((n-j) % 4) == 2, t051168(n/2, j/2)))); t;
a027376(n) = if(n<1, n==0, sumdiv(n, d, moebius(n/d)*3^d)/n);
a133267(n) = sumdiv(n, d, moebius(d)*3^(n/d)/n - if (d%2, moebius(d)*(3^(n/d)-1)/(2*n)));
a006575(n) = sumdiv(n, d, if ( bitand(d, 1), moebius(d) * (3^(n/d)-1) , 0 ) ) / (2*n);
a(n) = if (n <= 2, 1, res = a027376(n)/2 - sum(i=2, n-1, (n+1-i)*T303979(n,i)); if (!(n%2), if ((n%4)==2, res += a133267(n/2)/2, res += a006575(n/2)/2)); res); \\ Michel Marcus, May 18 2018

a(n) = A027376(n)/2 - Sum_{i=2..n-1} (n+1-i)*A303979(n,i), when n is odd and n > 2;
a(n) = (A027376(n) + A133267(n/2))/2 - Sum_{i=2..n-1} (n+1-i)*A303979(n,i), when n = 2 (mod 4) and n > 2.
a(n) = (A027376(n) + A006575(n/2))/2 - Sum_{i=2..n-1} (n+1-i)*A303979(n,i), when n = 0 (mod 4) and n > 2.

More terms from Michel Marcus, May 19 2018

cp's OEIS Frontend

A006575 Number of primitive (aperiodic, or Lyndon) asymmetric rhythm cycles: ones having no nontrivial shift automorphism.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A136704 Number of Lyndon words on {1,2,3} with an odd number of 1's and an odd number of 2's.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A136703 Number of Lyndon words on {1,2,3} with an even number of 1's and an even number of 2's.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

A304201 a(n) is the number of cyclic permutations of length n that admit a [1,-1,-1]-gridding.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

Formula

Extensions