|
| |
|
|
A209398
|
|
Number of subsets of {1,...,n} containing two elements whose difference is 2.
|
|
4
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,4
|
|
|
COMMENTS
|
Also, the number of bitstrings of length n containing either 101 or 111.
|
|
|
LINKS
|
David Nacin, Table of n, a(n) for n = 0..500
Index to sequences with linear recurrences with constant coefficients, signature (3,- 2,1,-1,-2).
|
|
|
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)).
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)).
|
|
|
EXAMPLE
|
For n=3 the subsets containing 1 and 3 are {1,3} and {1,2,3} so a(3)=2.
|
|
|
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]
|
|
|
PROG
|
(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))
|
|
|
CROSSREFS
|
Cf. A006498, A209399, A209400.
Sequence in context: A154117 A173769 A067038 * A175660 A175120 A106910
Adjacent sequences: A209395 A209396 A209397 * A209399 A209400 A209401
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
David Nacin, Mar 07 2012
|
|
|
STATUS
|
approved
|
| |
|
|
