Detailed mathematical approach

Problem Summary

We start with a row of 50 grey unit squares. In one tiling we are allowed to use tiles of exactly one non-grey color: red tiles have length 2, green tiles have length 3, and blue tiles have length 4. Grey squares may remain anywhere, colored tiles may touch each other, colors may not be mixed, and the all-grey row is excluded. If \(B_m(n)\) denotes the number of valid tilings of a row of length \(n\) using grey unit squares and tiles of one fixed length \(m\), with at least one colored tile, then the required quantity is

$B_2(50)+B_3(50)+B_4(50).$

The three colors do not interact, so the problem is really three separate counting problems that are added at the end.

Mathematical Approach

Fix a tile length \(m\in\{2,3,4\}\), and let \(A_m(n)\) be the number of tilings of a row of length \(n\) when grey squares of length 1 and colored tiles of length \(m\) are both allowed, including the all-grey tiling. Then \(B_m(n)=A_m(n)-1\). The mathematics comes from counting \(A_m(n)\) in two equivalent ways: directly by the number of colored tiles, and recursively by looking at the end of the row.

One Color Becomes One Counting Problem

Once \(m\) is fixed, every legal tiling is made from two kinds of pieces only:

$\text{grey square of length }1,\qquad \text{colored tile of length }m.$

There is no mandatory separator between colored tiles, so two red tiles may sit next to each other, two green tiles may sit next to each other, and so on. That is exactly why the recurrence for this problem is simpler than in the separator-based tiling problems: adjacency is allowed, so the only constraint is total length.

Count Tilings with Exactly \(k\) Colored Tiles

Suppose a tiling uses exactly \(k\) colored tiles of length \(m\). Those tiles occupy \(mk\) cells, leaving \(n-mk\) grey squares. Since tiles of the same color are indistinguishable, the question is only how these objects are interleaved along the row.

A convenient compression argument is to shrink each colored tile from length \(m\) to length 1. This removes \(m-1\) cells per colored tile, so the compressed row has length

$n-(m-1)k.$

Inside that compressed row we must choose which \(k\) positions are occupied by the colored objects; the remaining positions are grey squares. Therefore the number of tilings with exactly \(k\) colored tiles is

$\binom{n-(m-1)k}{k}.$

This formula is valid whenever \(0\le k\le \lfloor n/m\rfloor\).

Sum over All Admissible Numbers of Colored Tiles

Adding over every possible value of \(k\) gives the total count including the all-grey row:

$A_m(n)=\sum_{k=0}^{\lfloor n/m\rfloor}\binom{n-(m-1)k}{k}.$

Since the problem demands at least one colored tile, we remove the \(k=0\) term:

$B_m(n)=A_m(n)-1=\sum_{k=1}^{\lfloor n/m\rfloor}\binom{n-(m-1)k}{k}.$

So the whole problem can already be written as

$\sum_{m=2}^{4}\sum_{k=1}^{\lfloor 50/m\rfloor}\binom{50-(m-1)k}{k}.$

The Recurrence Used by the Implementations

The code evaluates the same quantity with a small dynamic program. For a row of length \(n\), inspect the last position. Either that last cell is grey, in which case the first \(n-1\) cells form any tiling counted by \(A_m(n-1)\), or the row ends with one colored tile of length \(m\), in which case the first \(n-m\) cells form any tiling counted by \(A_m(n-m)\).

This gives the recurrence

$A_m(n)=A_m(n-1)+A_m(n-m),$

together with the initial conditions

$A_m(0)=1,\qquad A_m(r)=0\text{ for }r<0.$

Equivalently, for \(0\le n<m\) we simply have \(A_m(n)=1\), because the all-grey tiling is the only possibility. For \(m=2\) this is the shifted Fibonacci recurrence \(A_2(n)=F_{n+1}\), while \(m=3\) and \(m=4\) follow the same dynamic idea without needing a special closed form.

Worked Example: A Row of Length 5

The short example in the statement is a perfect check on the formulas.

For red tiles \((m=2)\),

$B_2(5)=\binom{4}{1}+\binom{3}{2}=4+3=7.$

The first term counts the 4 placements of one red tile, and the second term counts the 3 placements of two red tiles.

For green tiles \((m=3)\),

$B_3(5)=\binom{3}{1}=3.$

For blue tiles \((m=4)\),

$B_4(5)=\binom{2}{1}=2.$

Hence the total for length 5 is

$B_2(5)+B_3(5)+B_4(5)=7+3+2=12,$

which matches the known checkpoint and confirms that the three colors are counted separately and then added.

Assembling Problem 116

Define

$T(n)=B_2(n)+B_3(n)+B_4(n).$

Then Problem 116 asks for \(T(50)\). The implementations compute \(A_2(50)\), \(A_3(50)\), and \(A_4(50)\) by recurrence, subtract 1 from each to exclude the all-grey row, and sum the three results.

How the Code Works

The C++, Python, and Java implementations all use the same per-color dynamic program. For a chosen tile length \(m\), they allocate a table for row lengths \(0,1,\dots,50\), set the length-0 count to 1, and then fill the table from left to right. At each length \(n\), they begin with the contribution from ending in a grey square, namely the count for \(n-1\), and if \(n\ge m\) they add the contribution from ending in one colored tile of length \(m\).

After the table entry for length 50 has been computed, the implementation subtracts 1 to discard the all-grey tiling. The outer logic repeats the same calculation for \(m=2\), \(m=3\), and \(m=4\), then adds the three one-color answers.

The C++ implementation also includes a small checkpoint based on the length-5 example, while the Python and Java versions directly evaluate the length-50 case. In every language, however, the underlying algorithm is the same recurrence \(A_m(n)=A_m(n-1)+A_m(n-m)\).

Complexity Analysis

For one tile length \(m\), the dynamic program fills one table of size \(n+1\), so it runs in \(O(n)\) time and uses \(O(n)\) memory. Here \(n=50\), so each pass is tiny.

Problem 116 performs exactly three such passes, one for each tile length in \(\{2,3,4\}\). Therefore the total running time is \(O(3n)=O(n)\) and the space usage is \(O(n)\). Because the set of colors is fixed, the constant factor is small; in fact, for \(n=50\) the computation is effectively instantaneous.

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=116
2. Tiling problem: Wikipedia - Tiling problem
3. Binomial coefficient: Wikipedia - Binomial coefficient
4. Linear recurrence: Wikipedia - Recurrence relation
5. Fibonacci number: Wikipedia - Fibonacci number