基本情報技術者 2014年秋期午前（科目A）問07

問題文

次の関数

f (n, k)

がある。

f (4, 2)

の値はいくらか。

f (n, k) = ⎩ ⎨ ⎧ 1 f (n - 1, k - 1) + f (n - 1, k) 1 (k = 0) (0 < k < n) (k = n)

選択肢

ア：3

イ：4

ウ：5

エ：6（正解）

次の関数 f(n, k) がある。f(4,2) の値はいくらか。【午前2 解説】

要点まとめ

結論：与えられた再帰定義はパスカルの三角における二項係数の定義と一致し、したがって f(4,2)=6 となります。
根拠：境界条件 $f (n, 0) = f (n, n) = 1$ と漸化式 $f (n, k) = f (n - 1, k - 1) + f (n - 1, k)$ は二項係数の再帰式そのものだからです。
差がつくポイント： $(k n)$ の閉形式やパスカルの三角を使って手早く計算し、添字の開始（0起算か1起算か）で誤らないことが重要です。

正解の理由

正解: エ（6）
与えられた再帰は二項係数（パスカルの三角）を定義する標準的な式です。すなわち

f (n, k) = (k n)

が成り立ちます。したがって

f (4, 2) = (2 4) = \frac{4 \times 3}{2 \times 1} = 6

となり、選択肢の中では「エ」が正しいです。

よくある誤解

「n や k の起点をずらす」: 行・列を 0 起点と 1 起点で取り違え、値をずらして計算してしまう。
「漸化式を見ずに別の公式を誤適用」: 頻繁に起きるのは順列や重複組合せの式を誤って使うミスです。
「手計算ミス」: $(2 4)$ を $4$ や $5$ と誤って計算する単純な乗除ミス。

解法ステップ

再帰式と境界条件を見て、これはパスカルの三角の定義であることを確認する。
$f (n, k) = (k n)$ と同一視してよいと判断する。
$(2 4)$ を計算する： $\frac{4 !}{2 ! 2 !} = \frac{24}{4} = 6$ 。もしくはパスカルの三角の第4行を参照して 1,4,6,4,1 の中央が 6 であることを確認する。

選択肢別の誤答解説

ア: 3 — これは $(2 3) = 3$ を誤って計算したか、あるいは n を 3 と見なしてしまった結果です。
イ: 4 — パスカルの三角の隣接する値（例えば行の先頭や末尾の 1 に隣接する 4）と混同した可能性や、 $(1 4) = 4$ と取り違えた誤りです。
ウ: 5 — 組合せの基本公式を誤適用した結果や、手計算での単純な計算ミスが考えられます。
エ: 6 — 正解。 $(2 4) = 6$ に対応します。

補足コラム

パスカルの三角の第4行（0起点で行番号が4）: 1, 4, 6, 4, 1。中央の 6 が $(2 4)$ 。
二項定理との関係： $(1 + x)^{n} = \sum_{k = 0}^{n} (k n) x^{k}$ の係数が二項係数です。
閉形式： $(k n) = \frac{n !}{k ! ( n - k )!}$ を使えば大きな値も高速に求められます。
実装例（Python）:

import math
def f(n,k):
    return math.comb(n,k)  # Python 3.8+
print(f(4,2))  # 6

漸化式ベースでのメモ化（動的計画）も有効です。

FAQ

Q1: 定義は全ての整数 n,k について成り立ちますか？
A1: 本来の式は

0 \leq k \leq n

を前提としています。

k < 0

や

k > n

の場合は 0 と定義することが多いです（組合せの意味から）。

Q2: たとえば f(5,2) はどう計算しますか？
A2:

(2 5) = \frac{5 \times 4}{2} = 10

。またはパスカルの三角で確認できます。

Q3: 大きな n,k を速く計算するには？
A3: 組合せの閉形式を階乗や対数を使って計算するか、動的計画（漸化式をテーブルで埋める）や整数向けの効率的なアルゴリズム（乗除を順に行う）を用います。

関連キーワード: 二項係数、パスカルの三角、漸化式、組合せ、再帰、動的計画法、二項定理、数学的帰納法

← 前の問題へ次の問題へ →

\ せっかくなら /

基本情報技術者を
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！