OFFSET
1,2
COMMENTS
Consider the array in which the n-th row contains all the palindromes that use nonzero digits and have a digit sum of n:
1
2 11
3 111
4 22 121 1111
5 131 212 11111
6 33 141 222 11211 1221 2112 111111
...
a(n) = number of partitions of n into parts < 10 (single-digit nonzero parts) that can be arranged to form a palindrome.
LINKS
G. C. Greubel, Table of n, a(n) for n = 1..1000
FORMULA
a(1) = 1, a(2) = 2. For 2<n<10 and 11<n<20, a(n) = 2 * a(n-2). For n=10, 11 or 20, a(n) = 2 * a(n-2) - 1. Otherwise, for 21<=n, a(n) = 2 * a(n-2) - a(n-20). - Jonathan R. Love (japanada11(AT)yahoo.ca), Mar 08 2007
Further remarks from Jonathan R. Love (japanada11(AT)yahoo.ca), Mar 08 2007: (Start) For 2<n<10: a(9) = 16 because it can be written as 9, 4(1)4, 3(3)3, 2(5)2, or 1(7)1. All (n) can be expanded into a(n) different terms; for example, 2(5)2 can be written as 2(11111)2, 2(131)2, 2(212)2, or 2(5)2: 4 terms, since a(5) = 4. So a(9) = 1 + a(1) + a(3) + a(5) + a(7). Since a(7) = 1 + a(1) + a(3) + a(5), a(9) = a(7) + a(7) = 2 * a(7).
For n=10 or 11: Using the rules for 2<n<10, a(10) would be 32, but since one of these terms is the number itself, in this case 10 and only single-digit numbers can be used, one term must be subtracted. a(10) = 2 * a(8) - 1 = 31.
For 12<n<20: The same rules for 2<n<10 apply, because for 12 and up, the term taken away from 10 and 11 is added into the terms: a(12) = 62 = 2 * a(10). a(10) = 2 * a(8) - 1, so a(12) = 4 * a(8) - 2: 1 for (12) and one for 1(10)1.
For 20: Including the terms subtracted in 12<n<20, another term must be subtracted for (10)(10).
For 21<=n: From this point on, all possible terms are 9(a(n-18))9 + 8(a(n-16))8 + 7(a(n-14))7 + 6(a(n-12))6 + 5(a(n-10))5 + 4(a(n-8))4 + 3(a(n-6))3 + 2(a(n-4))2 + 1(a(n-2))1. If a(n-20) were to be included, it would need to be (10)(a(n-20))(10) and 10s can't be included. So everything must subtract a(n-20) from the total of 2 * a(n-2). For example, a(24) = 3956 = 2 * a(22) - a(4). (End)
Let c(n,k) (1<=k<=n) = number of compositions of n into parts of size <= k (cf. A126198). Then a(n) = Sum_{i=0..floor(n/2)} c(n,9). This follows by consideration of the central term, which may be any of n, n-2, n-4, ..., n-2i, ...; the prefix is then a composition of i into parts of size <= 9. - N. J. A. Sloane Mar 09 2007
From Colin Barker, Feb 14 2013: (Start)
a(n) = 2*a(n-2) - a(n-20) for n > 20.
G.f.: x*(1+2*x-x^9-x^10-x^19) / (1-2*x^2+x^20). (End)
MAPLE
seq(coeff(series(x*(1+2*x-x^9-x^10-x^19)/(1-2*x^2+x^20), x, n+1), x, n), n = 1 .. 42); # Muniru A Asiru, Dec 08 2018
CROSSREFS
KEYWORD
base,nonn
AUTHOR
Amarnath Murthy, Apr 12 2003
EXTENSIONS
Corrected and extended by Jonathan R. Love, Mar 08 2007
STATUS
approved