# Arrange blocks to form matrix of $N \times 3$

Given are the blocks of 3 different colors (Red,Green and Blue).

Red colored block of size $1 \times 3.$ Green colored block of size $1 \times 2.$ Blue colored block of size $1 \times 1.$

We need to count the number of ways to make matrix of size $N \times 3$, for given $N.$

Note : The block can be used horizontally as well as vertically. So the red and green block can be used in two different ways (horizontally and vertically) while the blue block can be used only in one way (being of size $1 \times 1,$ it is immaterial how you place the block ).

Example : For $N=2$ answer is $29.$

The possible arrangements are:

Nice question!

Let $$a_n$$ be the number of desired arrangements for an $$n$$ by $$3$$ matrix and we'd like to find a recursive formula for it.

For the sake of simplicity, let $$1$$ denote the use of a $$1 \times 3,$$ block $$2$$ denote the use of a $$1 \times 2$$ block and $$3$$ the use of a $$1\times 1$$ block. Let also $$1v$$ denote the use of a vertical $$1 \times 3$$ block and likewise, $$1h$$ the horizontal use.

1) There are $$4$$ possible ways to only cover the first row $$(1h, (2h)3, 3(2h),(333))$$ (where $$(2h)3$$ means a horizontal $$1 \times 2$$ block followed by a $$1 \times 1$$ block) and for each configuration the rest of $$(n-1) \times 3$$ matrix can be filled out with $$a_{n-1}.$$

2) By investigation, there are $$13$$ possible ways to only cover the first two rows purely, i.e. those configurations which are not coming from a covering of the first row in case 1. Any such configuration, has to have at least one $$2v.$$ To see exactly why there are $$13$$ configurations, note that there are $$29$$ configurations in total as it was shown in the picture, where $$4\times 4=16$$ are coming from configurations of covering the first row, so $$29-16=13.$$

3) Further investigations (counting by hand, using case 2) shows that there are $$70$$ possible ways to only cover the first three rows purely which are not coming from a covering of the first row and a covering of the first two rows. Such a configuration must have at least one $$1v.$$

Finally, the recursive formula we get is

$$a_n= 4a_{n-1}+13a_{n-2}+70a_{n-3}.$$

Wolframalpha shows its characteristic polynomial has only one positive real root $$x\simeq 7.1729$$ so the complexity of this recursive approach is exponential which is not a surprise!

P.S. Try first and then let me know if you cannot find the number of configurations for case 3.