No.314

長さ $n$ のケンケンパコースで, 最後の $k$ 個が「ケン」である組み合わせの数を $C(n, k)$ とすると,

$$C(n, 0) = C(n-1, 1) + C(n-1, 2) \\ C(n, 1) = C(n-1, 0) \\ C(n, 2) = C(n-1, 1)$$

s.t.

$$C(0, 0) = 1 \\ C(0, 1) = 0 \\ C(0, 2) = 0$$

となる.