Detailed mathematical approach

Problem Summary

We must tile a row of length 50 using grey unit squares together with red tiles of length 2, green tiles of length 3, and blue tiles of length 4. Every arrangement has to cover the row exactly, with no overlap and no overhang, so the question is how many distinct complete tilings exist.

The all-grey arrangement is included, because grey squares are valid pieces. What makes this problem different from the earlier single-colour variants is that red, green, and blue tiles may be mixed freely in the same row. That turns the task into a counting problem on compositions of 50 with allowed part sizes \(1,2,3,4\), where the size-1 part represents one grey square.

Mathematical Approach

Let \(T(n)\) denote the number of legal tilings of a row of length \(n\). The required answer is therefore \(T(50)\). The useful state is just the remaining length, because once that length is known, the earlier part of the row no longer affects the number of ways to finish it.

Choose the right state space

A tiling of length \(n\) can be read as a sequence of piece lengths whose sum is \(n\). Since the available lengths are exactly \(1,2,3,4\), each valid arrangement corresponds to a composition of \(n\) with parts in \(\{1,2,3,4\}\). No extra colour factor is needed: there is exactly one tile type of each non-grey length.

The natural base case is \(T(0)=1\): there is exactly one way to tile a row of length 0, namely to place nothing. This is not an extra visible tiling of the 50-cell row; it is the neutral base case that makes the recurrence work cleanly. For convenience we also set \(T(n)=0\) for all \(n<0\).

Split the tilings by their final piece

Take any complete tiling of length \(n\). Its last piece must be exactly one of four possibilities: a grey square of length 1, a red tile of length 2, a green tile of length 3, or a blue tile of length 4. If we remove that last piece, what remains is a unique tiling of length \(n-1\), \(n-2\), \(n-3\), or \(n-4\), respectively.

These four cases are disjoint and exhaustive, so no arrangement is missed and none is counted twice. Therefore, for \(n \ge 1\),

$T(n)=T(n-1)+T(n-2)+T(n-3)+T(n-4).$

This four-term linear recurrence is the whole mathematical core of the problem.

Base values and early terms

Starting from \(T(0)=1\), the first values follow immediately: \(T(1)=1\), \(T(2)=2\), \(T(3)=4\), \(T(4)=8\). The sequence therefore begins

$1,\,1,\,2,\,4,\,8,\,15,\,29,\dots$

Each term is the sum of the previous four terms, with any negative-index term treated as 0. The all-grey tiling is already included automatically through repeated use of the \(T(n-1)\) branch.

Worked example: a row of length 5

The small example used as a checkpoint in the implementations is length 5. Applying the recurrence gives

$T(5)=T(4)+T(3)+T(2)+T(1)=8+4+2+1=15.$

This has a direct combinatorial meaning. There are 8 tilings ending in a grey square, 4 ending in a red tile, 2 ending in a green tile, and 1 ending in a blue tile. Adding those disjoint families yields exactly 15 tilings.

A compact generating-function form

If we define \(F(x)=\sum_{n \ge 0} T(n)x^n\), the same recurrence can be written as

$F(x)=1+xF(x)+x^2F(x)+x^3F(x)+x^4F(x),$

which rearranges to

$F(x)=\frac{1}{1-x-x^2-x^3-x^4}.$

The implementations do not need this formula, but it packages the same counting rule into a single algebraic identity and confirms that the sequence is determined entirely by the four allowed tile lengths.

How the Code Works

The C++, Python, and Java implementations all use the same bottom-up dynamic program. They allocate a one-dimensional table indexed by row length, store \(1\) at length \(0\), and then fill lengths \(1\) through \(50\) in increasing order. For the current length \(n\), the implementation starts from the count for \(n-1\) and then adds the counts for \(n-2\), \(n-3\), and \(n-4\) whenever those indices are valid.

The key invariant is that after the entry for length \(n\) has been written, every table entry up to \(n\) already equals the exact number of tilings for that length. Because each new state depends only on smaller states, one left-to-right pass is enough. The final answer is the entry at length \(50\). The C++ implementation also includes a small sanity check at length \(5\), confirming the known value \(15\).

Complexity Analysis

For a general row length \(N\), the algorithm performs one constant-size update for each \(n=1,2,\dots,N\). That gives \(O(N)\) time. With \(N=50\), the running time is tiny.

As written, the implementations store all values from \(T(0)\) through \(T(N)\), so the space usage is \(O(N)\). Mathematically only the previous four values are needed, so the recurrence could be compressed to \(O(1)\) extra space, but the full table keeps the code straightforward. The value for \(N=50\) also fits comfortably inside a signed 64-bit integer, which is why the compiled implementations can use ordinary integer arithmetic.

Footnotes and References

1. Problem page: Project Euler 117
2. Dynamic programming: Wikipedia - Dynamic programming
3. Recurrence relation: Wikipedia - Recurrence relation
4. Generating function: Wikipedia - Generating function
5. Integer compositions: Wikipedia - Composition (combinatorics)