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,6

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

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

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]

Prog

(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]
(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
(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

Crossrefs

Cf. A031923, A209409, A209410.

Sequence in context: A105636 A102665 A212565 * A316214 A134638 A293289

Adjacent sequences: A209405 A209406 A209407 * A209409 A209410 A209411

Keyword

nonn,easy

Author

David Nacin, Mar 08 2012

Status

approved