A056513 Number of primitive (period n) periodic palindromic structures using a maximum of two different symbols.

1, 1, 1, 1, 2, 3, 4, 7, 10, 14, 21, 31, 42, 63, 91, 123, 184, 255, 371, 511, 750, 1015, 1519, 2047, 3030, 4092, 6111, 8176, 12222, 16383, 24486, 32767, 49024, 65503, 98175, 131061, 196308, 262143, 392959, 524223, 785910, 1048575, 1572256, 2097151, 3144702, 4194162

Offset

0,5

Comments

For example, aaabbb is not a (finite) palindrome but it is a periodic palindrome. Permuting the symbols will not change the structure.

Number of Lyndon compositions (aperiodic necklaces of positive integers) summing to n that can be rotated to form a palindrome. - Gus Wiseman, Sep 16 2018

References

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

Links

Andrew Howroyd, Table of n, a(n) for n = 0..1000

Formula

a(n) = Sum_{d|n} mu(d)*A056503(n/d) for n > 0.

a(n) = Sum_{k=1..2} A285037(n, k). - Andrew Howroyd, Apr 08 2017

G.f.: 1 + (1/2)*Sum_{k>=1} mu(k)*x^k*(2 + 3*x^k)/(1 - 2*x^(2*k)) - mu(2*k)*x^(2*k)*(1 + x^(2*k))/(1 - 2*x^(4*k)). - Andrew Howroyd, Sep 27 2019

Example

From Gus Wiseman, Sep 16 2018: (Start)
The sequence of palindromic Lyndon compositions begins:
  (1)  (2)  (3)  (4)    (5)    (6)      (7)
                 (112)  (113)  (114)    (115)
                        (122)  (1122)   (133)
                               (11112)  (223)
                                        (11113)
                                        (11212)
                                        (11122)
(End)

Mathematica

(* b = A164090, c = A045674 *)
b[n_] := (1/4)*(7 - (-1)^n)*2^((1/4)*(2*n + (-1)^n - 1));
c[0] = 1;
c[n_] := c[n] = If[EvenQ[n], 2^(n/2 - 1) + c[n/2], 2^((n - 1)/2)];
a56503[n_] := If[OddQ[n], b[n]/2, (1/2)*(b[n] + c[n/2])];
a[n_] := DivisorSum[n, MoebiusMu[#] a56503[n/#]&];
Array[a, 45] (* Jean-François Alcover, Jun 29 2018, after Andrew Howroyd *)

Prog

(PARI) a(n) = {if(n < 1, n==0, sumdiv(n, d, moebius(d)*(2 + d%2)*(2^(n/d\2)))/(4 - n%2))} \\ Andrew Howroyd, Sep 26 2019
(PARI) seq(n) = Vec(1 + (1/2)*sum(k=1, n, moebius(k)*x^k*(2 + 3*x^k)/(1 - 2*x^(2*k)) - moebius(2*k)*x^(2*k)*(1 + x^(2*k))/(1 - 2*x^(4*k)) + O(x*x^n))) \\ Andrew Howroyd, Sep 27 2019

Crossrefs

Row sums of A179317.

Cf. A008965, A025065, A056476, A059966, A242414, A285037, A317085, A317086, A317087, A318731.

Sequence in context: A184639 A035565 A240489 * A056518 A160644 A347734

Adjacent sequences: A056510 A056511 A056512 * A056514 A056515 A056516

Keyword

nonn

Author

Marks R. Nester

Extensions

a(17)-a(45) from Andrew Howroyd, Apr 08 2017

a(0)=1 prepended by Andrew Howroyd, Sep 27 2019

Status

approved