A209398 Number of subsets of {1,...,n} containing two elements whose difference is 2.

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

Offset: 0

Author

David Nacin, Mar 07 2012

Keywords

• nonn
• easy

Comments

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

Examples

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

Links

• David Nacin, Table of n, a(n) for n = 0..500
• Index entries for linear recurrences with constant coefficients, signature (3,-2,1,-1,-2).

Crossrefs

Cf. A006498, A209399, A209400.

Programs

Magma

[2^n - Fibonacci(Floor(n/2) + 2)*Fibonacci(Floor((n + 1)/2) + 2): n in [0..30]]; // G. C. Greubel, Jan 03 2018

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]
CoefficientList[ Series[x^3 (x +2)/(2x^5 +x^4 -x^3 +2x^2 -3x +1), {x, 0, 33}], x] (* Robert G. Wilson v, Jan 03 2018 *)
a[n_] := Floor[ N[(2^-n ((50 - 14 Sqrt[5]) (1 - Sqrt[5])^n + ((-1 + 2I) (-2I)^n - (1 + 2I) (2I)^n + 5 4^n) (15 + 11 Sqrt[5]) - 2 (1 + Sqrt[5])^n (85 + 37 Sqrt[5])))/(150 + 110 Sqrt[5])]]; Array[a, 33] (* Robert G. Wilson v, Jan 03 2018 *)

PARI

x='x+O('x^30); concat([0,0,0], Vec(x^3*(2+x)/((1-2*x)*(1+x^2)*(1-x-x^2)))) \\ G. C. Greubel, Jan 03 2018

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

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)), where F(n) are the Fibonacci numbers.

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

E.g.f.: (2*cos(x) + 5*cosh(2*x) + sin(x) + 5*sinh(2*x) - exp(x/2)*(7*cosh(sqrt(5)*x/2) + 3*sqrt(5)*sinh(sqrt(5)*x/2)))/5. - Stefano Spezia, Mar 12 2024