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-2 of 2 results.

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

A209400 Number of subsets of {1,...,n} containing a subset of the form {k,k+1,k+3} for some k.

Original entry on oeis.org

0, 0, 0, 0, 2, 7, 19, 46, 107, 242, 535, 1162, 2490, 5281, 11108, 23206, 48206, 99663, 205218, 421115, 861585, 1758249, 3580075, 7275377, 14759592, 29897683, 60481359, 122206014, 246665382, 497414751, 1002231335, 2017877779, 4060069150, 8164204342
Offset: 0

Views

Author

David Nacin, Mar 07 2012

Keywords

Comments

Also, number of subsets of {1,...,n} containing {a,a+2,a+3} for some a.
Also, number of bitstrings of length n containing 1101 or 1111.

Examples

			When n=4 the only subsets containing an {a,a+1,a+3} happen when a=1 with the two subsets {1,2,3,4} and {1,2,4}.  Thus a(4)=2.

Links

Crossrefs

Cf. A209398, A209399, A164387.

Programs

  • Magma
    I:=[0, 0, 0, 0, 2, 7]; [n le 6 select I[n] else 3*Self(n-1) - Self(n-2)-2*Self(n-3)+Self(n-4)-Self(n-5)-2*Self(n-6): n in [0..30]]; // G. C. Greubel, Jan 03 2018
  • Mathematica
    LinearRecurrence[{3, -1, -2, 1, -1, -2}, {0, 0, 0, 0, 2, 7}, 40]
CoefficientList[Series[x^4*(2+x)/(1-3*x+x^2+2*x^3-x^4+x^5+2*x^6), {x,0, 50}], x] (* G. C. Greubel, Jan 03 2018 *)
  • PARI
    x='x+O('x^30); concat([0,0,0,0], Vec(x^4*(2+x)/(1-3*x+x^2+2*x^3-x^4+x^5+2*x^6))) \\ G. C. Greubel, Jan 03 2018
  • Python
    #From recurrence
def a(n, adict={0:0, 1:0, 2:0, 3:0, 4:2, 5:7}):
 if n in adict:
  return adict[n]
 adict[n]=3*a(n-1)-a(n-2)-2*a(n-3)+a(n-4)-a(n-5)-2*a(n-6)
 return adict[n]
  • Python
    #Returns the actual list of valid subsets
def contains1101(n):
 patterns=list()
 for start in range (1,n-2):
  s=set()
  for i in range(4):
   if (1,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 sets
def countcontains1101(n):
 return len(contains1101(n))

Formula

a(n) = 3*a(n-1) - a(n-2) - 2*a(n-3) + a(n-4) - a(n-5) - 2*a(n-6), a(4)=2, a(5)=7, a(i)=0 for i<4.
G.f.: x^4*(2 + x)/(1 - 3*x + x^2 + 2*x^3 - x^4 + x^5 + 2*x^6) = x^4*(2 + x)/((1 - 2*x)*(1 - x - x^2 - x^4 - x^5)).
a(n) = 2^n - A164387(n).
Showing 1-2 of 2 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.