|
| |
|
|
A208743
|
|
Number of subsets of the set {1,2,...,n} which do not contain two elements whose difference is 6.
|
|
3
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
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
|
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
