基本情報技術者 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（正解）

🔒 解説は解答すると表示されます

二項係数と漸化式【午前解説】

正解の理由

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

f (n, k) = (k n)

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

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

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

解法ステップ

再帰式と境界条件を見て、これはパスカルの三角の定義であることを確認する。
$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$ に対応します。

よくある誤解

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

補足コラム

パスカルの三角の第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: 組合せの閉形式を階乗や対数を使って計算するか、動的計画（漸化式をテーブルで埋める）や整数向けの効率的なアルゴリズム（乗除を順に行う）を用います。

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

← 前の問題へこの年度をクイズで解く次の問題へ →

\ せっかくなら /

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

クイズ画面へ遷移する→

すぐに利用可能！