A181169 'ADPE(n,k)' triangle read by rows. ADPE(n,k) is the number of aperiodic k-double-palindromes of n up to cyclic equivalence.

0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 2, 2, 1, 0, 0, 2, 1, 2, 1, 0, 0, 3, 3, 3, 3, 1, 0, 0, 3, 3, 4, 3, 3, 1, 0, 0, 4, 3, 6, 6, 3, 4, 1, 0, 0, 4, 4, 8, 5, 8, 4, 4, 1, 0, 0, 5, 5, 10, 10, 10, 10, 5, 5, 1, 0, 0, 5, 4, 12, 10, 17, 10, 12, 4, 5, 1, 0, 0, 6, 6, 15, 15, 20, 20, 15, 15, 6, 6, 1, 0

Offset: 1

Author

John P. McSorley, Oct 07 2010

Keywords

• nonn
• tabl

Comments

A k-composition of n is an ordered collection of k positive integers (parts) which sum to n. A k-composition is aperiodic (primitive) if its period is k, i.e., if it is not the concatenation of at least two smaller compositions. A palindrome is a word which is the same when written backwards.

A k-double-palindrome of n is a k-composition of n which is the concatenation of two palindromes, PP'=P|P', where both |P|, |P'|>=1.

For example 1123532=11|23532 is a 7-double-palindrome of 17 since both 11 and 23532 are palindromes. It is also aperiodic, and so it is an aperiodic 7-double-palindrome of 17. See sequence A181111.

Two k-compositions of n are cyclically equivalent if one can be obtained from the other by a cyclic permutation of its parts.

Let ADPE(n,k) denote the number of aperiodic k-double-palindromes of n up to cyclic equivalence, i.e., the number of cyclic equivalence classes containing at least one aperiodic k-double-palindrome.

This sequence is the `ADPE(n,k)' triangle read by rows.

Examples

			The triangle begins:
  0
  0 0
  0 1 0
  0 1 1 0
  0 2 2 1 0
  0 2 1 2 1 0
  0 3 3 3 3 1 0
  0 3 3 4 3 3 1 0
  0 4 3 6 6 3 4 1 0
  0 4 4 8 5 8 4 4 1 0
  ...
For example, row 8 is: 0 3 3 4 3 3 1 0.
We have ADPE(8,3)=3 because the 6 aperiodic 3-double-palindromes of 8: 116, 611, 224, 422, 233, and 332 come in 3 cyclic equivalence classes: {116, 611, 161}, {224, 422, 242}, and {233, 323, 332}.
We have ADPE(8,4)=4 because there are 4 4-double-palindromes of 8 up to cyclic equivalence, the 4 classes are: {1115, 5111, 1511, 1151}, {1214, 4121, 1412, 2141}, {1133, 3113, 3311, 1331}, and {1232, 2123, 3212, 2321}.
		

References

• John P. McSorley: Counting k-compositions of n with palindromic and related structures. Preprint, 2010.

Links

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

Crossrefs

Row sums are A181314.

If we remove the aperiodic requirement we get sequence A180918.

If we count the aperiodic k-double-palindromes of n (not the number of classes) we get sequence A181111 which is the 'ADP(n, k)' triangle read by rows, where ADP(n, k) is the number of aperiodic k-double-palindromes of n.

Cf. A180424.

Programs

PARI

\\ here RE(n, k) is A119963(n, k).
RE(n, k) = binomial((n-k%2)\2, k\2);
T(n, k) = if(k<=1, 0, sumdiv(gcd(n, k), d, moebius(d)*RE(n/d, k/d))); \\ Andrew Howroyd, Sep 28 2019

Formula

T(n, 1) = 0; T(n, k) = A180424(n, k) for k > 1. - Andrew Howroyd, Sep 28 2019

Extensions

Terms a(56) and beyond from Andrew Howroyd, Sep 27 2019