login
Number of compositions of n into parts 1, 8, 9.
1

%I #20 Dec 21 2023 11:49:54

%S 1,1,1,1,1,1,1,1,2,4,6,8,10,12,14,16,19,25,35,49,67,89,115,145,180,

%T 224,284,368,484,640,844,1104,1429,1833,2341,2993,3845,4969,6453,8401,

%U 10934,14196,18370,23704,30542,39356,50778,65632,84967,110097

%N Number of compositions of n into parts 1, 8, 9.

%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, k+6 or k+7. The number of subsets having this property is a(n+7).

%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, (k+6)-th or (k+7)-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+7).

%H <a href="/index/Rec#order_09">Index entries for linear recurrences with constant coefficients</a>, signature (1, 0, 0, 0, 0, 0, 0, 1, 1).

%F a(n) = a(n-1) + a(n-8) + a(n-9) for n > 8.

%F G.f.: 1/(1 - x - x^8 - x^9).

%e G.f. = 1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + 1*x^7 + 2*x^8 + 4*x^9 + 6*x^10 + 8*x^11 + ...

%e For n=3 so {1,2,3}, the answer is a(3+7) = a(10) = 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+7)=a(11)=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

%p seq(coeff(series((1-x-x^8-x^9)^(-1),x,n+1), x, n), n = 0 .. 50); # _Muniru A Asiru_, Dec 08 2018

%t CoefficientList[Series[1/(1 - x - x^8 - x^9), {x, 0, 54}], x]

%Y Cf. A276106.

%K nonn

%O 0,9

%A _Alperen Gözeten_, Dec 07 2018