login
Number of nonempty subsequences {s(k)} of 1..n such that the difference sequence is palindromic.
5

%I #58 Oct 01 2022 19:33:05

%S 1,3,7,13,23,37,59,89,135,197,291,417,607,861,1243,1753,2519,3541,

%T 5075,7121,10191,14285,20427,28617,40903,57285,81859,114625,163775,

%U 229309,327611,458681,655287,917429,1310643,1834929,2621359,3669933,5242795,7339945

%N Number of nonempty subsequences {s(k)} of 1..n such that the difference sequence is palindromic.

%C Equals (n-1)-th row sums of triangle A152202. - _Gary W. Adamson_, Nov 29 2008

%C a(n) is the number of positive integers < 2^n such that the binary representation of the odd part is palindromic; i.e., palindromic without the final 0's. - _Andrew Woods_, May 19 2012

%C a(n) is the number of ideals of the quotient ring Z_{2^n}[u]/<u^2> for indeterminate u. - _Fatih Temiz_, Oct 11 2017

%C Conjecture: let b(n) be the number of subsets S of {1,2,...,n} having more than one element such that (sum of least two elements of S) > max(S). Then b(0) = b(1) = 0 and b(n+2) = a(n+1) for n >= 0. - _Clark Kimberling_ Sep 27 2022

%H Andrew Woods, <a href="/A053599/b053599.txt">Table of n, a(n) for n = 1..1000</a>

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (2,1,-4,2).

%F a(1)=1, a(2)=3 and, for n > 2, a(n) = 2*a(n-2) + 2*n - 1.

%F G.f.: x*(1+x)/((1-x)^2*(1-2*x^2)). - _Colin Barker_, Mar 28 2012

%F a(n) = 5*2^((n+1)/2) - 2*n - 7 for odd n, 7*2^(n/2) - 2*n - 7 for even n. - _Andrew Woods_, May 19 2012

%e For n=4 the 13 sequences are 1,2,3,4,12,13,14,23,24,34,123,234,1234.

%t t={1,1};Do[AppendTo[t,t[[-2]]+t[[-1]]];AppendTo[t,2*t[[-2]]],{n,40}];Nest[Accumulate,t,2] (* _Vladimir Joseph Stephan Orlovsky_, Jan 29 2012 *)

%Y Cf. A027383 (first differences), A016116 (second differences).

%Y Cf. A152202.

%K nonn,easy

%O 1,2

%A _John W. Layman_, Jan 19 2000

%E Corrected by _T. D. Noe_, Nov 08 2006