cp's OEIS Frontend

A259278 Number of compositions of n into parts 1, 6, and 7.

%I A259278 #74 Sep 08 2022 08:46:13
%S A259278 1,1,1,1,1,1,2,4,6,8,10,12,15,21,31,45,63,85,112,148,200,276,384,532,
%T A259278 729,989,1337,1813,2473,3389,4650,6368,8694,11844,16130,21992,30031,
%U A259278 41049,56111,76649,104623,142745,194768,265848,363008,495768,677040,924408,1261921
%N A259278 Number of compositions of n into parts 1, 6, and 7.
%C A259278 Suppose A is a subset of {1,2,3,...,n} having the following property: if A includes an integer k, then A includes none of the integers k+2, k+3, k+4, or k+5. The number of subsets having this property is a(n+5).
%C A259278 The terms of this sequence also give us this coloring problem's answer: 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, or (k+5)-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+5).
%H A259278 Robert Israel, <a href="/A259278/b259278.txt">Table of n, a(n) for n = 0..6659</a>
%H A259278 <a href="/index/Rec#order_07">Index entries for linear recurrences with constant coefficients</a>, signature (1,0,0,0,0,1,1).
%F A259278 a(n) = a(n-1) + a(n-6) + a(n-7).
%F A259278 G.f.: 1/(1-x-x^6-x^7).
%e A259278 G.f. = 1 + x + x^2 + x^3 + x^4 + x^5 + 2*x^6 + 4*x^7 + 6*x^8 + 8*x^9 + ...
%e A259278 For n=3 so {1,2,3}, the answer is a(3+5) = a(8), so the answer is 6.
%e A259278 It can be checked easily. Here are the subsets: {},{1},{2},{3},{1,2},{2,3}.
%e A259278 For n=4, the number of ways of painting a 4-section board is a(4+5)=a(9)=8; here are the 8 situations:
%e A259278 situation 1: none
%e A259278 situation 2: painted only 1st section
%e A259278 situation 3: painted only 2nd section
%e A259278 situation 4: painted only 3rd section
%e A259278 situation 5: painted only 4th section
%e A259278 situation 6: painted 1st and 2nd sections
%e A259278 situation 7: painted 2nd and 3rd sections
%e A259278 situation 8: painted 3rd and 4th sections
%p A259278 F:= gfun:-rectoproc({a(n)=a(n-1)+a(n-6)+a(n-7),seq(a(i)=1,i=0..5),a(6)=2},a(n),remember):
%p A259278 map(F, [$0..100]); # _Robert Israel_, Jul 23 2015
%t A259278 LinearRecurrence[{1, 0, 0, 0, 0, 1, 1}, {1, 1, 1, 1, 1, 1, 2}, 50] (* _Vincenzo Librandi_, Jun 27 2015 *)
%o A259278 (PARI) Vec(1/(1-x-x^6-x^7) + O(x^50)) \\ _Michel Marcus_, Jun 26 2015
%o A259278 (Magma) I:=[1,1,1,1,1,1,2]; [n le 7 select I[n] else Self(n-1)+Self(n-6)+Self(n-7): n in [1..60]]; // _Vincenzo Librandi_, Jun 27 2015
%Y A259278 Cf. A079972, A121832, A000930, A078012.
%K A259278 nonn,easy
%O A259278 0,7
%A A259278 _Ayse Pelin Ozcan_ and _Feyza Duman_, Jun 23 2015
%E A259278 More terms from _Michel Marcus_, Jun 26 2015