Строите матрицу перехода между рядами (43х43, как описано в ответе
Andy_U ), потом возводите её в 9-ю степень (поскольку у нас 9 переходов) и считаете сумму всех элементов (поскольку первый и последний ряд могут быть любыми). Всё.
Работает для любого числа рядов, хоть для триллиона :) Только потребуется быстрое возведение в степень.
Но это будет число способов построить стену. Если имелось в виду число наборов кирпичей (сколько может быть кирпичей 3x1 и сколько 4x1), то надо подумать, как сделать проще всего.