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

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

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

番号 $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$ 個のキーを挿入し終えるまでの探査回数の合計の期待値を求めよ。

互いに異なる $6$ 個の実数を、$6!$ 通りの並べ方のどれもが等確率 $\frac{1}{720}$ で起こるように並べ、配列 $A[1],A[2],\dots ,A[6]$ を作る。$1\leqq i<j\leqq 6$ を満たす整数の組 $(i,j)$ のうち、$A[i]>A[j]$ となるものを転倒といい、転倒の個数を $X$ とする（$X$ は、この配列を挿入ソートで昇順に並べかえるときに行われる隣り合う要素の交換の回数に等しい）。$X$ の期待値 $E(X)$ を求めよ。