A244281 Answer to Red, Green and Blue Tiles Problem.

0, 0, 1, 4, 11, 23, 43, 75, 126, 207, 335, 536, 852, 1350, 2136, 3378, 5344, 8462, 13416, 21300, 33866, 53923, 85979, 137274, 219444, 351203, 562667, 902327, 1448298, 2326472, 3739820, 6015701, 9682260, 15591825, 25120251, 40489004, 65285631, 105304917, 169908475

Offset

0,4

Comments

A row of n black squares is to have a number of its squares replaced by rectangles of lengths 2 (red), 3 (green) or 4 (blue). In how many different ways can the original squares be replaced if rectangles cannot be mixed and at least one rectangle must be used?

Links

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

Kristian Edlund, MathBlog, Project Euler 116: Investigating the number of ways of replacing square tiles with one of three coloured tiles.

Project Euler, Problem 116: Red, green or blue tiles

Formula

Empirical g.f.: -x^2*(3*x^7+2*x^6+x^4-3*x^3-x+1) / ((x-1)^2*(x^2+x-1)*(x^3+x-1)*(x^4+x-1)). - Colin Barker, Nov 14 2014

Prog

(Python)
import math
for n in range(1, 40):
    ans = 0
    for k in range(0, n):
        for i in range(2, 5):
            for j in range(1, ((k/i)+1)):
                c = k - (i * j) + j
                ans = ans + (math.factorial(c) / (math.factorial(j) * math.factorial(k-(i*j))))
    print ans

Crossrefs

Sequence in context: A019298 A237586 A173702 * A014242 A240074 A008181

Adjacent sequences: A244278 A244279 A244280 * A244282 A244283 A244284

Keyword

nonn

Author

Jameson Lee, Jul 02 2014

Status

approved