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