cp's OEIS Frontend

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

%I A209399 #21 May 22 2025 10:21:35
%S A209399 0,0,0,0,4,14,37,83,181,387,824,1728,3584,7360,15032,30571,61987,
%T A209399 125339,252883,509294,1024300,2057848,4130724,8285758,16610841,
%U A209399 33285207,66673209,133512759,267294832,535025408,1070755840,2142652160,4287149680,8577285255
%N A209399 Number of subsets of {1,...,n} containing two elements whose difference is 3.
%C A209399 Also, the number of bitstrings of length n containing one of the following: 1001, 1101, 1011, 1111.
%H A209399 David Nacin, <a href="/A209399/b209399.txt">Table of n, a(n) for n = 0..500</a>
%H A209399 <a href="/index/Rec#order_09">Index entries for linear recurrences with constant coefficients</a>, signature (3,-1,-3,3,-1,-1,-3,1,2).
%F A209399 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).
%F A209399 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)).
%F A209399 a(n) = 2^n - A006500(n).
%F A209399 a(n) = 2^n - Product(i=0 to 2) F(floor((n+i)/3)+2) where F(n) is the n-th Fibonacci number.
%e A209399 When n=4 any such subset must contain 1 and 4.  There are four such subsets so a(4) = 4.
%t A209399 LinearRecurrence[{3, -1, -3, 3, -1, -1, -3, 1, 2}, {0, 0, 0, 0, 4, 14, 37, 83, 181}, 50]
%t A209399 Table[2^n - Product[Fibonacci[Floor[(n + i)/3] + 2], {i, 0, 2}], {n, 0, 50}]
%o A209399 (Python)
%o A209399 #From recurrence
%o A209399 def a(n, adict={0:0, 1:0, 2:0, 3:0, 4:4, 5:14, 6:37, 7:83, 8:181}):
%o A209399  if n in adict:
%o A209399   return adict[n]
%o A209399  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)
%o A209399  return adict[n]
%o A209399 (Python)
%o A209399 #Returns the actual list of valid subsets
%o A209399 def contains1001(n):
%o A209399  patterns=list()
%o A209399  for start in range (1,n-2):
%o A209399   s=set()
%o A209399   for i in range(4):
%o A209399    if (1,0,0,1)[i]:
%o A209399     s.add(start+i)
%o A209399   patterns.append(s)
%o A209399  s=list()
%o A209399  for i in range(2,n+1):
%o A209399   for temptuple in comb(range(1,n+1),i):
%o A209399    tempset=set(temptuple)
%o A209399    for sub in patterns:
%o A209399     if sub <= tempset:
%o A209399      s.append(tempset)
%o A209399      break
%o A209399  return s
%o A209399 #Counts all such sets
%o A209399 def countcontains1001(n):
%o A209399  return len(contains1001(n))
%o A209399 (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
%o A209399 (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
%Y A209399 Cf. A209398, A209400, A006500.
%K A209399 nonn,easy
%O A209399 0,5
%A A209399 _David Nacin_, Mar 07 2012