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.

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

Original entry on oeis.org

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

Views

Author

David Nacin, Mar 08 2012

Keywords

Comments

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

Examples

			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.

Links

Crossrefs

Cf. A209408, A209410.

Programs

  • Mathematica
    LinearRecurrence[{3, -2, 2, -4, 2, -2, -4, -1, 1, 2}, {0, 0, 0, 0, 0, 4, 15, 37, 87, 200}, 40]
  • 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
  • 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]

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)).

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

Original entry on oeis.org

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

Views

Author

David Nacin, Mar 08 2012

Keywords

Comments

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

Examples

			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.

Links

Crossrefs

Cf. A209408, A209409

Programs

  • 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
  • Mathematica
    LinearRecurrence[{1, 0, 2, 0, 2, 2, 0, -1, -1}, {1, 2, 4, 8, 16, 28, 49, 91, 169}, 40]
  • 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
  • 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]

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)).
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.