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,1

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

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

Example

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.

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]

Prog

(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

Crossrefs

Cf. A006498, A006500, A208741, A208742.

Sequence in context: A272985 A318588 A008881 * A335853 A247213 A302934

Adjacent sequences: A208740 A208741 A208742 * A208744 A208745 A208746

Keyword

nonn,easy

Author

David Nacin, Mar 01 2012

Status

approved