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

1, 3, 7, 13, 23, 37, 59, 89, 135, 197, 291, 417, 607, 861, 1243, 1753, 2519, 3541, 5075, 7121, 10191, 14285, 20427, 28617, 40903, 57285, 81859, 114625, 163775, 229309, 327611, 458681, 655287, 917429, 1310643, 1834929, 2621359, 3669933, 5242795, 7339945

Offset

1,2

Comments

Equals (n-1)-th row sums of triangle A152202. - Gary W. Adamson, Nov 29 2008

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

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

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

Links

Andrew Woods, Table of n, a(n) for n = 1..1000

Index entries for linear recurrences with constant coefficients, signature (2,1,-4,2).

Formula

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

G.f.: x*(1+x)/((1-x)^2*(1-2*x^2)). - Colin Barker, Mar 28 2012

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

Example

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

Mathematica

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 *)

Crossrefs

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

Cf. A152202.

Sequence in context: A058682 A081995 A291141 * A212146 A136851 A155339

Adjacent sequences: A053596 A053597 A053598 * A053600 A053601 A053602

Keyword

nonn,easy

Author

John W. Layman, Jan 19 2000

Extensions

Corrected by T. D. Noe, Nov 08 2006

Status

approved