A180750 a(n) = DP(n) is the total number of k-double-palindromes of n, where 2 <= k <= n.

0, 1, 3, 6, 13, 21, 43, 68, 116, 185, 311, 464, 757, 1157, 1741, 2720, 4081, 6214, 9199, 14078, 20353, 31405, 45035, 68930, 98224, 150761, 212706, 326362, 458725, 702209, 983011, 1504400, 2096441, 3207137, 4456139, 6808172, 9437149, 14408669, 19921297, 30393800

Offset: 1

Author

John P. McSorley, Sep 19 2010

Keywords

• nonn
• base

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 (see sequence A180653) 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.

The n-th term of this sequence is DP(n), the total number of k-double-palindromes of n, where 2 <= k <= n.

For example, DP(6)=21 because there are 21 k-double-palindromes of 6 for k=2,3,4,5, or 6. They are:

(with k=2) 15=1|5, 51=5|1, 24=2|4, 42=4|2, 33=3|3,

(with k=3) 114=11|4, 411=4|11, 222=2|22,

(with k=4) 1113=111|3, 3111=3|111, 1311=131|1, 1131=1|131, and 1122=11|22, 2211=22|11, 1212=121|2, 2121=2|121,

(with k=5) 11112=1111|2, 21111=2|1111, 12111=121|11, 11121=11|121,

(with k=6) 111111=1|11111.

References

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

Crossrefs

a(n) is the sum of the n-th row of the triangle sequence A180653 (number of k-double-palindromes of n).

The n-th term of sequence A016116 is the total number of k-palindromes (single palindromes) of n.

Formula

a(n) = A180249(n) - A179781(n). - Petros Hadjicostas, Nov 03 2017

G.f.: Sum_{n>=1} phi^{(-1)}(n)*f(x^n) - Sum_{n>=1} mu(n)*g(x^n), where phi^{(-1)}(n) = A023900(n) is the Dirichlet inverse of Euler's totient function, mu(n) = A008683(n) is the Mobius function, f(x) = x*(x+1)*(2*x+1)/(1-2*x^2)^2, and g(x) = x*(1+2*x)/(1-2*x^2). - Petros Hadjicostas, Nov 06 2017

Extensions

a(11)-a(18) from Donovan Johnson, Oct 22 2010

a(11)-a(18) corrected by and a(19)-a(40) from Petros Hadjicostas and Andrew Howroyd, Nov 03 2017