|
%I #16 Nov 07 2016 08:54:17
%S 1,1,1,1,1,1,1,2,4,6,8,10,12,14,17,23,33,47,65,87,113,144,184,240,320,
%T 432,584,784,1041,1369,1793,2353,3105,4121,5489,7314,9724,12886,17032,
%U 22490,29716,39326,52129,69167,91777,121695,161217,213423,282465,373920,495216,656160,869632,1152544,1527184
%N Number of compositions of n into parts 1, 7, and 8.
%C Suppose A is a subset of {1..n} having the following property: if A includes an integer k, then A includes none of the integers k+2, k+3, k+4, k+5 or k+6. The number of subsets having this property is a(n+6).
%C The terms of this sequence also give us the answer to the following coloring problem: suppose that, given an n-section board, if we paint the k-th section, we can't paint the (k+2)-th, (k+3)-th, (k+4)-th, (k+5)-th or (k+6)-th section. In how many different ways can we paint this n-section board (where painting none of the sections is considered one of the ways)? Similarly the answer is a(n+6).
%H <a href="/index/Rec#order_08">Index entries for linear recurrences with constant coefficients</a>, signature (1,0,0,0,0,0,1,1).
%F a(n) = a(n-1) + a(n-7) + a(n-8) for n > 7.
%F G.f.: 1/(1-x-x^7-x^8).
%e G.f. = 1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + 2*x^7 + 4*x^8 + 6*x^9 + 8*x^10 + ...
%e For n=3 so {1,2,3}, the answer is a(3+6) = a(9) = 6. Here are the subsets: {},{1},{2},{3},{1,2},{2,3}.
%e For n=4, the number of ways of painting a 4-section board is a(4+6)=a(10)=8; here are the 8 situations: {},{1},{2},{3},{4},{1,2},{2,3},{3,4}.
%e situation 1: none
%e situation 2: painted only 1st section
%e situation 3: painted only 2nd section
%e situation 4: painted only 3rd section
%e situation 5: painted only 4th section
%e situation 6: painted 1st and 2nd sections
%e situation 7: painted 2nd and 3rd sections
%e situation 8: painted 3rd and 4th sections
%t CoefficientList[Series[1/(1 - x - x^7 - x^8), {x, 0, 54}], x] (* _Michael De Vlieger_, Aug 28 2016 *)
%o (PARI) Vec(1/(1-x-x^7-x^8) + O(x^50)) \\ _Felix Fröhlich_, Aug 27 2016
%K nonn
%O 0,8
%A _Ozan Kaymak_, _Ibrahim Suat Evren_, Aug 18 2016
|
