A056458 -id:A056458 - cp's OEIS frontend

A284823 Array read by antidiagonals: T(n,k) = number of primitive (aperiodic) palindromes of length n using a maximum of k different symbols (n >= 1, k >= 1).

1, 2, 0, 3, 0, 0, 4, 0, 2, 0, 5, 0, 6, 2, 0, 6, 0, 12, 6, 6, 0, 7, 0, 20, 12, 24, 4, 0, 8, 0, 30, 20, 60, 18, 14, 0, 9, 0, 42, 30, 120, 48, 78, 12, 0, 10, 0, 56, 42, 210, 100, 252, 72, 28, 0, 11, 0, 72, 56, 336, 180, 620, 240, 234, 24, 0, 12, 0, 90, 72, 504, 294, 1290, 600, 1008, 216, 62

Offset: 1

Andrew Howroyd, Apr 03 2017

			Table starts:
1  2   3    4    5    6     7     8     9    10 ...
0  0   0    0    0    0     0     0     0     0 ...
0  2   6   12   20   30    42    56    72    90 ...
0  2   6   12   20   30    42    56    72    90 ...
0  6  24   60  120  210   336   504   720   990 ...
0  4  18   48  100  180   294   448   648   900 ...
0 14  78  252  620 1290  2394  4088  6552  9990 ...
0 12  72  240  600 1260  2352  4032  6480  9900 ...
0 28 234 1008 3100 7740 16758 32704 58968 99900 ...
0 24 216  960 3000 7560 16464 32256 58320 99000 ...
...
Row 4 includes palindromes of the form abba but excludes those of the form aaaa, so T(4,k) is k*(k-1).
Row 6 includes palindromes of the forms aabbaa, abbbba, abccba but excludes those of the forms aaaaaa, abaaba, so T(6,k) is 2*k*(k-1) + k*(k-1)*(k-2).

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]

Andrew Howroyd, Table of n, a(n) for n = 1..1275

Columns 2-6 are A056458, A056459, A056460, A056461, A056462.
Rows 5-10 are A007531(k+1), A045991, A058895, A047928(k-1), A135497, A133754.
Cf. A284826, A284841.

T[n_, k_] := DivisorSum[n, MoebiusMu[n/#]*k^Ceiling[#/2]&]; Table[T[n-k+1, k], {n, 1, 12}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, Jun 05 2017 *)

a(n,k) = sumdiv(n, d, moebius(n/d) * k^(ceil(d/2)));
for(n=1, 10, for(k=1, 10, print1( a(n,k),", ");); print();)

T(n,k) = Sum_{d | n} mu(n/d) * k^(ceiling(d/2)).

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

Original entry on oeis.org

2, 1, 2, 3, 6, 7, 14, 18, 28, 39, 62, 81, 126, 175, 246, 360, 510, 728, 1022, 1485, 2030, 3007, 4094, 6030, 8184, 12159, 16352, 24381, 32766, 48849, 65534, 97920, 131006, 196095, 262122, 392364, 524286, 785407, 1048446, 1571310, 2097150, 3143497

Offset: 1

Marks R. Nester

nonn

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

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

			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

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]

Index entries for sequences related to Lyndon words

Column 2 of A284856.

Cf. A029744, A056391, A056458.

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

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

More terms and additional comments from Christian G. Bower, Jun 22 2000

A056476 Number of primitive (aperiodic) palindromic structures of length n using a maximum of two different symbols.

Original entry on oeis.org

1, 1, 0, 1, 1, 3, 2, 7, 6, 14, 12, 31, 27, 63, 56, 123, 120, 255, 238, 511, 495, 1015, 992, 2047, 2010, 4092, 4032, 8176, 8127, 16383, 16242, 32767, 32640, 65503, 65280, 131061, 130788, 262143, 261632, 524223, 523770, 1048575, 1047494, 2097151, 2096127, 4194162

Offset: 0

Marks R. Nester

nonn

Permuting the symbols will not change the structure.

a(n) = A056481(n) for n > 1. - Jonathan Frech, May 21 2021

			Example from _Jonathan Frech_, May 21 2021: (Start)
The a(9)=14 lexicographically earliest equivalence class members in the alphabet {0,1} are:
  000010000
  000101000
  000111000
  001000100
  001010100
  001101100
  001111100
  010000010
  010101010
  010111010
  011000110
  011010110
  011101110
  011111110
(End)

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]

Michael De Vlieger, Table of n, a(n) for n = 0..5000

Cf. A056458, A056481, A284826.

