No.533

$i$ 段目に到達したときに最後の step が $j$ あるときの組み合わせの数を $A(i, j)$ とすると,

$$A(i, 1) = A(i-1, 2) + A(i-1, 3) \\ A(i, 2) = A(i-2, 1) + A(i-2, 3) \\ A(i, 3) = A(i-3, 1) + A(i-3, 2)$$

である. ただし,

$$\begin{matrix} A(1, 1) = 1 & A(1, 2) = 0 & A(1, 3) = 0 \\ A(2, 1) = 0 & A(2, 2) = 1 & A(2, 3) = 0 \\ A(3, 1) = 1 & A(3, 2) = 1 & A(3, 3) = 1 \end{matrix}$$

である.