cp's OEIS Frontend

A208742 Number of subsets of the set {1,2,...,n} which do not contain two elements whose difference is 5.

%I A208742 #41 Sep 17 2024 20:32:42
%S A208742 1,2,4,8,16,32,48,72,108,162,243,405,675,1125,1875,3125,5000,8000,
%T A208742 12800,20480,32768,53248,86528,140608,228488,371293,599781,968877,
%U A208742 1565109,2528253,4084101,6612354,10705716,17333064,28063056,45435424,73498480,118894600
%N A208742 Number of subsets of the set {1,2,...,n} which do not contain two elements whose difference is 5.
%D A208742 M. El-Mikkawy, T. Sogabe, A new family of k-Fibonacci numbers, Appl. Math. Comput. 215 (2010) 4456-4461 doi:10.1016/j.amc.2009.12.069, Table 1 k=5.
%H A208742 Vincenzo Librandi, <a href="/A208742/b208742.txt">Table of n, a(n) for n = 0..1000</a>
%H A208742 M. Tetiva, <a href="http://www.jstor.org/stable/10.4169/math.mag.84.4.296">Subsets that make no difference d</a>, Mathematics Magazine 84 (2011), no. 4, 300-301.
%H A208742 <a href="/index/Rec#order_22">Index entries for linear recurrences with constant coefficients</a>, signature (1, 1, 0, 0, -3, 3, 3, 0, 0, 6, -6, -6, 0, 0, 3, -3, -3, 0, 0, -1, 1, 1).
%F A208742 a(n) = F(floor(n/5) + 3)^(n mod 5)*F(floor(n/5) + 2)^(5 - (n mod 5)) where F(n) is the n-th Fibonacci number.
%F A208742 a(n) = a(n-1) + a(n-2) - 3*a(n-5) + 3*a(n-6) + 3*a(n-7) + 6*a(n-10) - 6*a(n-11) - 6*a(n-12) + 3*a(n-15) - 3*a(n-16) - 3*a(n-17) - a(n-20) + a(n-21) + a(n-22).
%F A208742 G.f.: 1-x*(x^21 +2*x^20 +x^19 +x^18 +x^17 -2*x^16 -6*x^15 -4*x^14 -3*x^13 -3*x^12 -9*x^11 -12*x^10 -3*x^9 -6*x^8 -6*x^7 -2*x^6 +6*x^5 +8*x^4 +4*x^3 +2*x^2 +2*x +2) / ((x^2 +x -1) * (x^10 -4*x^5 -1) * (x^10 +x^5 -1)). - _Colin Barker_, Jun 02 2013
%e A208742 If n=6 then we must count all subsets not containing both 1 and 6.  There are 2^4 subsets containing 1 and 6, giving us 2^6 - 2^4 = 48.  Thus a(6) = 48.
%t A208742 Table[Fibonacci[Floor[n/5] + 3]^Mod[n, 5] * Fibonacci[Floor[n/5] + 2]^(5 - Mod[n, 5]), {n, 1, 40}]
%t A208742 LinearRecurrence[{1, 1, 0, 0, -3, 3, 3, 0, 0, 6, -6, -6, 0, 0, 3, -3, -3, 0, 0, -1, 1, 1}, {2, 4, 8, 16, 32, 48, 72, 108, 162, 243, 405, 675, 1125, 1875, 3125, 5000, 8000, 12800, 20480, 32768, 53248, 86528, 140608, 228488, 371293, 599781, 968877}, 80]
%o A208742 (PARI) a(n)=fibonacci(n\5+3)^(n%5)*fibonacci(n\5+2)^(5-n%5) \\ _Charles R Greathouse IV_, Mar 05 2012
%Y A208742 Cf. A006498, A006500, A208741, A208743.
%K A208742 nonn,easy
%O A208742 0,2
%A A208742 _David Nacin_, Mar 01 2012
%E A208742 a(0)=1 prepended by _Alois P. Heinz_, Sep 17 2024