Table[DivisorSum[n, MoebiusMu[#]*2^Floor[(n/# - 1)/2] &], {n, 46}] (* Michael De Vlieger, May 21 2021 *)

a(n) = if(n==0, 1, sumdiv(n, d, moebius(d)*2^((n/d-1)\2))) \\ Andrew Howroyd, May 21 2021

from sympy import mobius, divisors
def A056476(n): return sum(mobius(n//d)<<(d-1>>1) for d in divisors(n, generator=True)) if n else 1 # Chai Wah Wu, Feb 18 2024

a(n) = Sum_{d|n} mu(d)*A016116(n/d-1) for n > 0.
a(n) = Sum_{k=1..2} A284826(n, k) for n > 0. - Andrew Howroyd, May 21 2021
a(n) = A056458(n)/2 for n>=1. - Alois P. Heinz, Feb 18 2025

Definition clarified by Jonathan Frech, May 21 2021

a(0)=1 prepended and a(32)-a(45) from Andrew Howroyd, May 21 2021

A056463 Number of primitive (aperiodic) palindromes using exactly two different symbols.

Original entry on oeis.org

0, 0, 2, 2, 6, 4, 14, 12, 28, 24, 62, 54, 126, 112, 246, 240, 510, 476, 1022, 990, 2030, 1984, 4094, 4020, 8184, 8064, 16352, 16254, 32766, 32484, 65534, 65280, 131006, 130560, 262122, 261576, 524286, 523264, 1048446, 1047540, 2097150, 2094988, 4194302, 4192254

Offset: 1

Marks R. Nester

nonn

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]

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

Column 2 of A327873.

Cf. A056453, A056458.

seq(n)={Vec(sum(k=1, n\3, moebius(k)*2*x^(3*k)/((1 - 2*x^(2*k))*(1 - x^k)) + O(x*x^n)), -n)} \\ Andrew Howroyd, Sep 29 2019

from sympy import mobius, divisors
def A056463(n): return sum(mobius(n//d)*((1<<(d+1>>1))-2) for d in divisors(n, generator=True)) # Chai Wah Wu, Feb 18 2024

a(n) = Sum_{d|n} mu(d)*A056453(n/d).

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

Terms a(32) and beyond from Andrew Howroyd, Sep 28 2019

A370410 Number of length-n binary strings that are the concatenation of two nonempty palindromes.

Original entry on oeis.org

0, 4, 6, 14, 26, 48, 86, 148, 232, 400, 622, 982, 1514, 2440, 3482, 5680, 8162, 12932, 18398, 29146, 40706, 64856, 90070, 141880, 196448, 309712, 425412, 668978, 917450, 1437148, 1966022, 3074080, 4192882, 6545344, 8912278, 13877920, 18874298, 29341624, 39842594, 61835140, 83886002, 129977116, 176160686, 272563362

Offset: 1

Jeffrey Shallit, Feb 18 2024

nonn

a(6618) has 1001 digits. - Michael S. Branicky, Feb 21 2024

Michael S. Branicky, Table of n, a(n) for n = 1..6617
Michael S. Branicky, Python program for A370410 (bitwise operations)
Michael S. Branicky, Python program for A370410 (explicit construction)
R. C. Lyndon and M. P. Schützenberger, The equation a^M = b^N c^P in a free group, Michigan Math. J., 9(4):289-298, 1962.

Cf. A007055 (allows the palindromes to be empty), A056458.

# see below and Links for faster programs
from itertools import product
def p(w): return w == w[::-1]
def c(w): return any(p(w[:i]) and p(w[i:]) for i in range(1, len(w)))
def a(n): return 2*sum(1 for w in product("01", repeat=n-1) if c(("1",)+w))
print([a(n) for n in range(1, 21)]) # Michael S. Branicky, Feb 18 2024

from itertools import product
def bin_pals(d): yield from ("".join(p+(m,)+p[::-1]) for p in product("01", repeat=d//2) for m in [[""], ["0", "1"]][d%2])
def a(n): return len(set(a+b for i in range(1, n) for a in bin_pals(i) for b in bin_pals(n-i)))
print([a(n) for n in range(1, 21)]) # Michael S. Branicky, Feb 18 2024

# uses formula above; functions/imports in A007055, A056458
def a(n): return A007055(n) - A056458(n)
print([a(n) for n in range(1, 45)]) # Michael S. Branicky, Feb 21 2024

a(n) = A007055(n) - A056458(n) (conjectured). - Michael S. Branicky, Feb 18 2024
From Daniel Gabric, Feb 21 2024: (Start)
Proof of the above formula: Let w be a length-n binary string that is the concatenation of two possibly empty palindromes. It suffices to show that w is not the concatenation of two nonempty palindromes iff w is a primitive palindrome.
We prove the forward direction. Suppose w is not the concatenation of two nonempty palindromes. By assumption, w is the concatenation of two possibly empty palindromes. Therefore, w must be a palindrome. Suppose, for the sake of a contradiction, that w is not primitive. Then w = z^i for some nonempty string z and some integer i>=2. But since w is a palindrome, we have that z^i = w = w^R = (z^i)^R = (z^R)^i, which implies z is a palindrome. Thus, w is the concatenation of the nonempty palindromes z and z^(i-1), a contradiction.
Now we prove the backward direction.  Assume, for the sake of a contradiction, that w is a primitive palindrome, and w = uv for some nonempty palindromes u and v. Then uv = w = w^R = (uv)^R = v^Ru^R = vu. By Lemma 3 in a paper of Lyndon and Schützenberger (see links for reference), uv = vu implies w is not primitive, a contradiction. (End)

a(21)-a(44) from Michael S. Branicky, Feb 18 2024

cp's OEIS Frontend

A284823 Array read by antidiagonals: T(n,k) = number of primitive (aperiodic) palindromes of length n using a maximum of k different symbols (n >= 1, k >= 1).

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A056476 Number of primitive (aperiodic) palindromic structures of length n using a maximum of two different symbols.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

A056463 Number of primitive (aperiodic) palindromes using exactly two different symbols.

Views

Author

Keywords

References

Links

Crossrefs

Programs

PARI

Python

Formula

Extensions

A370410 Number of length-n binary strings that are the concatenation of two nonempty palindromes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

Python

Python

Formula

Extensions