login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A279312 Number of subsets of {1, 2, 3, ..., n} that include no consecutive even integers. 0
1, 2, 4, 8, 12, 24, 40, 80, 128, 256, 416, 832, 1344, 2688, 4352, 8704, 14080, 28160, 45568, 91136, 147456, 294912, 477184, 954368, 1544192, 3088384, 4997120, 9994240, 16171008, 32342016, 52330496 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

Let b(n) be the number of subsets of [n] that include no consecutive odd integers then b(n) satisfies the recurrence b(0)=1, b(1)=2, b(2)=4, b(3)=6; for n > 3, b(n) = 2b(n-2) + 4b(n-4). For that sequence see A279245.

Let a(n) be the number of subsets of [n] that include no consecutive even integers. If n is an even integer then, a(n) = b(n). Since in the set S = {1, 2, 3, ..., n} where n is even, the number of odd integers is equal to the number of even integers. For example, let S ={1, 2, 3, 4} In this set there are 2 odd and 2 even integers. So the number of subsets of S contain no consecutive odd integers is equal to  the number of subsets of S contain no consecutive even integers. In the other case if n is an odd integer then, a(n) = 2b(n-1). Since in the set S = {1, 2, 3, ..., n} where n is odd; Let K = {1, 2, 3, ..., n-1}, n-1 is an even integer so there are b(n-1) subsets containing no consecutive even integers in the set K. And prepending the last element 'n' to each of those gives us another b(n-1) subsets, for a total of 2b(n-1) subsets. Hence if n is even then, a(n) = b(n). If n is odd then, a(n) = 2b(n-1). For k = 0, 1, 2, 3, ... ; a(2k+1) = 2a(2k).

LINKS

Table of n, a(n) for n=0..30.

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

FORMULA

a(n) = A279245(n) if n is even; a(n) = 2*A279245(n-1) if n is odd.

G.f.: (2*x^3+4*x^2+2*x+2)/(4*x^4+2*x^2-1).

a(n) = 2a(n-2) + 4a(n-4). - Charles R Greathouse IV, Dec 13 2016

EXAMPLE

For n=4, a(n)=12. The number of subsets of {1, 2, 3, 4} that include no consecutive even integers are: {}, {1}, {2}, {3}, {4}, {1,2}, {1,3}, {1,4}, {2,3}, {3,4}, {1,2,3}, {1,3,4}.

PROG

(PARI) a(n)=([0, 1, 0, 0; 0, 0, 1, 0; 0, 0, 0, 1; 4, 0, 2, 0]^n*[1; 2; 4; 8])[1, 1] \\ Charles R Greathouse IV, Dec 13 2016

CROSSREFS

Cf. A279245

Sequence in context: A171647 A089821 A294067 * A326076 A181808 A097942

Adjacent sequences:  A279309 A279310 A279311 * A279313 A279314 A279315

KEYWORD

nonn,easy

AUTHOR

Baris Arslan, Dec 09 2016

EXTENSIONS

More terms from Charles R Greathouse IV, Dec 13 2016

Edited by Michel Marcus, Jul 04 2017

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 26 02:56 EDT 2020. Contains 334613 sequences. (Running on oeis4.)