A181111 'ADP(n,k)' triangle read by rows. ADP(n,k) is the number of aperiodic k-double-palindromes of n.

0, 0, 0, 0, 2, 0, 0, 2, 2, 0, 0, 4, 4, 4, 0, 0, 4, 2, 6, 4, 0, 0, 6, 6, 12, 12, 6, 0, 0, 6, 6, 14, 12, 16, 6, 0, 0, 8, 6, 24, 24, 18, 24, 8, 0, 0, 8, 8, 28, 20, 44, 24, 28, 8, 0, 0, 10, 10, 40, 40, 60, 60, 40, 40, 10, 0, 0, 10, 8, 44, 40, 94, 60, 88, 32, 46, 10, 0

Offset: 1

Author

John P. McSorley, Oct 03 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. The 4-double-palindrome of 8 1313=131|3 is not aperiodic, so it is not an aperiodic 4-double-palindrome of 8.

Let ADP(n,k) denote the number of aperiodic k-double-palindromes of n.

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

Examples

			The triangle begins:
  0
  0 0
  0 2 0
  0 2 2  0
  0 4 4  4  0
  0 4 2  6  4  0
  0 6 6 12 12  6  0
  0 6 6 14 12 16  6  0
  0 8 6 24 24 18 24  8 0
  0 8 8 28 20 44 24 28 8 0
  ...
For example, row 8 is: 0 6 6 14 12 16 6 0.
We have ADP(8,3)=6 because there are 6 aperiodic 3-double-palindromes of 8: 116, 611, 224, 422, 233, and 332.
We have ADP(8,4)=14 because there are 14 4-double-palindromes of 8: 1115, 5111, 1511, 1151, 1214, 4121, 1412, 2141, 1133, 3311, 1232, 2123, 3212, and 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 A181135.

See sequence A180653 for the triangle whose (n, k) term gives the number of k-double-palindromes of n.

See sequence A179519 for the triangle whose (n, k) term gives the number of aperiodic k-palindromes (single-palindromes) of n.

Cf. A180279, A180918, A181169.

Programs

PARI

\\ here p(n,k) is A119963(n,k), q(n,k) is A051159(n-1, k-1).
p(n, k) = { binomial((n-k%2)\2, k\2) }
q(n, k) = { if(n%2==1&&k%2==0, 0, binomial((n-1)\2, (k-1)\2)) }
T(n, k) = sumdiv(gcd(n, k), d, moebius(d) * (k*p(n/d, k/d) - q(n/d, k/d))); \\ Andrew Howroyd, Sep 27 2019

Formula

T(n,k) = A180279(n,k) - A179519(n,k). - Andrew Howroyd, Sep 27 2019

Extensions

a(37) corrected and terms a(56) and beyond from Andrew Howroyd, Sep 27 2019