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!)
A259278 Number of compositions of n into parts 1, 6, and 7. 1
1, 1, 1, 1, 1, 1, 2, 4, 6, 8, 10, 12, 15, 21, 31, 45, 63, 85, 112, 148, 200, 276, 384, 532, 729, 989, 1337, 1813, 2473, 3389, 4650, 6368, 8694, 11844, 16130, 21992, 30031, 41049, 56111, 76649, 104623, 142745, 194768, 265848, 363008, 495768, 677040, 924408, 1261921 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,7

COMMENTS

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

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

LINKS

Robert Israel, Table of n, a(n) for n = 0..6659

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

FORMULA

a(n) = a(n-1) + a(n-6) + a(n-7).

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

EXAMPLE

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

For n=3 so {1,2,3}, the answer is a(3+5) = a(8), so the answer is 6.

It can be checked easily. 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+5)=a(9)=8; here are the 8 situations:

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

MAPLE

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

map(F, [$0..100]); # Robert Israel, Jul 23 2015

MATHEMATICA

LinearRecurrence[{1, 0, 0, 0, 0, 1, 1}, {1, 1, 1, 1, 1, 1, 2}, 50] (* Vincenzo Librandi, Jun 27 2015 *)

PROG

(PARI) Vec(1/(1-x-x^6-x^7) + O(x^50)) \\ Michel Marcus, Jun 26 2015

(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

CROSSREFS

Cf. A079972, A121832, A000930, A078012.

Sequence in context: A130261 A186384 A011860 * A049445 A002174 A002202

Adjacent sequences:  A259275 A259276 A259277 * A259279 A259280 A259281

KEYWORD

nonn,easy

AUTHOR

Ayse Pelin Ozcan and Feyza Duman, Jun 23 2015

EXTENSIONS

More terms from Michel Marcus, Jun 26 2015

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 July 10 00:05 EDT 2020. Contains 335570 sequences. (Running on oeis4.)