次の関数 f(n,k)f(n, k)f(n,k) がある。f(4,2)f(4, 2)f(4,2) の値は幾らか。
f(n,k)={1(k=0),f(n−1,k−1)+f(n−1,k)(0<k<n),1(k=n).f(n, k) = \begin{cases} 1 & (k = 0), \\ f(n-1, k-1) + f(n-1, k) & (0 < k < n), \\ 1 & (k = n). \end{cases}f(n,k)=⎩⎨⎧1f(n−1,k−1)+f(n−1,k)1(k=0),(0<k<n),(k=n).
3
4
5
6
この漸化式は二項係数を表しています。f(4,2)f(4, 2)f(4,2) を展開すると次のようになります。
f(4,2)=f(3,1)+f(3,2)f(4, 2) = f(3, 1) + f(3, 2)f(4,2)=f(3,1)+f(3,2) f(3,1)=f(2,0)+f(2,1)=1+(f(1,0)+f(1,1))=1+(1+1)=3f(3, 1) = f(2, 0) + f(2, 1) = 1 + (f(1, 0) + f(1, 1)) = 1 + (1 + 1) = 3f(3,1)=f(2,0)+f(2,1)=1+(f(1,0)+f(1,1))=1+(1+1)=3 f(3,2)=f(2,1)+f(2,2)=(1+1)+1=3f(3, 2) = f(2, 1) + f(2, 2) = (1 + 1) + 1 = 3f(3,2)=f(2,1)+f(2,2)=(1+1)+1=3
f(4,2)=3+3=6f(4, 2) = 3 + 3 = 6f(4,2)=3+3=6
したがって、正解は「エ」です。