|
%I #22 Dec 20 2018 23:55:57
%S 1,2,2,4,4,8,8,16,16,31,31,62,62,124,124,248,248,496,496,991,991,1980,
%T 1980,3956,3956,7904,7904,15792,15792,31553,31553,63044,63044,125964,
%U 125964,251680,251680,502864,502864,1004737,1004737,2007494,2007494
%N Number of palindromes that use nonzero digits and have a digit sum of n.
%C Consider the array in which the n-th row contains all the palindromes that use nonzero digits and have a digit sum of n:
%C 1
%C 2 11
%C 3 111
%C 4 22 121 1111
%C 5 131 212 11111
%C 6 33 141 222 11211 1221 2112 111111
%C ...
%C a(n) = number of partitions of n into parts < 10 (single-digit nonzero parts) that can be arranged to form a palindrome.
%H G. C. Greubel, <a href="/A082267/b082267.txt">Table of n, a(n) for n = 1..1000</a>
%F 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
%F 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).
%F 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.
%F 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.
%F For 20: Including the terms subtracted in 12<n<20, another term must be subtracted for (10)(10).
%F 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)
%F 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
%F From _Colin Barker_, Feb 14 2013: (Start)
%F a(n) = 2*a(n-2) - a(n-20) for n > 20.
%F G.f.: x*(1+2*x-x^9-x^10-x^19) / (1-2*x^2+x^20). (End)
%p 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
%Y Cf. A082264, A082265, A082266.
%K base,nonn
%O 1,2
%A _Amarnath Murthy_, Apr 12 2003
%E Corrected and extended by Jonathan R. Love, Mar 08 2007
|
