login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A276106 Number of compositions of n into parts 1, 7, and 8. 1
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, 432, 584, 784, 1041, 1369, 1793, 2353, 3105, 4121, 5489, 7314, 9724, 12886, 17032, 22490, 29716, 39326, 52129, 69167, 91777, 121695, 161217, 213423, 282465, 373920, 495216, 656160, 869632, 1152544, 1527184 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,8

COMMENTS

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

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

LINKS

Table of n, a(n) for n=0..54.

Index entries for linear recurrences with constant coefficients, signature (1,0,0,0,0,0,1,1).

FORMULA

a(n) = a(n-1) + a(n-7) + a(n-8) for n > 7.

G.f.: 1/(1-x-x^7-x^8).

EXAMPLE

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

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

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

situation 1: none

situation 2: painted only 1st section

situation 3: painted only 2nd section

situation 4: painted only 3rd section

situation 5: painted only 4th section

situation 6: painted 1st and 2nd sections

situation 7: painted 2nd and 3rd sections

situation 8: painted 3rd and 4th sections

MATHEMATICA

CoefficientList[Series[1/(1 - x - x^7 - x^8), {x, 0, 54}], x] (* Michael De Vlieger, Aug 28 2016 *)

PROG

(PARI) Vec(1/(1-x-x^7-x^8) + O(x^50)) \\ Felix Fröhlich, Aug 27 2016

CROSSREFS

Sequence in context: A062417 A240114 A076828 * A321501 A238264 A098807

Adjacent sequences:  A276103 A276104 A276105 * A276107 A276108 A276109

KEYWORD

nonn

AUTHOR

Ozan Kaymak, Ibrahim Suat Evren, Aug 18 2016

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 22 17:14 EST 2020. Contains 332140 sequences. (Running on oeis4.)