login
Number of primitive (period n) periodic palindromes using a maximum of two different symbols.
7

%I #40 Feb 12 2022 15:32:51

%S 2,1,2,3,6,7,14,18,28,39,62,81,126,175,246,360,510,728,1022,1485,2030,

%T 3007,4094,6030,8184,12159,16352,24381,32766,48849,65534,97920,131006,

%U 196095,262122,392364,524286,785407,1048446,1571310,2097150,3143497

%N Number of primitive (period n) periodic palindromes using a maximum of two different symbols.

%C For example, aaabbb is not a (finite) palindrome but it is a periodic palindrome.

%C Also number of aperiodic necklaces (Lyndon words) with two colors that are the same when turned over.

%D M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for a pdf file of Chap. 2]

%H <a href="/index/Lu#Lyndon">Index entries for sequences related to Lyndon words</a>

%F Sum_{d|n} mu(d)*b(n/d), where b(n) = A029744(n+1). [Corrected by _Petros Hadjicostas_, Oct 15 2017. The original formula referred to a previous version of sequence A029744 that had a different offset.]

%F More generally, let gf(k) be the g.f. for the number of necklaces with reflectional symmetry but no rotational symmetry and beads of k colors. Then gf(k): Sum_{n >= 1} mu(n)*Sum_{i=0..2} binomial(k,i)*x^(n*i)/(1 - k*x^(2*n)). - _Herbert Kociemba_, Nov 29 2016

%F G.f.: Sum_{n >= 1} mu(n)*x^n*(2 + 3*x^n)/(1 - 2*x^(2*n)). The g.f. by _Herbet Kociemba_ above, with k = 2, becomes Sum_{n>=1} mu(n)*(x^n + 1)^2/(1 - 2*x^(2*n)). The two formulae differ by the "undetermined" constant Sum_{n >= 1} mu(n). - _Petros Hadjicostas_, Oct 15 2017

%e a(1) = 2 with aaa... and bbb..., a(2) = 1 with ababab..., a(3) = 2 with aabaab... and abbabb..., a(4) = 3 with aaabaaab... and aabbaabb... and abbbabbb.... - _Michael Somos_, Nov 29 2016

%t mx=40;gf[x_,k_]:=Sum[ MoebiusMu[n]*Sum[Binomial[k,i]x^(n i),{i,0,2}]/( 1-k x^(2n)),{n,mx}]; CoefficientList[Series[gf[x,2],{x,0,mx}],x] (* _Herbert Kociemba_, Nov 29 2016 *)

%Y Column 2 of A284856.

%Y Cf. A029744, A056391, A056458.

%K nonn

%O 1,1

%A _Marks R. Nester_

%E More terms and additional comments from _Christian G. Bower_, Jun 22 2000