A006575 -id:A006575 - cp's OEIS frontend

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

2, 1, 4, 8, 24, 56, 156, 400, 1092, 2928, 8052, 22080, 61320, 170664, 478288, 1344800, 3798240, 10760568, 30585828, 87166656, 249055976, 713197848, 2046590844, 5883926400, 16945772184, 48881973840, 141214767876, 408513980160, 1183282368360, 3431518388960

Offset: 1

Jennifer Woodcock (jennifer.woodcock(AT)ugdsb.on.ca), Jan 03 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=even. Alternatively, a(n)=(sum mu(d)*3^(n/d)/n; d|n) - (sum mu(d)*(3^(n/d)-1)/(2n); d|n, d odd).

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

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

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

Cf. A006575, A027376.

with(numtheory): a:= n-> add(mobius(d) *3^(n/d), d=divisors(n))/n -add(mobius(d) *(3^(n/d)-1), d=select(x-> irem(x, 2)=1, divisors(n)))/ (2*n): seq(a(n), n=1..30);  # Alois P. Heinz, Jul 29 2011

a[n_] := DivisorSum[n, MoebiusMu[#]*(3^(n/#) - (1/2)*Boole[OddQ[#]]*(3^(n/#)-1))&]/n; Table[a[n], {n, 1, 30}] (* Jean-François Alcover, Mar 21 2017, after Alois P. Heinz *)

a133267(n) = sumdiv(n, d, moebius(d)*3^(n/d)/n - if (d%2, moebius(d)*(3^(n/d)-1)/(2*n))); \\ Michel Marcus, May 17 2018

a(1)=2; for n>1, if n=2^k for some k, then a(n) = ((3^(n/2)-1)^2)/(2*n). Otherwise, if n is even then a(n) = Sum_{d|n, d odd} mu(d)*(3^(n/d)-2*3^(n/(2*d)))/(2*n). If n is odd then a(n) = Sum_{d|n, d odd} mu(d)*(3^(n/d)-1)/(2*n).

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

A098691 Array T(q,n) by antidiagonals: number of self-reciprocal polynomials of degree 2*n over GF(q) (for q >= 2 and n >= 1).

Original entry on oeis.org

1, 1, 1, 2, 2, 1, 2, 4, 4, 2, 3, 6, 10, 10, 3, 3, 9, 20, 32, 24, 5, 4, 12, 35, 78, 102, 60, 9, 4, 16, 56, 162, 312, 340, 156, 16, 5, 20, 84, 300, 777, 1300, 1170, 410, 28, 5, 25, 120, 512, 1680, 3885, 5580, 4096, 1092, 51, 6, 30, 165, 820, 3276, 9800, 19995, 24414

Offset: 2

Ralf Stephan, Sep 21 2004

Also, number of self-complementary primitive necklaces of length n in q colors.

			  [q=2]: 1,  1,  1,   2,    3,    5,     9,     16, ...
  [q=3]: 1,  2,  4,  10,   24,   60,   156,    410, ...
  [q=4]: 2,  4, 10,  32,  102,  340,  1170,   4096, ...
  [q=5]: 2,  6, 20,  78,  312, 1300,  5580,  24414, ...
  [q=6]: 3,  9, 35, 162,  777, 3885, 19995, 104976, ...
  [q=7]: 3, 12, 56, 300, 1680, 9800, 58824, 360300, ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 2..1276
H. Meyn and W. Götz, Self-reciprocal polynomials over finite fields, Séminaire Lotharingien de Combinatoire, B21d (1989), 8 pp.
R. L. Miller, Necklaces, symmetries and self-reciprocal polynomials, Discr. Math. 22 (1978), 25-33.

Rows are A000048 (q=2), A006575 (q=3).
Columns 1-4 are A004526, A002620, A000292, 2*A011863.
Main diagonal is in A098692.

T(q,n) = sumdiv(n, d, if(d%2, moebius(d) * (q^(n/d)-q%2), 0)) / (2*n); \\ Andrew Howroyd, Aug 21 2019

T(q,n) = {if(q%2 && n == 2^logint(n,2), q^n-1, sumdiv(n, d, if(d%2, moebius(d)*q^(n/d)))) / (2*n)} \\ Andrew Howroyd, Aug 22 2019

T(q, n) = (q^n-1)/(2*n) for q odd and n=2^s; otherwise Sum_{d|n, d odd} mu(d)*q^(n/d) / (2*n).

T(q, n) = Sum_{d|n, d odd} mu(d) * (q^(n/d) - (q mod 2)) / (2*n). - Andrew Howroyd, Aug 21 2019

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.

Original entry on oeis.org

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

Valery A. Liskovets, Jan 17 2006

			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.

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].

Cf. A000016, A006575.

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

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.

a(n) ~ 3^n/(2*n). - Vaclav Kotesovec, Oct 27 2024

A115116 Number of imprimitive (periodic) asymmetric rhythm cycles: ones having nontrivial shift automorphisms. 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.

Original entry on oeis.org

1, 1, 2, 1, 2, 3, 2, 1, 6, 3, 2, 11, 2, 3, 30, 1, 2, 63, 2, 11, 162, 3, 2, 411, 26, 3, 1098, 11, 2, 3015, 2, 1, 8058, 3, 182, 22151, 2, 3, 61326, 411, 2, 170883, 2, 11, 479410, 3, 2, 1345211, 158, 2955, 3798246, 11, 2, 10761723, 8078, 411, 30585834, 3, 2, 87191759, 2, 3, 249057230, 1, 61346, 713205963, 2, 11, 2046590850, 173775, 2

Offset: 1

Valery A. Liskovets, Jan 17 2006

a(2^k)=1 for all k including k=0.

a(p)=2, a(2p)=3, a(4p)=11, etc. for an odd prime p.

Antti Karttunen, Table of n, a(n) for n = 1..6300
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].

