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

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

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. 152-155.

Index entries for linear recurrences with constant coefficients, signature (0, 3, 0, 2).

Formula

a(n) = 3*a(n-2) + 2*a(n-4).

G.f.: (x^3+2*x+1)/(-2*x^4-3*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