The OEIS mourns the passing of Jim Simons and is grateful to the Simons Foundation for its support of research in many branches of science, including the OEIS.
login
The OEIS is supported by the many generous donors to the OEIS 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
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
Sequence in context: A130261 A186384 A011860 * A049445 A356448 A340521
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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 26 08:47 EDT 2024. Contains 372815 sequences. (Running on oeis4.)