Cf. A006575, A115114.

A006575[n_] := DivisorSum[n, If[BitAnd[#, 1] == 1, MoebiusMu[#] (3^(n/#) - 1), 0]&]/(2n);
A115114[n_] := Sum[EulerPhi[2d] + Boole[OddQ[d]] EulerPhi[d] 3^(n/d), {d, Divisors[n]}]/(2n);
a[n_] := A115114[n] - A006575[n];
Array[a, 60] (* Jean-François Alcover, Aug 29 2019 *)

A006575(n) = (sumdiv(n,d,bitand(d,1)*moebius(d)*(3^(n/d)-1)) / (2*n)); \\ From A006575.
A115114(n) = (1/(2*n))*(sumdiv(n,d,eulerphi(2*d)+(bitand(d,1)*eulerphi(d)*(3^(n/d)))));
A115116(n) = (A115114(n) - A006575(n)); \\ Antti Karttunen, Jan 19 2020

a(n) = A115114(n) - A006575(n).

More terms from Antti Karttunen, Jan 19 2020

A115117 Number of primitive (aperiodic, or Lyndon) 3-asymmetric rhythm cycles: ones having no nontrivial shift automorphism. 3-asymmetric rhythm cycles (A115115): binary necklaces of length 3n subject to the restriction that for any k if the k-th bead is of color 1 then the (k+n)-th and (k+2n)-th beads (modulo 3n) are of color 0.

Original entry on oeis.org

1, 2, 7, 20, 68, 224, 780, 2720, 9709, 34918, 127100, 465920, 1720740, 6390930, 23860928, 89477120, 336860180, 1272578048, 4822419420, 18325176316, 69810262080, 266548209850, 1019836872140, 3909374443520, 15011998757888

Offset: 1

Valery A. Liskovets, Jan 17 2006

Jinyuan Wang, Table of n, a(n) for n = 1..1000
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.

Cf. A006575, A115115.

a[n_] := Sum[MoebiusMu[3d] + Boole[GCD[3, d] == 1] MoebiusMu[d] 4^(n/d), {d, Divisors[n]}]/(3n);
Array[a, 25] (* Jean-François Alcover, Aug 30 2019 *)

a(n) = 1/(3*n) * sumdiv(n,d, moebius(3*d) + if(gcd(3,d)==1, moebius(d)*4^(n/d),0) ); \\ Joerg Arndt, Aug 29 2019

a(n) = (Sum_{d|n} mu(3d) + Sum_{d|n, (3,d)=1} mu(d) 4^(n/d))/(3n), where mu(n) is the Moebius function A008683.

a(n) ~ 4^n / (3*n). - Vaclav Kotesovec, Oct 27 2024

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.

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

Original entry on oeis.org

1, 1, 1, 2, 5, 15, 42, 120, 338, 952, 2671, 7494, 21035, 59115, 166432, 469560, 1327802, 3763545, 10692500, 30447858, 86894361, 248506757, 712109662, 2044402512, 5879579540, 16937048040, 48864612667, 141179970820, 408444645375, 1183143522435, 3431241484224, 9961919944284

Offset: 0

Kassie Archer, May 03 2018

nonn

a(n) is the number of cyclic permutations that, when written in their one-line notation, is composed of an increasing segment, followed by another increasing segment, followed by a decreasing segment.

Cf. A027376, A303979, A006575.

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);
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, i*T303979(n,i)); if (!(n%2), res += a006575(n/2)/2); res); \\ Michel Marcus, May 16 2018

a(n) = A027376(n)/2 - Sum_{i=2..n-1} i*A303979(n,i) when n is odd and n>2.

a(n) = (A027376(n)+A006575(n/2))/2 - Sum_{i=2..n-1} i*A303979(n,i) when n is even and n>2.

More terms from Michel Marcus, May 16 2018

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

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

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

A098691 Array T(q,n) by antidiagonals: number of self-reciprocal polynomials of degree 2*n over GF(q) (for q >= 2 and n >= 1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

PARI

Formula

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.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A115116 Number of imprimitive (periodic) asymmetric rhythm cycles: ones having nontrivial shift automorphisms. 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.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

Views

Author

Keywords

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