アルゴリズムと計算量の問題

番号 $0,1,2,3,4,5$ の $6$ 個のセルからなる、線形探査法（オープンアドレス法）のハッシュ表がある。最初はすべてのセルが空である。この表に、互いに異なる $4$ 個のキーを $1$ 個ずつ順に挿入する（削除は行わない）。

キー $x$ を挿入するときは、ハッシュ値 $h(x)\in \{0,1,\dots ,5\}$ から始めて、セル $h(x),h(x)+1,h(x)+2,\dots$（番号は $6$ を法として考え、セル $5$ の次はセル $0$ とする）の順に調べ、最初に見つかった空のセルにキーを格納する。調べたセルの個数（キーを格納した空のセルも $1$ 個と数える）を、その挿入の探査回数とよぶ。

各キーのハッシュ値は $0,1,\dots ,5$ のどれかに等確率 $\frac{1}{6}$ で定まり、キーどうしのハッシュ値は互いに独立であるとする。$4$ 個のキーの挿入における探査回数の合計の期待値を求めよ。

番号 $0,1,2,3,4$ の $5$ 個のスロットからなるハッシュ表が最初は空である。この表に、互いに異なる $3$ 個のキーを $1$ 個ずつ順に、次の線形探査法（オープンアドレス法）で挿入する。

• キーのハッシュ値を $h$ とし、スロット $h,h+1,h+2,\dots$ の順に（番号は $5$ を法として考え、スロット $4$ の次はスロット $0$ とする）調べ、最初に見つかった空のスロットにそのキーを入れる。
• $1$ 個のスロットを調べることを探査 $1$ 回と数える。キーを入れた空のスロットを調べることも $1$ 回に数える（たとえば、スロット $h$ が空ならば探査は $1$ 回）。

各キーのハッシュ値は $0,1,2,3,4$ のどれかに等確率 $\frac{1}{5}$ で定まり、キーどうしのハッシュ値は互いに独立であるとする。$3$ 個のキーを挿入し終えるまでの探査回数の合計の期待値を求めよ。

バケット数 $3$ のチェイン法ハッシュ表が最初は空である。この表に、互いに異なる $4$ 個のキーを挿入する。各キーのハッシュ値は $3$ 個のバケットのどれかに等確率 $\frac{1}{3}$ で定まり、キーどうしのハッシュ値は互いに独立であるとする。$4$ 個のキーをすべて挿入し終えたとき、キーを $2$ 個以上含むバケットの個数の期待値を求めよ。

バケット数 $20$ のチェイン法ハッシュ表に、互いに異なる $6$ 個のキーを挿入する。各キーのハッシュ値は $20$ 個のバケットのどれかに等確率 $\frac{1}{20}$ で定まり、キーどうしのハッシュ値は互いに独立であるとする。$6$ 個のキーから選んだ $2$ 個のキーの組（順序は考えない）のうち、$2$ 個が同じバケットに入る組を「衝突する組」と呼ぶ。衝突する組の個数の期待値を求めよ。

$1$ 円、$4$ 円、$6$ 円の硬貨がそれぞれ十分な枚数あるとする。$0$ 以上の整数 $n$ に対し、$n$ 円をちょうど支払うときの硬貨の枚数の最小値を $M(n)$ とする（$M(0)=0$ とする）。$M(n)$ は、$n\ge 1$ のとき漸化式
$$M(n)=\underset{c\in \{1,4,6\},c\le n}{\min }\{M(n-c)+1\}$$
を満たす。この漸化式を用いて $M(0),M(1),\dots$ の表を順に埋め、$M(14)$ を求めよ。