login
This site is supported by donations to The OEIS Foundation.

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A209398 Number of subsets of {1,...,n} containing two elements whose difference is 2. 4
0, 0, 0, 2, 7, 17, 39, 88, 192, 408, 855, 1775, 3655, 7478, 15228, 30898, 62511, 126177, 254223, 511472, 1027840, 2063600, 4140015, 8300767, 16635087, 33324462, 66736764, 133615658, 267461287, 535294673, 1071191415, 2143357000, 4288290240, 8579130888 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

Also, the number of bitstrings of length n containing either 101 or 111.

LINKS

David Nacin, Table of n, a(n) for n = 0..500

Index to sequences with linear recurrences with constant coefficients, signature (3,- 2,1,-1,-2).

FORMULA

a(n) = 3*a(n-1) - 2*a(n-2) + a(n-3) - a(n-4) - 2*a(n-5), a(0)=0, a(1)=0, a(2)=0, a(3)=2, a(4)=7.

a(n) = 2^n - F(2+floor(n/2))*F(floor(2+(n+1)/2)).

a(n) = 2^n - A006498(n+2).

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

x^3(2 + x) / ((1 - 2*x) (1 + x^2) (1 - x - x^2)).

EXAMPLE

For n=3 the subsets containing 1 and 3 are {1,3} and {1,2,3} so a(3)=2.

MATHEMATICA

Table[2^n -

  Fibonacci[Floor[n/2] + 2]*Fibonacci[Floor[(n + 1)/2] + 2], {n, 0,

  30}]

LinearRecurrence[{3, -2, 1, -1, -2}, {0, 0, 0, 2, 7}, 40]

PROG

(Python)

#Through Recurrence

def a(n, adict={0:0, 1:0, 2:0, 3:2, 4:7}):

.if n in adict:

..return adict[n]

.adict[n]=3*a(n-1)-2*a(n-2)+a(n-3)-a(n-4)-2*a(n-5)

.return adict[n]

(Python)

#Returns the actual list of valid subsets

def contains101(n):

.patterns=list()

.for start in range (1, n-1):

..s=set()

..for i in range(3):

...if (1, 0, 1)[i]:

....s.add(start+i)

..patterns.append(s)

.s=list()

.for i in range(2, n+1):

..for temptuple in comb(range(1, n+1), i):

...tempset=set(temptuple)

...for sub in patterns:

....if sub <= tempset:

.....s.append(tempset)

.....break

.return s

#Counts all such subsets using the preceding function

def countcontains101(n):

.return len(contains101(n))

CROSSREFS

Cf. A006498, A209399, A209400.

Sequence in context: A154117 A173769 A067038 * A175660 A175120 A239357

Adjacent sequences:  A209395 A209396 A209397 * A209399 A209400 A209401

KEYWORD

nonn,easy

AUTHOR

David Nacin, Mar 07 2012

STATUS

approved

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

Content is available under The OEIS End-User License Agreement .

Last modified July 28 00:10 EDT 2014. Contains 244987 sequences.