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

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

Offset: 0

Author

Ayse Pelin Ozcan and Feyza Duman, Jun 23 2015

Keywords

• nonn
• easy

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

Examples

			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
		

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

Crossrefs

Cf. A079972, A121832, A000930, A078012.

Programs

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

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

PARI

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

Formula

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

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

Extensions

More terms from Michel Marcus, Jun 26 2015