

A007481


Number of subsequences of [ 1,...,n ] in which each even number has an odd neighbor.
(Formerly M0828)


5



1, 2, 3, 7, 11, 25, 39, 89, 139, 317, 495, 1129, 1763, 4021, 6279, 14321, 22363, 51005, 79647, 181657, 283667, 646981, 1010295, 2304257, 3598219, 8206733, 12815247, 29228713, 45642179, 104099605, 162557031, 370756241, 578955451, 1320467933
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

A055099(n) = a(2*n+1)  a(2*n) = a(2*(n+1))  a(2*n+1).  Reinhard Zumkeller, Oct 25 2015


REFERENCES

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).


LINKS

T. D. Noe, Table of n, a(n) for n = 0..400
R. K. Guy and W. O. J. Moser, Numbers of subsequences without isolated odd members, Fibonacci Quarterly 34:2 (1996), pp. 152155.
Index entries for linear recurrences with constant coefficients, signature (0, 3, 0, 2).


FORMULA

a(n) = 3*a(n2) + 2*a(n4).
G.f.: (x^3+2*x+1)/(2*x^43*x^2+1).  Harvey P. Dale, Feb 29 2012


EXAMPLE

For n=2, there are the following three subsequences of [1,2] with the desired property: empty, [1], [1,2].
For n=3, there are the following seven subsequences of [1,2,3] with the desired property: empty, [1], [3], [1,2], [2,3], [1,3], [1,2,3].


MATHEMATICA

LinearRecurrence[{0, 3, 0, 2}, {1, 2, 3, 7}, 40] (* Harvey P. Dale, Feb 29 2012 *)


PROG

(Haskell)
a007481 n = a007481_list !! n
a007481_list = 1 : 2 : 3 : 7 : zipWith (+)
(map (* 3) $ drop 2 a007481_list) (map (* 2) a007481_list)
 Reinhard Zumkeller, Oct 25 2015
(PARI) a(n)=([0, 1, 0, 0; 0, 0, 1, 0; 0, 0, 0, 1; 2, 0, 3, 0]^n*[1; 2; 3; 7])[1, 1] \\ Charles R Greathouse IV, Mar 02 2016


CROSSREFS

Cf. A007455, A007482, A007484, A055099.
Sequence in context: A128631 A092217 A191659 * A238312 A121268 A101173
Adjacent sequences: A007478 A007479 A007480 * A007482 A007483 A007484


KEYWORD

nonn,easy,nice


AUTHOR

N. J. A. Sloane.


EXTENSIONS

More terms from James A. Sellers, Dec 24 1999


STATUS

approved



