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

2, 4, 8, 16, 32, 64, 96, 144, 216, 324, 486, 729, 1215, 2025, 3375, 5625, 9375, 15625, 25000, 40000, 64000, 102400, 163840, 262144, 425984, 692224, 1124864, 1827904, 2970344, 4826809, 7797153, 12595401, 20346417, 32867289, 53093313, 85766121, 138859434

Offset: 1

Author

David Nacin, Mar 01 2012

Keywords

• nonn
• easy

Examples

			If n=7 then we must count all subsets not containing both 1 and 7.  There are 2^5 subsets containing 1 and 7, giving us 2^7 - 2^5 = 48.  Thus a(7) = 96.
		

References

• 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=6.

Links

• Vincenzo Librandi, Table of n, a(n) for n = 1..1000
• Katharine A. Ahrens, Combinatorial Applications of the k-Fibonacci Numbers: A Cryptographically Motivated Analysis, Ph. D. thesis, North Carolina State University (2020).
• M. Tetiva, Subsets that make no difference d, Mathematics Magazine 84 (2011), no. 4, 300-301.
• Index entries for linear recurrences with constant coefficients, signature (1, 1, 0, 0, 0, -5, 5, 5, 0, 0, 0, 15, -15, -15, 0, 0, 0, 15, -15, -15, 0, 0, 0, -5, 5, 5, 0, 0, 0, -1, 1, 1).

Crossrefs

Cf. A006498, A006500, A208741, A208742.

Programs

Mathematica

Table[Fibonacci[Floor[n/6] + 3]^Mod[n, 6] * Fibonacci[Floor[n/6] + 2]^(6 - Mod[n, 6]), {n, 1, 80}]
LinearRecurrence[{1, 1, 0, 0, 0, -5, 5, 5, 0, 0, 0, 15, -15, -15, 0, 0, 0, 15, -15, -15, 0, 0, 0, -5, 5, 5, 0, 0, 0, -1, 1, 1}, {2, 4, 8, 16, 32, 64, 96, 144, 216, 324, 486, 729, 1215, 2025, 3375, 5625, 9375, 15625, 25000, 40000, 64000, 102400, 163840, 262144, 425984, 692224, 1124864, 1827904, 2970344, 4826809, 7797153, 12595401}, 80]

PARI

Vec(x*(2 + 2*x + 2*x^2 + 4*x^3 + 8*x^4 + 16*x^5 + 10*x^6 - 6*x^7 - 14*x^8 - 16*x^9 - 14*x^10 - x^11 - 30*x^12 - 29*x^13 - 15*x^14 - 15*x^15 - 15*x^16 - 20*x^17 - 30*x^18 - 10*x^19 + 5*x^20 + 5*x^21 + 5*x^22 + 4*x^23 + 10*x^24 + 6*x^25 + x^26 + x^27 + x^28 + x^29 + 2*x^30 + x^31) / ((1 + x^2)*(1 - x - x^2)*(1 - x^2 + x^4)*(1 + x^3 - x^6)*(1 - x^3 - x^6)*(1 + 7*x^6 + x^12)) + O(x^30)) \\ Colin Barker, Feb 23 2017

Formula

a(n) = F(floor(n/6) + 3)^(n mod 6)*F(floor(n/6) + 2)^(6 - (n mod 6)) where F(n) is the n-th Fibonacci number.

a(n) = a(n-1) + a(n-2) - 5*a(n-6) + 5*a(n-7) + 5*a(n-8) + 15*a(n-12) - 15*a(n-13) - 15*a(n-14) + 15*a(n-18) - 15*a(n-19) - 15*a(n-20) - 5*a(n-24) + 5*a(n-25) + 5*a(n-26) - a(n-30) + a(n-31) + a(n-32).

G.f.: x*(2 + 2*x + 2*x^2 + 4*x^3 + 8*x^4 + 16*x^5 + 10*x^6 - 6*x^7 - 14*x^8 - 16*x^9 - 14*x^10 - x^11 - 30*x^12 - 29*x^13 - 15*x^14 - 15*x^15 - 15*x^16 - 20*x^17 - 30*x^18 - 10*x^19 + 5*x^20 + 5*x^21 + 5*x^22 + 4*x^23 + 10*x^24 + 6*x^25 + x^26 + x^27 + x^28 + x^29 + 2*x^30 + x^31) / ((1 + x^2)*(1 - x - x^2)*(1 - x^2 + x^4)*(1 + x^3 - x^6)*(1 - x^3 - x^6)*(1 + 7*x^6 + x^12)). - Colin Barker, Feb 23 2017