|
%I #29 May 08 2024 02:29:31
%S 0,1,2,5,12,30,78,205,546,1476,4026,11070,30660,85410,239144,672605,
%T 1899120,5380830,15292914,43584804,124527988,356602950,1023295422,
%U 2941974270,8472886092,24441017580,70607383938
%N Number of Lyndon words on {1,2,3} with an odd number of 1's and an odd number of 2's.
%C 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.
%C 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.
%D M. Lothaire, Combinatorics on Words, Addison-Wesley, Reading, MA, 1983.
%H Amiram Eldar, <a href="/A136704/b136704.txt">Table of n, a(n) for n = 1..1000</a>
%H E. N. Gilbert and John Riordan, <a href="https://doi.org/10.1215/ijm/1255631587">Symmetry types of periodic sequences</a>, Illinois J. Math., 5 (1961), 657-665.
%H Frank Ruskey, <a href="http://combos.org/necklace">Necklaces, Lyndon words, De Bruijn sequences, etc.</a>
%H Frank Ruskey, <a href="/A000011/a000011.pdf">Necklaces, Lyndon words, De Bruijn sequences, etc.</a> [Cached copy, with permission, pdf format only]
%H Frank Ruskey and Joe Sawada, <a href="http://dx.doi.org/10.1137/S0097539798344112">An Efficient Algorithm for Generating Necklaces with Fixed Density</a>, SIAM J. Computing, 29 (1999), 671-684.
%H Mike Zabrocki, <a href="http://garsia.math.yorku.ca/~zabrocki/math5020y0708/">MATH5020 York University Course Website</a>.
%F 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).
%e 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.
%t a[1] = 0;
%t 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);
%t Array[a, 27] (* _Jean-François Alcover_, Aug 26 2019 *)
%o (PARI) 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
%Y Cf. A006575, A027376, A133267, A136703.
%Y Bisections: A253076, A253077.
%K nonn
%O 1,3
%A Jennifer Woodcock (jennifer.woodcock(AT)ugdsb.on.ca), Jan 16 2008
|
