Suppose we have a wall of n*3 size, and bricks of size 1*3, 2*3, and 3*3, the bricks can be put horizontally and vertically, what is the total number of ways to arrange the bricks to fill the wall? What is the recurrence relation of this problem?

I think it is T(n) = T(n-1) 2T(n-2) 7T(n-3), because for T(n-2) we have 1x3 1x3 or 2x3 so 2T(n-2). For three, 1x3 1x3 1x3, 1x3 2x3 or 2x3 1x3 and same for horizontal, plus 3x3 so we have 7dp(n-3), is this correct?

Thank you!

CodePudding user response：

This is almost right, but it over-counts several terms. For example, a solution S for T(n-2) can have two vertical 1-bricks added after it to become a solution for T(n). If you add one 1-brick after S, it's a solution for T(n-1), so the arrangement S two 1-bricks is being counted in your T(n-2) and T(n-1) terms.

Instead, think about how a solution S for T(n) ends on the right. You can show that the (n-1) x 3 initial segment of S is valid for T(n-1) if and only if the final block of S is a vertical 1-block.
Otherwise, when is the (n-2) x 3 initial segment of S the longest valid initial segment of S? Exactly when S ends with a vertical 2-block (if it ended with two vertical 1-blocks, the longest valid initial segment has length n-1, which we've already counted).

The final case is n-3: figure out how many configurations of the last 3 x 3 space are possible such that the longest valid initial segment of S has length n-3. As a hint: the answer, call it 'c', is smaller than 7, which, as you showed, is the count of all configurations of a 3 x 3 space. These give you the coefficients for the recursion, T(n) = T(n-1) T(n-2) c*T(n-3), with appropriate base cases for n = 1, 2 and 3.