A180653 'DP(n,k)' triangle read by rows. DP(n,k) is the number of k-double-palindromes of n.

0, 0, 1, 0, 2, 1, 0, 3, 2, 1, 0, 4, 4, 4, 1, 0, 5, 3, 8, 4, 1, 0, 6, 6, 12, 12, 6, 1, 0, 7, 6, 17, 12, 19, 6, 1, 0, 8, 7, 24, 24, 20, 24, 8, 1, 0, 9, 8, 32, 21, 50, 24, 32, 8, 1, 0, 10, 10, 40, 40, 60, 60, 40, 40, 10, 1, 0, 11, 9, 49, 40, 100, 60, 98, 35, 51, 10, 1

Offset: 1

Author

John P. McSorley, Sep 14 2010

Keywords

• nonn
• tabl

Comments

A k-composition of n is an ordered collection of k positive integers (parts) which sum to n. 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.

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

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

Examples

			The triangle begins
  0
  0 1
  0 2 1
  0 3 2  1
  0 4 4  4  1
  0 5 3  8  4  1
  0 6 6 12 12  6  1
  0 7 6 17 12 19  6  1
  0 8 7 24 24 20 24  8 1
  0 9 8 32 21 50 24 32 8 1
  ...
For example, row 8 is: 0 7 6 17 12 19 6 1.
We have DP(8,3)=6 because there are 6 3-double-palindromes of 8: 116, 611, 224, 422, 233, and 332.
We have DP(8,4)=17 because there are 17 4-double-palindromes of 8: 1115, 5111, 1511, 1151, 1214, 4121, 1412, 2141, 1133, 3311, 1313, 3131, 1232, 2123, 3212, 2321, and 2222.
		

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

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

Cf. A179519, A180279, A180918, A181111, A181169.

Programs

PARI

\\ p(n,k) is k*A119963(n,k); q(n,k) is A051159(n-1, k-1).
p(n, k) = {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))}
invphi(n) = {sumdiv(n, d, d*moebius(d))}
T(n, k) = sumdiv(gcd(n, k), d, invphi(d) * p(n/d, k/d) - moebius(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

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