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

0, 0, 0, 0, 0, 4, 15, 37, 87, 200, 448, 992, 2160, 4628, 9823, 20699, 43335, 90246, 187068, 386192, 794560, 1629944, 3334975, 6808073, 13870191, 28207552, 57274368, 116129280, 235165632, 475678200, 961190943, 1940470231, 3914210127, 7889613022, 15891777084

Offset

0,6

Comments

Also, the number of bitstrings of length n containing 10101,11101,10111 or 11111.

Links

G. C. Greubel, Table of n, a(n) for n = 0..1000

Index entries for linear recurrences with constant coefficients, signature (3,-2,2,-4,2,-2,-4,-1,1,2).

Formula

A(n) = 2^n - A209410(n)

a(n) = 2^n - t[floor(n/2)+2]*t[floor((n+1)/2)+2] where t(n) is the n-th tribonacci number.

a(n) = 3*a(n-1) - 2*a(n-2) + 2*a(n-3) - 4*a(n-4) + 2*a(n-5) - 2*a(n-6) - 4*a(n-7) - a(n-8) + a(n-9) + 2*a(n-10).

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

Example

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

Mathematica

LinearRecurrence[{3, -2, 2, -4, 2, -2, -4, -1, 1, 2}, {0, 0, 0, 0, 0, 4, 15, 37, 87, 200}, 40]

Prog

(Python)
#Returns the actual list of valid subsets
def containscode(n, bitstring=(1, 0, 1, 0, 1)):
.patterns=list()
.for start in range (1, n-len(bitstring)+2):
..s=set()
..for i in range(len(bitstring)):
...if bitstring[i]:
....s.add(start+i)
..patterns.append(s)
.s=list()
.for i in range(sum(bitstring), 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 countcontainscode(n, bitstring=(1, 0, 1, 0, 1)):
.return len(containscode(n))
(Python)
#From recurrence
def a(n, adict={0:0, 1:0, 2:0, 3:0, 4:0, 5:4, 6:15, 7:37, 8:87, 9:200}):
.if n in adict:
..return adict[n]
.adict[n]=3*a(n-1) - 2*a(n-2) + 2*a(n-3) - 4*a(n-4) + 2*a(n-5) - 2*a(n-6) - 4*a(n-7) - a(n-8) + a(n-9) + 2*a(n-10)
.return adict[n]
(PARI) x='x+O('x^30); concat([0, 0, 0, 0, 0], Vec(x^5*(4+3*x-2*x^3-x^4)/((1- 2*x)*(1-x-x^2-x^3)*(1+x^2+x^4-x^6)))) \\ G. C. Greubel, Jan 03 2018

Crossrefs

Cf. A209408, A209410.

Sequence in context: A033813 A296295 A296268 * A241302 A112666 A014629

Adjacent sequences: A209406 A209407 A209408 * A209410 A209411 A209412

Keyword

nonn,easy

Author

David Nacin, Mar 08 2012

Status

approved