cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-3 of 3 results.

A164387 Number of binary strings of length n with no substrings equal to 0000 or 0010.

Original entry on oeis.org

1, 2, 4, 8, 14, 25, 45, 82, 149, 270, 489, 886, 1606, 2911, 5276, 9562, 17330, 31409, 56926, 103173, 186991, 338903, 614229, 1113231, 2017624, 3656749, 6627505, 12011714, 21770074, 39456161, 71510489, 129605869, 234898146, 425730250, 771595046, 1398441654
Offset: 0

Views

Author

R. H. Hardin, Aug 14 2009

Keywords

Comments

Also, number of subsets of {1,...,n} not containing {a,a+1,a+3} for any a. Also, the number of subsets of {1,...,n} not containing {a,a+2,a+3} for any a. - David Nacin, Mar 07 2012

Examples

			When n=5, the bitstrings containing 0000 or 0010 are 00000, 10000, 00001, 10010, 00010, 00100, 00101.  Thus a(5) = 2^5 - 7. - _David Nacin_, Mar 07 2012

Links

Crossrefs

Cf. A209400.

Programs

  • Maple
    f:=proc(n) option remember;
if n <= 3 then 2^n elif n=4 then 14
else f(n-1)+f(n-2)+f(n-4)+f(n-5); fi; end;
  • Mathematica
    LinearRecurrence[{1, 1, 0, 1, 1}, {1, 2, 4, 8, 14}, 40] (* David Nacin, Mar 07 2012 *)
  • PARI
    v=[1,2,4,8,14];while(#v<=1000,v=concat(v,v[#v]+v[#v-1]+v[#v-3]+v[#v-4]));v \\ Charles R Greathouse IV, Aug 01 2011
  • Python
    def a(n, adict={0:1, 1:2, 2:4, 3:8, 4:14}):
    if n in adict:
        return adict[n]
    adict[n]=a(n-1)+a(n-2)+a(n-4)+a(n-5)
    return adict[n] # David Nacin, Mar 07 2012

Formula

From N. J. A. Sloane, Mar 31 2011: (Start)
For n >= 5, a(n) = a(n-1) + a(n-2) + a(n-4) + a(n-5).
G.f.: (1 + x + x^2 + 2*x^3 + x^4)/(1 - x - x^2 - x^4 - x^5). (End)

Extensions

Edited by N. J. A. Sloane, Mar 31 2011

A209398 Number of subsets of {1,...,n} containing two elements whose difference is 2.

Original entry on oeis.org

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
Offset: 0

Views

Author

David Nacin, Mar 07 2012

Keywords

Comments

Also, the number of bitstrings of length n containing either 101 or 111.

Examples

			For n=3 the subsets containing 1 and 3 are {1,3} and {1,2,3} so a(3)=2.

Links

Crossrefs

Cf. A006498, A209399, A209400.

Programs

  • Magma
    [2^n - Fibonacci(Floor(n/2) + 2)*Fibonacci(Floor((n + 1)/2) + 2): n in [0..30]]; // G. C. Greubel, Jan 03 2018
  • 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]
CoefficientList[ Series[x^3 (x +2)/(2x^5 +x^4 -x^3 +2x^2 -3x +1), {x, 0, 33}], x] (* Robert G. Wilson v, Jan 03 2018 *)
a[n_] := Floor[ N[(2^-n ((50 - 14 Sqrt[5]) (1 - Sqrt[5])^n + ((-1 + 2I) (-2I)^n - (1 + 2I) (2I)^n + 5 4^n) (15 + 11 Sqrt[5]) - 2 (1 + Sqrt[5])^n (85 + 37 Sqrt[5])))/(150 + 110 Sqrt[5])]]; Array[a, 33] (* Robert G. Wilson v, Jan 03 2018 *)
  • PARI
    x='x+O('x^30); concat([0,0,0], Vec(x^3*(2+x)/((1-2*x)*(1+x^2)*(1-x-x^2)))) \\ G. C. Greubel, Jan 03 2018
  • 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))

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)), where F(n) are the Fibonacci numbers.
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)).
E.g.f.: (2*cos(x) + 5*cosh(2*x) + sin(x) + 5*sinh(2*x) - exp(x/2)*(7*cosh(sqrt(5)*x/2) + 3*sqrt(5)*sinh(sqrt(5)*x/2)))/5. - Stefano Spezia, Mar 12 2024

A209399 Number of subsets of {1,...,n} containing two elements whose difference is 3.

Original entry on oeis.org

0, 0, 0, 0, 4, 14, 37, 83, 181, 387, 824, 1728, 3584, 7360, 15032, 30571, 61987, 125339, 252883, 509294, 1024300, 2057848, 4130724, 8285758, 16610841, 33285207, 66673209, 133512759, 267294832, 535025408, 1070755840, 2142652160, 4287149680, 8577285255
Offset: 0

Views

Author

David Nacin, Mar 07 2012

Keywords

Comments

Also, the number of bitstrings of length n containing one of the following: 1001, 1101, 1011, 1111.

Examples

			When n=4 any such subset must contain 1 and 4.  There are four such subsets so a(4) = 4.

Links

Crossrefs

Cf. A209398, A209400, A006500.

Programs

  • Magma
    [2^n - Fibonacci(Floor(n/3) + 2)*Fibonacci(Floor((n + 1)/3) + 2)*Fibonacci(Floor((n + 2)/3) + 2): n in [0..30]]; // G. C. Greubel, Jan 03 2018
  • Mathematica
    LinearRecurrence[{3, -1, -3, 3, -1, -1, -3, 1, 2}, {0, 0, 0, 0, 4, 14, 37, 83, 181}, 50]
Table[2^n - Product[Fibonacci[Floor[(n + i)/3] + 2], {i, 0, 2}], {n, 0, 50}]
  • PARI
    x='x+O('x^30); concat([0,0,0,0], Vec(x^4*(4+2*x-x^2-2*x^3-x^4)/( (1-2*x)*(1-x-x^2)*(1+x^3-x^6)))) \\ G. C. Greubel, Jan 03 2018
  • Python
    #From recurrence
def a(n, adict={0:0, 1:0, 2:0, 3:0, 4:4, 5:14, 6:37, 7:83, 8:181}):
 if n in adict:
  return adict[n]
 adict[n]=3*a(n-1)-a(n-2)-3*a(n-3)+3*a(n-4)-a(n-5)-a(n-6)-3*a(n-7)+a(n-8)+2*a(n-9)
 return adict[n]
  • Python
    #Returns the actual list of valid subsets
def contains1001(n):
 patterns=list()
 for start in range (1,n-2):
  s=set()
  for i in range(4):
   if (1,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 countcontains1001(n):
 return len(contains1001(n))

Formula

a(n) = 3*a(n-1) - a(n-2) - 3*a(n-3) + 3*a(n-4) - a(n-5) - a(n-6) - 3*a(n-7) + a(n-8) + 2*a(n-9).
G.f.: (4*x^4 + 2*x^5 - x^6 - 2*x^7 - x^8)/(1 - 3*x + 1*x^2 + 3*x^3 - 3*x^4 + x^5 + x^6 + 3*x^7 - x^8 - 2*x^9) = x^4*(4 + 2*x - x^2 - 2*x^3 - x^4)/((1 - 2*x)*(1 - x - x^2)*(1 + x^3 - x^6)).
a(n) = 2^n - A006500(n).
a(n) = 2^n - Product(i=0 to 2) F(floor((n+i)/3)+2) where F(n) is the n-th Fibonacci number.
Showing 1-3 of 3 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.