A209408 Number of subsets of {1,...,n} containing {a,a+4} for some a.

0, 0, 0, 0, 0, 8, 28, 74, 175, 377, 799, 1673, 3471, 7192, 14784, 30208, 61440, 124416, 251328, 506712, 1020015, 2051015, 4119775, 8268215, 16582735, 33239558, 66599068, 133392344, 267099120, 534709192, 1070244924, 2141826898, 4285816671, 8575127217

Offset: 0

Author

David Nacin, Mar 08 2012

Keywords

• nonn
• easy

Comments

For n=5, subsets containing {a,a+4} occur only when a=1. There are 2^3 subsets including {1,5}, thus a(5) = 8.

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000
• Index entries for linear recurrences with constant coefficients, signature (3,-1,-2,-2,6,-2,-4,2,-6,2,4,1,-3, 1,2).

Crossrefs

Cf. A031923, A209409, A209410.

Programs

Magma

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

Mathematica

Table[2^n - Product[Fibonacci[Floor[(n + i)/4] + 2], {i, 0, 3}], {n, 0, 30}]
LinearRecurrence[{3, -1, -2, -2, 6, -2, -4, 2, -6, 2, 4, 1, -3, 1, 2}, {0, 0, 0, 0, 0, 8, 28, 74, 175, 377, 799, 1673, 3471, 7192, 14784}, 30]

PARI

for(n=0,20, print1(2^n - fibonacci(floor(n/4) + 2)*fibonacci( floor((n + 1)/4) + 2)*fibonacci(floor((n + 2)/4) + 2)*fibonacci( floor((n + 3)/4) + 2), ", ")) \\ G. C. Greubel, Jan 03 2018

Python

#Returns the actual list of valid subsets
def contains10001(n):
 patterns=list()
 for start in range (1,n-3):
  s=set()
  for i in range(5):
   if (1,0,0,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 sets
def countcontains10001(n):
 return len(contains10001(n))
#From recurrence
def a(n, adict={0:0, 1:0, 2:0, 3:0, 4:0, 5:8, 6:28, 7:74, 8:175, 9:377, 10:799, 11:1673, 12:3471, 13:7192, 14:14784}):
 if n in adict:
  return adict[n]
 adict[n]=3*a(n-1)-a(n-2)-2*a(n-3)-2*a(n-4)+6*a(n-5)-2*a(n-6)-4*a(n-7)+2*a(n-8)-6*a(n-9)+2*a(n-10)+4*a(n-11)+a(n-12)-3*a(n-13)+a(n-14)+2*a(n-15)
 return adict[n]

Formula

a(n) = 2^n - A208741(n-1).

a(n) = 2^n - Product_{i=0..3} Fibonacci(floor((n + i)/4) + 2).

a(n) = 3*a(n-1) - a(n-2) -2*a(n-3) -2*a(n-4) + 6*a(n-5) - 2*a(n-6) - 4*a(n-7) + 2*a(n-8) - 6*a(n-9) + 2*a(n-10) + 4*a(n-11) + a(n-12) - 3*a(n-13) + a(n-14) + 2*a(n-15).

G.f.: x^5*(8 + 4 x - 2 x^2 - 3 x^3 - 2 x^4 - x^5 - x^6 - x^7 - 2 x^8 - x^9) / ((1 - x) (1 + x) (1 - 2 x) (1 + x^2) (1 - x - x^2) (1 + 3 x^4 + x^8)).