Red, Green or Blue Tiles

A row of five grey square tiles is to have a number of its tiles replaced with coloured oblong tiles chosen from red (length two), green (length three), or blue (length four).
If red tiles are chosen there are exactly seven ways this can be done.

If green tiles are chosen there are three ways.

And if blue tiles are chosen there are two ways.

Assuming that colours cannot be mixed there are $7 + 3 + 2 = 12$ ways of replacing the grey tiles in a row measuring five units in length.
How many different ways can the grey tiles in a row measuring fifty units in length be replaced if colours cannot be mixed and at least one coloured tile must be used?
NOTE: This is related to Problem 117.

This problem is known as a combinatorial problem, where you are trying to find out the number of ways of arranging a set of objects. In this problem, you are trying to figure out the number of ways you can arrange red, green and blue tiles in a row of length fifty.

Each color corresponds to a tile of different length: red (length 2), green (length 3), and blue (length 4). The problem says that we cannot mix colours and we need to use at least one coloured tile.

Let’s denote the number of ways to replace N grey tiles with red, green or blue tiles as f(N) (for N >= 1).

For a row of N tiles, the first tile can either be a coloured tile or a grey one. If the first tile is grey, there are f(N-1) ways to fill the rest of the row.

If the first tile is coloured, then the number of ways depends on the colour of the tile. If the tile is red (length 2), then there are f(N-2) ways to fill the rest. If the tile is green (length 3), there are f(N-3) ways. And if the tile is blue (length 4), there are f(N-4) ways.

All these possibilities are exclusive since we are not allowed to mix colours. Therefore, the total number of ways is equal to the sum:

f(N) = f(N-1) + f(N-2) + f(N-3) + f(N-4)

We need to have some base cases to start off our calculation. From the problem we know that f(1) = 0, f(2) = 1 (one red), f(3) = 1 (one green), f(4) = 2 (one blue or two reds), f(5) = 4 (one blue and one red, three reds or one green and one red).

We then use these base cases and the formula above to calculate f(50).

A direct calculation will show that there are 204,226 ways to replace grey tiles in a row measuring fifty units in length if colours cannot be mixed and at least one coloured tile must be used.

More Answers: