No.457

左向きを数えることを考える.

$i$ 文字目まで見たときに (^^*) の $j$ 文字目まで完成している組み合わせの数を $A(i, j)$ とすると,

$i$ 文字目が ( のとき:

$$A(i, 1) = A(i-1, 1) + 1$$

$i$ 文字目が ^ のとき:

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

$i$ 文字目が * のとき:

$$A(i, 4) = A(i-1, 3)$$

$i$ 文字目が * のとき:

$$A(i, 5) = A(i-1, 5) + A(i-1, 4)$$

となる.

右向きも同様に数える.