A209410 Number of subsets of {1,...,n} not containing {a,a+2,a+4} for any a.

1, 2, 4, 8, 16, 28, 49, 91, 169, 312, 576, 1056, 1936, 3564, 6561, 12069, 22201, 40826, 75076, 138096, 254016, 467208, 859329, 1580535, 2907025, 5346880, 9834496, 18088448, 33269824, 61192712, 112550881, 207013417, 380757169, 700321570, 1288092100

Offset

0,2

Comments

Also, the number of bitstrings of length n not 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 (1, 0, 2, 0, 2, 2, 0, -1, -1).

Formula

a(n) = 2^n - A209409(n).

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

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

G.f.: (1 + 1*x + 2*x^2 + 2*x^3 + 4*x^4 + 2*x^5 - 1*x^6 - 2*x^7 - x^8)/((-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) = 2^5 - 4 = 28.

Mathematica

LinearRecurrence[{1, 0, 2, 0, 2, 2, 0, -1, -1}, {1, 2, 4, 8, 16, 28, 49, 91, 169}, 40]

Prog

(Python)
#Returns the actual list of valid subsets
def avoidscode(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)):
..for smallset in comb(range(1, n+1), i):
...s.append(smallset)
.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:
.....status=False
.....break
...if status:
....s.append(tempset)
.return s
#Counts all such sets
def countavoidscode(n, bitstring=(1, 0, 1, 0, 1)):
.return len(avoidscode(n))
#From recurrence
def a(n, adict={0:1, 1:2, 2:4, 3:8, 4:16, 5:28, 6:49, 7:91, 8:169}):
.if n in adict:
..return adict[n]
.adict[n]=a(n-1) + 2*a(n-3) + 2*a(n-5) + 2*a(n-6) - a(n-8) - a(n-9)
.return adict[n]
(PARI) x='x+O('x^30); Vec((1+x+2*x^2+2*x^3+4*x^4+2*x^5-x^6-2*x^7-x^8)/( (-1+x+x^2+x^3)*(-1-x^2-x^4+x^6))) \\ G. C. Greubel, Jan 05 2018
(Magma) I:=[1, 2, 4, 8, 16, 28, 49, 91, 169]; [n le 9 select I[n] else Self(n-1)+2*Self(n-3)+2*Self(n-5)+2*Self(n-6)-Self(n-8)-Self(n-9): n in [1..30]]; // G. C. Greubel, Jan 05 2018

Crossrefs

Cf. A209408, A209409

Sequence in context: A208933 A227036 A172020 * A228733 A318767 A208531

Adjacent sequences: A209407 A209408 A209409 * A209411 A209412 A209413

Keyword

nonn,easy

Author

David Nacin, Mar 08 2012

Status

approved