組合せ

ある学校の文化祭で、出し物の準備を手伝ってくれる生徒の候補が $12$ 人いる。この $12$ 人の中から、準備係を $10$ 人選ぶ。選ばれた $10$ 人の間に役割の区別はないものとするとき、選び方は全部で何通りあるか。

ある部活動には部員が $12$ 人いる。この $12$ 人の中から、試合に出場する $10$ 人を選ぶ。選び方は全部で何通りあるか。ただし、選ぶ $10$ 人の間に順番や役割の区別はないものとする。

ある部には部員が $12$ 人いる。この $12$ 人の中から、大会に出場する $10$ 人を選ぶ。選び方は全部で何通りあるか。ただし、選ばれた $10$ 人の間に役割の区別はないものとする。

袋の中に赤玉 $4$ 個と白玉 $3$ 個の合計 $7$ 個の玉が入っている。この袋から玉を $3$ 個同時に取り出すとき、取り出した $3$ 個のうち少なくとも $1$ 個が白玉である確率を求めよ。

袋の中に赤玉が $4$ 個、白玉が $3$ 個、合わせて $7$ 個の玉が入っている。この袋から玉を $3$ 個同時に取り出すとき、取り出した玉の中に白玉が少なくとも $1$ 個含まれる確率を求めよ。

袋の中に赤玉 $5$ 個と白玉 $3$ 個、合計 $8$ 個の玉が入っている。この袋から玉を $3$ 個同時に取り出すとき、少なくとも $1$ 個は白玉である確率を求めよ。

1 個のさいころを 4 回続けて投げるとき、$1$ の目がちょうど $2$ 回出る確率を求めよ。

ある選手がバスケットボールのフリースローを $1$ 回投げるとき、成功する確率は $\frac{2}{3}$ である。この選手がフリースローを $4$ 回投げるとき、ちょうど $3$ 回成功する確率を求めよ。ただし、各回の成功・失敗は他の回の結果に影響しないものとする。

参加費 $200$ 円を払って、次のゲームを $1$ 回行う。

硬貨を $3$ 枚同時に投げ、表が出た枚数に応じて賞金を受け取る。表が $3$ 枚なら $800$ 円、表が $2$ 枚なら $200$ 円を受け取り、表が $1$ 枚以下なら賞金はない。

受け取る賞金から参加費 $200$ 円を引いた金額（損得の金額。損をしたときは負の値とする）の期待値を求めよ。答えは円単位の数値で答えよ。

袋の中に赤玉が $3$ 個、白玉が $2$ 個、合わせて $5$ 個の玉が入っている。この袋から同時に $3$ 個の玉を取り出し、取り出した赤玉の個数を $X$ とする。確率変数 $X$ の確率分布を求め、確率 $P(X\geqq 2)$ を求めよ。

袋の中に赤玉が $3$ 個、白玉が $4$ 個、合わせて $7$ 個の玉が入っている。この袋から同時に $3$ 個の玉を取り出し、取り出した玉のうち赤玉の個数を $X$ とする。確率変数 $X$ の確率分布を求め、それを用いて確率 $P(X\geqq 2)$ を求めよ。

袋の中に赤玉が $3$ 個、白玉が $2$ 個、合わせて $5$ 個の玉が入っている。この袋から同時に $3$ 個の玉を取り出し、取り出した赤玉の個数を $X$ とする。確率変数 $X$ の確率分布を調べ、確率 $P(X\geqq 2)$ を求めよ。

$3$ 枚の硬貨を同時に $1$ 回投げ、表が出た枚数を $X$ とする。確率変数 $Y=4X-1$ の分散 $V(Y)$ を求めよ。

確率変数 $X_1,X_2,\dots ,X_{10}$ は互いに独立で、それぞれ確率 $\frac{1}{2}$ で $1$、確率 $\frac{1}{2}$ で $-1$ をとるとする。$S_0=0$、$S_k=X_1+X_2+\cdots +X_k(k=1,2,\dots ,10)$ とおく（単純対称ランダムウォーク）。このとき、
$$\underset{0\le k\le 10}{\max }{S}_k\ge 4$$
となる確率を求めよ。

$X_1,X_2,\dots ,X_{10}$ を独立な確率変数で、各 $X_i$ は $P(X_i=1)=P(X_i=-1)=\frac{1}{2}$ を満たすとする。$S_0=0$、$S_k=X_1+X_2+\cdots +X_k(k=1,2,\dots ,10)$ とおく（単純対称ランダムウォーク）。

事象「$\underset{0\le k\le 10}{\max }{S}_k\ge 4$ かつ $S_{10}=2$」の確率を求めよ。

$X_1,X_2,\dots$ は互いに独立な確率変数で、各 $X_i$ は $P(X_i=1)=P(X_i=-1)=\frac{1}{2}$ を満たすとする。$S_0=0$, $S_k=X_1+X_2+\cdots +X_k(k\ge 1)$ で定まる単純対称ランダムウォークを考える。最初の $6$ ステップまでに一度でも $2$ に到達する確率、すなわち
$$P\left(\underset{0\le k\le 6}{\max }{S}_k\ge 2\right)$$
を求めよ。

袋の中に $1,2,3,4,5$ の数字が 1 つずつ書かれた 5 枚のカードが入っている。この袋から 2 枚のカードを同時に取り出し、次のように得点を定める。

• 取り出した 2 枚のカードに書かれた数の積が偶数のときは、その積を得点とする。
• 積が奇数のときは、得点を $0$ とする。

このとき、得点の期待値を求めよ。

方程式 $x+y+z=15$ を満たす正の整数の組 $(x,y,z)$ のうち、$x,y,z$ がすべて奇数であるものは何組あるか。

袋 A には赤玉 3 個と白玉 2 個が、袋 B には赤玉 2 個と白玉 4 個が入っている。1 個のさいころを 1 回投げ、1 または 2 の目が出たら袋 A を、それ以外の目が出たら袋 B を選ぶ。選んだ袋から玉を 2 個同時に取り出したところ、2 個とも赤玉であった。このとき、選んだ袋が A である確率を求めよ。

袋の中に、$1,2,3,4,5,6$ の数字が 1 つずつ書かれた 6 個の玉が入っている。この袋から玉を 2 個同時に取り出し、取り出した 2 個の玉に書かれた数のうち、大きい方から小さい方を引いた値を $X$ とする。$X$ の期待値を求めよ。

ケーキ店で、ショートケーキ、チーズケーキ、モンブランの 3 種類のケーキから合計 $10$ 個を買う。どの種類も少なくとも $1$ 個は買い、モンブランは $4$ 個以下にする。このような買い方は何通りあるか。ただし、同じ種類のケーキは区別しないものとし、どの種類も十分な数があるものとする。

袋の中に $1$ から $6$ までの整数が $1$ つずつ書かれた $6$ 枚のカードが入っている。この袋から同時に $2$ 枚のカードを取り出し、取り出したカードに書かれた数のうち小さい方を $X$ とする。確率変数 $X$ の分散 $V(X)$ を求めよ。

1 から 5 までの整数が 1 つずつ書かれた 5 枚のカードが袋に入っている。この袋から同時に 2 枚のカードを取り出し、書かれた 2 つの数の差の絶対値を $X$ とする。確率変数 $Y=-3X+7$ の標準偏差 $\sigma (Y)$ を求めよ。

袋の中に、$1$ から $6$ までの整数が $1$ つずつ書かれた $6$ 枚のカードが入っている。この袋から同時に $2$ 枚のカードを取り出し、取り出したカードに書かれた数のうち大きい方を $X$ とする。確率変数 $Y=3X+1$ の標準偏差 $\sigma (Y)$ を求めよ。

$1$ から $6$ までの数字が 1 つずつ書かれた $6$ 枚のカードが袋に入っている。この袋から同時に $2$ 枚のカードを取り出し、取り出したカードに書かれた $2$ つの数の差の絶対値を $X$ とする。確率変数 $X$ の分散 $V(X)$ を求めよ。

袋の中に、$1$ と書かれたカードが $1$ 枚、$2$ と書かれたカードが $2$ 枚、$3$ と書かれたカードが $3$ 枚、合わせて $6$ 枚のカードが入っている。この袋から同時に $2$ 枚のカードを取り出し、取り出したカードに書かれた数の和を $X$ とする。確率変数 $Y=3X-5$ の標準偏差 $\sigma (Y)$ を求めよ。

1 から 6 までの数字が 1 つずつ書かれた 6 枚のカードが箱に入っている。この箱から 2 枚のカードを同時に取り出し、2 枚に書かれた数の差（大きい方から小さい方を引いた値）を $X$ とする。確率変数 $3X-1$ の分散 $V(3X-1)$ を求めよ。

スピン $1$ の同種のボース粒子 3 個が、1 次元の無限に深い井戸型ポテンシャル
$$V(x)=\{\begin{array}{ll}0& (0<x<L)\\ \infty & (\text{otherwise})\end{array}$$
の中にある。粒子どうしの相互作用はなく、ハミルトニアンはスピンによらない。1 粒子のエネルギー準位は ${\epsilon }_n=\frac{n^2{\pi }^2{\hslash }^2}{2m{L}^2}$（$n=1,2,\dots$、$m$ は粒子の質量）で、各 $n$ の空間的な状態はただ 1 つである。

この 3 粒子系の基底状態の縮退度（基底状態のエネルギーをもつ、線形独立な 3 粒子状態の数）を求めよ。

互いに相互作用しない区別できる $N$ 個の粒子からなる孤立系を考える。各粒子がとりうるエネルギー準位は、縮退のない $0$ と、縮退のない $\epsilon (\epsilon >0)$ の 2 つだけである。系の全エネルギーが $E=\frac{N\epsilon }{4}$ に固定されているとき、ミクロカノニカル分布にもとづいてこの系の温度 $T$ を求めよ。ただし、$N$ は 4 の倍数で十分大きく、エネルギー $\epsilon$ の準位にある粒子の数 $M$ とともにスターリングの近似 $\log n!\approx n\log n-n$ が使えるものとする。エントロピーはボルツマンの関係式 $S=k_B\log W$（$W$ は状態数、$k_B$ はボルツマン定数）で定め、温度は $\frac{1}{T}=\frac{\partial S}{\partial E}$ で定める。$T$ を $\epsilon$, $k_B$ を用いて表せ。

$A=\{1,2,3,4\}$, $B=\{a,b,c\}$ とする。$A$ の部分集合 $S$ と写像 $f:S\to B$ の組 $(S,f)$ 全体の集合
$$P=\{(S,f)\mid S\subseteq A,f\text{ は }S\text{ から }B\text{ への写像}\}$$
の濃度 $|P|$ を求めよ。ただし、$S=\varnothing$ のときは、$\varnothing$ から $B$ への写像は空写像のただ $1$ つであるとする。

1 項関数記号 $f$ と 1 項関係記号 $P$ からなる一階の言語（等号を含む）を考える。台集合を $A=\{1,2,3,4,5,6\}$ に固定し、関数 $f^{\mathcal{M}}:A\to A$ と部分集合 $P^{\mathcal{M}}\subseteq A$ の組を 1 つ定めるごとに構造 $\mathcal{M}=(A,f^{\mathcal{M}},P^{\mathcal{M}})$ が 1 つ定まるとする。次の 2 つの文
$${\phi }_1:\forall x(f(f(x))=x),{\phi }_2:\forall x(P(x)\to \neg P(f(x)))$$
をともにみたす構造 $\mathcal{M}$（すなわち $\mathcal{M}\models {\phi }_1\wedge {\phi }_2$ となる組 $(f^{\mathcal{M}},P^{\mathcal{M}})$）の個数を求めよ。ただし、同型な構造であっても $(f^{\mathcal{M}},P^{\mathcal{M}})$ が異なれば別のものとして数える。

2 項関係記号 $E$ だけからなる一階の言語（等号を含む）を考える。台集合を $A=\{1,2,3,4,5,6\}$ に固定し、$E$ の解釈 $E^{\mathcal{M}}\subseteq A\times A$ を 1 つ定めるごとに構造 $\mathcal{M}=(A,E^{\mathcal{M}})$ が 1 つ定まるとする。次の 3 つの文の連言を $\sigma ={\sigma }_1\wedge {\sigma }_2\wedge {\sigma }_3$ とおく。
$${\sigma }_1:\forall x\neg E(x,x)$$
$${\sigma }_2:\forall x\forall y(E(x,y)\to E(y,x))$$
$${\sigma }_3:\forall x\exists y\exists z(y\ne z\wedge E(x,y)\wedge E(x,z)\wedge \forall w(E(x,w)\to (w=y\vee w=z)\left)\right)$$
$\mathcal{M}\models \sigma$ となる $E^{\mathcal{M}}\subseteq A\times A$ の個数を求めよ（同型な構造も、$E^{\mathcal{M}}$ が集合として異なれば別に数える）。

$4$ 人のプレイヤー $1,2,3,4$ が、共同の設備を作るために、それぞれ同時に「出資する（$C$）」か「出資しない（$D$）」かを 1 回だけ選ぶ。出資したプレイヤーの人数を $k$（$0\le k\le 4$）とする。

• $k\ge 2$ のとき設備が完成し、$4$ 人全員がそれぞれ $3$ の便益を得る。$k\le 1$ のときは設備は完成せず、便益は $0$ である。
• 出資したプレイヤーは、設備が完成するかどうかにかかわらず費用 $2$ を負担する。

各プレイヤーの利得は（便益）$-$（自分が負担した費用）とする。このゲームの純粋戦略ナッシュ均衡（4 人の戦略の組）の個数を求めよ。

$4$ 変数のブール関数とは写像 $f:\{0,1{\}}^4\to \{0,1\}$ のこととし、$\{0,1\}$ を 2 元体 ${\mathbb{F}}_2$ と同一視する。各 $4$ 変数のブール関数 $f$ は、${\mathbb{F}}_2$ 上の多項式として
$$f(x_1,x_2,x_3,x_4)=\sum _{S\subseteq \{1,2,3,4\}}{a}_S\prod _{i\in S}{x}_i(a_S\in {\mathbb{F}}_2)$$
の形にただ 1 通りに表される（代数的標準形。$S=\varnothing$ のときの積は $1$ とする）。$a_S=1$ となる $S$ の要素の個数 $|S|$ の最大値を $f$ の次数とよぶ（恒等的に $0$ の関数の次数は $-\infty$ とする）。

次数がちょうど $2$ である $4$ 変数のブール関数の個数を求めよ。

半順序集合 $(Q,\le )$ は、対象を $Q$ の元とし、$p\le q$ のときに限り $p$ から $q$ への射がちょうど $1$ つ存在する（それ以外のときは射が存在しない）圏とみなす。

集合 $\{1,2,3,4\}$ の分割（空でない互いに素な部分集合（ブロック）への分け方）全体を ${\Pi }_4$ とし、分割 $\pi ,\sigma$ について「$\pi$ の各ブロックが $\sigma$ のあるブロックに含まれる」ときに $\pi \le \sigma$ と定める（細分による順序）。この半順序集合 $({\Pi }_4,\le )$ を圏とみなしたとき、射（恒等射も含む）の総数を求めよ。

正の整数 $n$ に対し、集合 $\{1,2,\dots ,n\}$ 上の置換（$\{1,2,\dots ,n\}$ からそれ自身への全単射）$\sigma$ で、すべての $i(1\le i\le n)$ について $\sigma (i)\ne i$ を満たすもの（攪乱順列）の個数を $D_n$ とする。

包除原理を用いて、正の整数 $n$ について「$D_n$ が偶数であることと、$n$ が奇数であることは同値である」ことを証明せよ。

$a,b$ を $a\ge b\ge 0$ をみたす整数とし、$n=a+b\ge 1$ とする。ヤング図形 $\lambda =(a,b)$ とは、第 $1$ 行の第 $1$ 列から第 $a$ 列までの $a$ 個の箱と、第 $2$ 行の第 $1$ 列から第 $b$ 列までの $b$ 個の箱からなる図形とする（$b=0$ のときは第 $1$ 行だけ。$a\ge b$ なので、第 $2$ 行の各箱の真上には第 $1$ 行の箱がある）。$\lambda$ の標準ヤング盤とは、$\lambda$ の $n$ 個の箱に $1,2,\dots ,n$ を $1$ つずつ書き入れたもので、次の 2 条件をみたすものをいう。ここで第 $i$ 行第 $j$ 列の箱に書かれた数を $T(i,j)$ と書く。

• 行の条件: $T(1,1)<T(1,2)<\cdots <T(1,a)$ かつ $T(2,1)<T(2,2)<\cdots <T(2,b)$。
• 列の条件: $1\le j\le b$ をみたすすべての $j$ について $T(1,j)<T(2,j)$。

$\lambda =(a,b)$ の標準ヤング盤の個数を $f^{(a,b)}$ とするとき、
$$f^{(a,b)}=\left(\genfrac{}{}{0ex}{}{n}{b}\right)-\left(\genfrac{}{}{0ex}{}{n}{b-1}\right)$$
が成り立つことを証明せよ。ただし $\left(\genfrac{}{}{0ex}{}{n}{-1}\right)=0$ とし、フック長公式は用いないものとする。

$n\ge 2$ を整数、$k$ を $1\le k\le n-1$ を満たす整数とし、
$$P=\left\{x\in {\mathbb{R}}^n:0\le x_i\le 1(i=1,\dots ,n),\sum _{i=1}^n{x}_i=k\right\}$$
とおく。ここで $P$ の頂点とは、$P$ の端点、すなわち「$y,z\in P$ かつ $x=\frac{1}{2}(y+z)$ ならば $y=z=x$」を満たす点 $x\in P$ のことをいう。

$P$ の頂点全体が、成分がすべて $0$ または $1$ で、$1$ の個数がちょうど $k$ 個であるベクトル全体と一致することを示し、特に $P$ の頂点の個数が $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ であることを証明せよ。

$1,2,\dots ,8$ の $8$ 個の数を、それぞれちょうど $1$ 回ずつ使って左から右へ $1$ 列に並べる。このような並べ方 $8!$ 通りのうち、どの $i$ $(1\le i\le 7)$ についても「$i$ のすぐ右隣に $i+1$ がある」ことが起こらないものは何通りあるか。

出力が $8$ 通りの値 $\{0,1,2,\dots ,7\}$ のどれかになるハッシュ関数 $H$ を考える。$H$ はランダムオラクルとみなす。つまり、互いに異なる入力に対する出力は、それぞれ独立に $8$ 通りの値から等確率で選ばれるものとする。

攻撃者は、署名してもらいたい「正当な文書」の変種 $x_1,x_2,x_3$ と、すり替えたい「不正な文書」の変種 $y_1,y_2,y_3$ を用意する。これら $6$ 個の入力は互いに異なる。攻撃者は
$$H(x_i)=H(y_j)$$
を満たす $i,j(1\le i\le 3,1\le j\le 3)$ が少なくとも $1$ 組存在するとき、攻撃に成功するものとする。正当な文書どうし、または不正な文書どうしでハッシュ値が一致しても、それだけでは成功とはみなさない。

攻撃に成功する確率を、既約分数で求めよ。

出力が $8$ 通りの値 $\{0,1,2,\dots ,7\}$ のどれかになるハッシュ関数 $H$ を考える。$H$ はランダムオラクルとみなす。すなわち、互いに異なる入力に対する出力は、それぞれ独立に $8$ 通りの値から等確率で選ばれるものとする。

攻撃者は互いに異なる $5$ 個の入力 $m_1,m_2,\dots ,m_5$ についてハッシュ値 $H(m_1),\dots ,H(m_5)$ を計算する。このとき、ある値 $v$ について $H(m_i)=v$ となる $i$ が $3$ 個以上存在する確率を求めよ。この事象を「$3$ 重衝突（3-マルチコリジョン）が起こる」という。

$A=\{1,2,3,4,5\}$ とする。$A$ 上の同値関係 $R$ と写像 $f:A\to A$ の組 $(R,f)$ のうち、次の条件を満たすものの個数を求めよ。
$$\text{すべての }x,y\in A\text{ に対して},xRy⟹f(x)Rf(y).$$
ただし、同値関係は $A\times A$ の部分集合として異なるものを区別し、写像は対応が異なるものを区別する。

命題変数 $x_1,x_2,x_3,x_4$ だけを用いた命題論理の論理式を考える（結合子は $\neg ,\wedge ,\vee ,\to$ を用いる）。2 つの論理式は、$x_1,\dots ,x_4$ へのすべての真理値割り当て（$2^4=16$ 通り）で同じ真理値をとるとき同値であるという。また、論理式 $\phi$ に現れる $x_3$ と $x_4$ を同時に入れ替えて得られる論理式を ${\phi }^{\sigma }$ と書く。

次の 4 つの条件をすべて満たす論理式 $\phi$ を考える。

(1) $(x_1\wedge x_2)\to \phi$ はトートロジーである。

(2) $\phi \to (x_1\vee x_2\vee x_3)$ はトートロジーである。

(3) $\phi$ と ${\phi }^{\sigma }$ は同値である。

(4) $\phi$ を真にする真理値割り当て（充足割り当て）はちょうど $8$ 個である。

このような論理式 $\phi$ は、同値なものを同一視すると何個あるか。

1 項関数記号 $f$ と 1 項関係記号 $P$ からなる等号付きの一階の言語を考える。台集合を $A=\{1,2,3,4,5,6\}$ に固定する。写像 $g:A\to A$ と部分集合 $S\subseteq A$ を 1 つずつ選ぶごとに、$f$ を $g$、$P$ を $S$ と解釈し、等号は $A$ 上の本当の等号と解釈して、構造 $\mathcal{M}=(A,g,S)$ が 1 つ定まる。

次の文を $\phi$ とする。
$$\phi :\forall x(f(f(x))=x)\wedge \forall x(f(x)=x\to P(x))\wedge \forall x(P(x)\wedge P(f(x))\to f(x)=x)$$

組 $(g,S)$ のうち、$\mathcal{M}=(A,g,S)$ が $\phi$ のモデルとなる（$\mathcal{M}\models \phi$ となる）ものの個数を求めよ。ただし、同型な構造でも $(g,S)$ が異なれば別のものとして数える。

体細胞の染色体数が $2n=12$ のある植物がある。この植物の体細胞には、父親（花粉親）に由来する染色体 $6$ 本と、母親（胚珠親）に由来する染色体 $6$ 本が含まれ、これらは $6$ 組の相同染色体をつくっている。

この植物の 1 個体が減数分裂によって配偶子をつくるとき、各相同染色体の組の 2 本は、互いに独立に分かれてそれぞれ別の配偶子に入るものとする。また、乗換え（交さ）は起こらず、突然変異も起こらないものとする。父親由来の染色体と母親由来の染色体を区別して考える。

この個体がつくる配偶子のうち、父親由来の染色体をちょうど $2$ 本含む配偶子の染色体の組み合わせは何通りあるか。

組成式 $\mathrm{A}{\mathrm{H}}_3$ で表される仮想的な結晶を考える。この結晶では、A 原子が単純立方格子の格子点を占め、各 A 原子は最近接の 6 個の A 原子と辺で結ばれている。隣り合う 2 個の A 原子を結ぶ辺の上には、H 原子がちょうど 1 個ずつある（したがって A 原子 1 個あたり H 原子は 3 個である）。各 H 原子は、その辺の両端の A 原子のどちらか一方に近い位置（2 通り）のいずれかを占める。

この結晶は $\mathrm{A}{\mathrm{H}}_3$ 分子からなるため、次の規則が成り立つ。

「どの A 原子についても、その A 原子を端とする 6 本の辺の H 原子のうち、ちょうど 3 個がその A 原子に近い位置にある。」

この規則を満たす配置はすべて同じエネルギーをもち、絶対零度でも等しい確率で凍結されているとする。Pauling が氷の残余エントロピーを見積もったのと同じ近似（各 A 原子についての規則が互いに独立に満たされるとみなす近似）を用いて、この結晶の $\mathrm{A}{\mathrm{H}}_3$ $1$ mol あたり（A 原子 $1$ mol あたり）の残余エントロピーを求めよ。気体定数を $R=8.314\mathrm{J}{\mathrm{K}}^{-1}\mathrm{mo}{\mathrm{l}}^{-1}$ とし、単位を $\mathrm{J}{\mathrm{K}}^{-1}\mathrm{mo}{\mathrm{l}}^{-1}$ として、式の形ではなく数値を有効数字 3 桁に丸めて答えよ。結晶は十分大きく、表面の効果は無視してよい。

数直線上の原点に点 $\mathrm{P}$ がある。1 個のさいころを投げ、出た目が $1$ または $2$ ならば $\mathrm{P}$ を正の向きに $2$ だけ動かし、それ以外の目ならば $\mathrm{P}$ を負の向きに $1$ だけ動かす。この試行を $6$ 回繰り返す。

$6$ 回目の試行の直後に $\mathrm{P}$ が原点にあり、かつ $1$ 回目から $5$ 回目までのどの試行の直後にも $\mathrm{P}$ が原点にない確率を求めよ。

箱の中に $1,2,3,4,5,6$ の数字が 1 つずつ書かれた 6 枚のカードが入っている。この箱から同時に 2 枚のカードを取り出し、取り出したカードに書かれた数のうち大きい方を $X$ とする。確率変数 $Y=3X+1$ の標準偏差 $\sigma (Y)$ を求めよ。

袋の中に $1,2,3,4,5,6$ の数字が 1 つずつ書かれた 6 枚のカードが入っている。この袋から同時に 2 枚のカードを取り出し、取り出した 2 枚のカードに書かれた数のうち大きい方から小さい方を引いた値を $D$ とする。さらに、得点 $Y$ を $Y=3D+2$ で定める。確率変数 $Y$ の標準偏差を求めよ。

袋の中に、$1$ と書かれたカードが $1$ 枚、$2$ と書かれたカードが $2$ 枚、$3$ と書かれたカードが $3$ 枚、合計 $6$ 枚のカードが入っている。この袋から同時に $2$ 枚のカードを取り出し、取り出した $2$ 枚に書かれた数の差の絶対値を $X$ とする。確率変数 $Y=5X+1$ の分散 $V(Y)$ を求めよ。

袋の中に赤玉が $4$ 個、白玉が $2$ 個、合わせて $6$ 個の玉が入っている。この袋から玉を $1$ 個ずつ取り出す。取り出した玉は袋に戻さず、白玉がはじめて取り出された時点で操作を終える。操作を終えるまでに取り出した玉の個数（最後に取り出した白玉も含める）を $X$ とする。確率変数 $3X+2$ の標準偏差 $\sigma (3X+2)$ を求めよ。

箱の中に赤玉が $2$ 個、白玉が $4$ 個、合わせて $6$ 個の玉が入っている。この箱から玉を $1$ 個ずつ取り出していき（取り出した玉は箱に戻さない）、$2$ 個目の赤玉が取り出された時点で操作を終了する。終了するまでに取り出した玉の個数（$2$ 個目の赤玉も含む）を $X$ とする。確率変数 $X$ の分散 $V(X)$ を求めよ。

$4\times 4$ のマス目（16 個の正方形のマスからなる正方形の盤）に、区別のつかない 4 個の石を、どの 2 個も同じマスに入らないように置く。盤を回転または裏返し（正方形の対称移動、全部で 8 通り）によって重ね合わせられる置き方は同じものとみなすとき、異なる置き方は何通りあるか。

赤い玉 4 個と青い玉 6 個（同じ色の玉どうしは区別しない）の計 10 個を、円周上に等間隔に並べた 10 か所に 1 個ずつ置き、ひもを通して輪（ブレスレット）を作る。輪の回転および裏返しによって互いに重ね合わせられる並べ方は同じものとみなすとき、異なる輪は何通りできるか。

$5$ 次対称群 $S_5$ を考える。$S_5$ の位数 $3$ の部分群の個数を $p$、位数 $4$ の巡回部分群の個数を $q$、位数 $5$ の部分群の個数を $r$ とする。組 $(p,q,r)$ をこの順に求めよ。

二元体 ${\mathbb{F}}_2=\{0,1\}$ 上で考える。${\mathbb{F}}_2^4$ のベクトルのうち、ハミング重み（$1$ である成分の個数）が奇数であるものは全部で $8$ 個ある。これら $8$ 個のベクトルを列ベクトルとして、どれも $1$ 回ずつ、ある順に並べてできる $4\times 8$ 行列を $H$ とし、
$$C=\{\mathbf{x}\in {\mathbb{F}}_2^8\mid H{\mathbf{x}}^{\mathsf{T}}=0\}$$
で定まる符号長 $8$ の線形符号 $C$ を考える（$\mathbf{x}$ は行ベクトル）。$C$ の次元を $k$、最小距離を $d$、$C$ に含まれるハミング重みがちょうど $d$ の符号語の個数を $A_d$ とする。組 $(k,d,A_d)$ をこの順に求めよ。

二元体 ${\mathbb{F}}_2=\{0,1\}$ 上で、生成多項式
$$g(x)=x^4+x+1$$
で定まる符号長 $15$ の巡回符号 $C$ を考える。すなわち、符号語 $c=(c_0,c_1,\dots ,c_{14})\in {\mathbb{F}}_2^{15}$ を多項式 $c(x)=c_0+c_{1}x+\cdots +c_{14}{x}^{14}$ と同一視し、$C=\{c(x)\mid \mathrm{deg}c(x)\le 14,g(x)\text{ が }c(x)\text{ を割り切る}\}$ とする。なお、$g(x)$ は ${\mathbb{F}}_2$ 上の原始多項式である（既約であり、その根 $\alpha$ は $15$ 個の元 ${\alpha }^0,{\alpha }^1,\dots ,{\alpha }^{14}$ がすべて異なる、${\mathbb{F}}_{16}$ の $0$ でない元すべてとなる）。

この符号を誤り検出のためだけに用いる。送信した符号語 $c$ に誤りパターン $e\in {\mathbb{F}}_2^{15}$ が加わって $r=c+e$ が受信されたとき、$r\in C$ ならば「誤りなし」と判定し、$r\notin C$ ならば「誤りあり」と判定する。$e\ne 0$ で $r\in C$ となるとき、誤りは検出されない。

ハミング重み（$1$ である成分の個数）が $1$ 以上 $4$ 以下の誤りパターン $e$ のうち、検出されないものの個数を求めよ。

$q$ を素数のべきとし、${\mathbb{F}}_q$ を $q$ 個の元からなる有限体とする。${\mathbb{F}}_q[x]$ の多項式が既約であるとは、次数が $1$ 以上で、次数 $1$ 以上の 2 つの多項式の積に表せないことをいう。このとき、${\mathbb{F}}_q$ 上のモニックな $3$ 次既約多項式の個数は
$$\frac{q^3-q}{3}$$
であることを証明せよ。

ただし、${\mathbb{F}}_q[x]$ において、次数 $1$ 以上のモニック多項式はモニックな既約多項式の積に（並べ方を除いて）ただ 1 通りに分解されること（素因数分解の一意性）は用いてよい。

0 以上の整数 $n$ に対して $[n]=\{0,1,\dots ,n\}$ を通常の順序で全順序集合とみなし、対象を $[n](n\ge 0)$、射を（広義）単調写像とする圏を $\Delta$ とする。単体的集合とは関手 $X:{\Delta }^{\mathrm{op}}\to \mathbf{Set}$ のことで、$X_n=X([n])$ とおき、$X_n$ の要素を $n$-単体という。$n\ge 1$ と $0\le i\le n-1$ に対して、全射単調写像 ${\sigma }_i:[n]\to [n-1]$ を
$${\sigma }_i(j)=\{\begin{array}{ll}j& (j\le i)\\ j-1& (j\ge i+1)\end{array}$$
で定める。$x\in X_n$ が退化しているとは、ある $0\le i\le n-1$ と $y\in X_{n-1}$ により $x=X({\sigma }_i)(y)$ と書けることをいい、そうでない単体を非退化という（$0$-単体はすべて非退化）。

0 以上の整数 $p$ に対して $\Delta [p]={\mathrm{Hom}}_{\Delta }(-,[p])$ とし（$\theta :[m]\to [n]$ に対して $\Delta [p](\theta )(f)=f\circ \theta$）、単体的集合 $X,Y$ の積 $X\times Y$ を $(X\times Y{)}_n=X_n\times Y_n$、$(X\times Y)(\theta )=X(\theta )\times Y(\theta )$ で定める。

0 以上の整数 $p,q$ に対して、単体的集合 $\Delta [p]\times \Delta [q]$ は、$n>p+q$ ならば非退化 $n$-単体をもたず、非退化 $(p+q)$-単体をちょうど $\left(\genfrac{}{}{0ex}{}{p+q}{p}\right)$ 個もつことを示せ。

$N\ge 2$ を整数とし、その素因数分解を $N=p_1^{e_1}{p}_2^{e_2}\cdots p_r^{e_r}$（$p_1,\dots ,p_r$ は相異なる素数、$e_1,\dots ,e_r$ は正の整数）とする。$N$ の正の約数全体の集合を $D(N)$ とし、整除関係 $a\mid b$ による半順序集合 $(D(N),\mid )$ を圏 $\mathcal{C}$ とみなす。すなわち $\mathcal{C}$ の対象は $D(N)$ の要素で、$a,b\in D(N)$ に対し $a\mid b$ のとき ${\mathrm{Hom}}_{\mathcal{C}}(a,b)$ はただ 1 つの射 $a\to b$ からなり、そうでないとき空集合である（合成は一意に定まるものとする）。

正の整数 $k$ に対して、$\mathcal{C}$ の射の列 $(f_1,f_2,\dots ,f_k)$ で、各 $1\le j\le k-1$ について $f_j$ の終域と $f_{j+1}$ の始域が一致するもの（合成可能な $k$ 個の射の列）全体の集合を ${\mathcal{C}}_k$ とする（${\mathcal{C}}_1$ は $\mathcal{C}$ の射全体）。このとき
$$|{\mathcal{C}}_k|=\prod _{i=1}^r\left(\genfrac{}{}{0ex}{}{e_i+k+1}{k+1}\right)$$
が成り立つことを示せ。素因数分解の一意性は用いてよい。

1 個のさいころを $n$ 回投げる。ただし、$n$ は正の整数とする。$n$ 回のうち $3$ の倍数の目が出た回数を $X$ とし、確率変数 $Y$ を $Y=X\cdot 2^X$ で定める。$Y$ の分散 $V(Y)$ を $n$ の式で求めよ。

$n$ を $2$ 以上の整数とする。$1$ から $n$ までの整数が $1$ つずつ書かれた $n$ 枚のカードを無作為に横一列に並べる。$1\leqq i\leqq n-1$ を満たす整数 $i$ のうち、$i$ と書かれたカードと $i+1$ と書かれたカードが隣り合っている（順序は問わない）ものの個数を $X$ とする。確率変数 $X$ の分散 $V(X)$ を $n$ の式で表せ。

$4\times 4$ のマス目（$16$ 個の正方形のマス）から、ちょうど $4$ マスを選んで黒く塗り、残りの $12$ マスを白く塗る。マス目全体（正方形）の対称変換、すなわち中心のまわりの $0^{\circ },90^{\circ },180^{\circ },270^{\circ }$ の回転と、$4$ 本の対称軸（縦・横の中線 $2$ 本と対角線 $2$ 本）に関する裏返しの計 $8$ 個の変換のいずれかで互いに重ね合わせられる塗り方は同じものとみなす。このとき、異なる塗り方は何通りあるか。

集合 $\{1,2,3,4,5,6,7\}$ の置換（$\{1,\dots ,7\}$ から自分自身への全単射）$\sigma$ を考える。$\sigma$ を互いに素な巡回置換の積に分解する。このとき、不動点も長さ $1$ の巡回として数える。分解に現れる巡回の個数がちょうど $3$ であり、しかも $1$ と $2$ が同じ巡回に属するような $\sigma$ は何個あるか。

集合 $\{1,2,3,4,5,6,7\}$ からそれ自身への全単射（置換）$\sigma$ のうち、次の 2 つの条件をともに満たすものの個数を求めよ。

• すべての $i$ $(1\le i\le 7)$ について $\sigma (i)\ne i$
• すべての $i$ $(1\le i\le 6)$ について $\sigma (i)\ne i+1$

（たとえば $7$ 人の生徒 $1,\dots ,7$ が席替えをするとき、生徒 $i$ が元の席 $i$ にも右隣の席 $i+1$ にも座らないような座り方の数に当たる。席 $7$ の右隣は考えない。）

$3\times 3$ のマス目（正方形の盤）の $9$ 個のマスのうち、ちょうど $4$ 個を黒で、残りの $5$ 個を白で塗る。正方形の対称変換群（中心のまわりの $0^{\circ },90^{\circ },180^{\circ },270^{\circ }$ の回転と、$4$ 本の対称軸に関する裏返しの、合わせて $8$ 個の変換からなる二面体群）によって互いに重ね合わせられる塗り方は同じものとみなす。異なる塗り方は何通りあるか。

集合 $\{1,2,\dots ,10\}$ の分割（空でない互いに素なブロックへの分け方。ブロックの順序は区別しない）を考える。分割が非交差であるとは、$a<b<c<d$ を満たす $a,b,c,d\in \{1,\dots ,10\}$ で、$a,c$ が同じブロックに属し、$b,d$ がそれとは異なる同じブロックに属するようなものが存在しないことをいう。

$\{1,2,\dots ,10\}$ の非交差分割のうち、どのブロックも 2 個以上の要素を含む（要素 1 個だけのブロックを持たない）ものの個数を求めよ。

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

$n$ 個の元からなる集合の上の位相（開集合系）の個数を $T(n)$ とする。ただし、開集合系として異なるものは区別して数える（同相なものも別々に数える）。$T(3)=29$, $T(4)=355$ であることが知られている。これを用いて、集合 $X=\{1,2,3,4\}$ 上の位相 $\mathcal{O}$ のうち、位相空間 $(X,\mathcal{O})$ が連結となるものの個数を求めよ。

有限集合と写像のなす圏を $\mathbf{FinSet}$ とする。関手 $F:\mathbf{FinSet}\to \mathbf{FinSet}$ を次のように定める。

• 有限集合 $X$ に対して $F(X)=X^4=X\times X\times X\times X$
• 写像 $f:X\to Y$ に対して $F(f)(x_1,x_2,x_3,x_4)=(f(x_1),f(x_2),f(x_3),f(x_4))$

自然変換 $\eta :F\Rightarrow F$ のうち、自分自身との垂直合成について $\eta \circ \eta =\eta$ を満たすものの個数を求めよ。ここで $\eta \circ \eta =\eta$ とは、すべての有限集合 $X$ について ${\eta }_X\circ {\eta }_X={\eta }_X$ が成り立つことをいう。

仮想的な分子結晶 $\mathrm{X}{\mathrm{H}}_3$ の残余エントロピーを考える。結晶は $1$ mol の X 原子（$N=N_{\mathrm{A}}$ 個）からなる。それぞれの X 原子は、ほかの $6$ 個の X 原子と水素結合 $\mathrm{X}-\mathrm{H}\cdots \mathrm{X}$ で結ばれている。結晶全体は、各 X 原子からちょうど $6$ 本の結合が出ている網目になっている（結晶の表面の効果は無視する）。水素原子の配置は次の規則に従う。

• それぞれの X–X 結合の上には、水素原子がちょうど $1$ 個ある。その水素原子は、結合の両端の X 原子のうちどちらか一方の近くにある（$2$ 通り）。
• それぞれの X 原子の近くには、水素原子がちょうど $3$ 個ある（各 X 原子は $\mathrm{X}{\mathrm{H}}_3$ 分子をつくる）。

この規則を満たす配置はすべて同じエネルギーをもち、$0$ K では等しい確率で凍結されているとする。規則を満たす配置の数 $W$ は、ポーリングの近似で見積もる。すなわち、各 X 原子のまわりで規則が満たされる確率は、ほかの X 原子とは独立であるとみなす。

気体定数を $R$ とする。この結晶の $1$ mol あたりの残余エントロピー $S_0$ を、$R$ を用いた式で求めよ。

1 個のさいころを 5 回続けて投げ、出た目を順に $a_1,a_2,a_3,a_4,a_5$ とする。積 $a_1{a}_2{a}_3{a}_4{a}_5$ が $60$ の倍数になる確率を求めよ。

さいころを $1$ 回投げ、出た目を $k$ とする。中の見えない袋に赤玉 $k$ 個と白玉 $6-k$ 個の合計 $6$ 個の玉を入れる。この袋から玉を $2$ 個同時に取り出したところ、少なくとも $1$ 個は赤玉であった。この条件のもとで、袋に残った $4$ 個の玉から $1$ 個を取り出すとき、それが赤玉である条件付き確率を求めよ。

横一列に並んだ $6$ 枚の板を、左から順に $1$ 枚ずつ、赤・青・黄・緑の $4$ 色のうちいずれか $1$ 色で塗る。ただし、次の $2$ つの条件をともに満たすように塗る。

(条件1) 隣り合う $2$ 枚の板は異なる色で塗る。

(条件2) $4$ 色すべてを少なくとも $1$ 回は使う。

板はすべて区別し、塗り方は各板の色の組で区別する。このような塗り方は全部で何通りあるか。

1 個のさいころを 4 回続けて投げ、出た目を順に $a_1,a_2,a_3,a_4$ とする。積 $a_1{a}_2{a}_3{a}_4$ が $12$ の倍数になる確率を求めよ。

$1,1,2,2,3,3,4,4$ の数字が 1 つずつ書かれた 8 枚のカードがある。これらをよくまぜて、無作為に横 1 列に並べる。同じ数字が書かれたカードどうしがどこでも隣り合わない確率を求めよ。

区別のつかない $12$ 個の玉を、区別のつく $4$ つの箱 $\mathrm{A},\mathrm{B},\mathrm{C},\mathrm{D}$ にすべて入れる。空の箱があってもよいが、どの箱にも玉は $5$ 個以下しか入れられない。このとき、箱 $\mathrm{A}$ に入る玉の個数が箱 $\mathrm{B}$ に入る玉の個数より多くなるような入れ方は何通りあるか。

$\mathrm{a},\mathrm{a},\mathrm{a},\mathrm{b},\mathrm{b},\mathrm{b},\mathrm{c},\mathrm{c}$ の $8$ 個の文字をすべて $1$ 列に並べる。同じ文字どうしがどこも隣り合わない並べ方は何通りあるか。

1 個のさいころを 1 回投げ、出た目を $k$ とする。次に、赤玉 3 個と白玉 3 個の合計 6 個の玉が入った袋から、$k$ 個の玉を同時に取り出す。取り出した玉の中に赤玉がちょうど 2 個含まれていたとき、さいころの出た目が偶数である条件付き確率を求めよ。

表と裏が出る確率がそれぞれ $\frac{1}{2}$ の硬貨を $n$ 回投げる。ただし $n$ は正の整数とする。$k=1,2,\dots ,n$ に対して、$k$ 回目に表が出たとき $X_k=1$、裏が出たとき $X_k=2$ と定める。
$$S=X_1+X_2+\cdots +X_n,T=X_1{X}_2\cdots X_n$$
とおくとき、確率変数 $S^{2}T$ の期待値 $E(S^{2}T)$ を $n$ の式で求めよ。

1 個のさいころを $n$ 回投げる。ただし、$n$ は正の整数とする。$n$ 回のうちに少なくとも $1$ 回出た目の種類の数を $X$ とする（たとえば $n=4$ で出た目が順に $2,5,2,6$ のとき $X=3$ である）。確率変数 $X$ の分散 $V(X)$ を $n$ の式で表せ。

袋の中に赤玉が $3$ 個、白玉が $4$ 個入っている。この袋から玉を $1$ 個ずつ取り出す。取り出した玉は袋に戻さない。この操作を $7$ 個の玉をすべて取り出すまで続ける。$k=1,2,\dots ,6$ のうち、$k$ 番目に取り出した玉と $(k+1)$ 番目に取り出した玉の色が異なるような $k$ の個数を $X$ とする。確率変数 $X$ の分散 $V(X)$ を求めよ。

$1,2,3,4,5,6,7$ を 1 列に並べる順列 $({\sigma }_1,{\sigma }_2,\dots ,{\sigma }_7)$ のうち、どの $j$ ($1\le j\le 6$) についても ${\sigma }_{j+1}={\sigma }_j+1$ とならないもの、すなわち「ある整数 $i$ のすぐ右隣に $i+1$ が来る」箇所が 1 つもないものの個数を求めよ。

立方体の 12 本の辺のうち、ちょうど 6 本を赤、残りの 6 本を青で塗る。立方体の回転によって互いに重ね合わせられる塗り方は同じものとみなすとき、異なる塗り方は何通りあるか。ただし、裏返し（鏡映）による同一視は行わない。

長さ $a$ の線分（セグメント）$N$ 個を順につないだ 1 次元の高分子鎖のモデルを考える。各セグメントは $x$ 軸の正の向きか負の向きのどちらかを向き、セグメントの向きによってエネルギーは変わらない（全エネルギーは向きの組によらず一定）。鎖の一端を原点に固定し、他端の $x$ 座標を $X$（$-Na<X<Na$）とする。セグメントは区別でき、$X$ を与えたときに実現する向きの組はすべて等確率（ミクロカノニカル分布）とする。エントロピーを $S(X)=k_B\log W(X)$（$W(X)$ は端の座標が $X$ となる向きの組の数、$k_B$ はボルツマン定数）で定め、$N\gg 1$ および $Na\pm X\gg a$ としてスターリングの公式 $\log n!\approx n\log n-n$ を用い、$X$ を連続変数とみなす。鎖が温度 $T$ にあるとき、他端を座標 $X$（$X>0$）に保つために $x$ 軸の正の向きに加える力の大きさ $f$ は、熱力学の関係式 $f=-T{\left(\frac{\partial S}{\partial X}\right)}_E$ で与えられる（$E$ は内部エネルギー）。$f$ を $N,a,X,T,k_B$ を用いて表せ。

$A=\{1,2,3,4,5\}$ とする。写像 $f:A\to A$ のうち、合成について
$$f\circ f=f\circ f\circ f$$
を満たすものの個数を求めよ。

$A=\{1,2,3,4,5,6,7\}$ とする。$A$ 上の同値関係 $R$ のうち、次の $2$ つの条件をともに満たすものの個数を求めよ。

• $(1)$ どの同値類も $2$ 個以上の元を含む
• $(2)$ $1$ と $2$ は $R$ に関して同値でない（すなわち $(1,2)\notin R$）

$10$ 人のプレイヤー $1,2,\dots ,10$ が円形に並んでおり、プレイヤー $i$ の隣人はプレイヤー $i-1$ と $i+1$ である（添字は $10$ を法として考え、プレイヤー $0$ はプレイヤー $10$、プレイヤー $11$ はプレイヤー $1$ を表す）。各プレイヤー $i$ は同時に $1$ 回だけ、行動 $x_i\in \{0,1\}$ を選ぶ。プレイヤー $i$ の利得は、2 人の隣人のうち自分と異なる行動を選んだ人数とする。すなわち
$$u_i(x_1,\dots ,x_{10})=|x_i-x_{i-1}|+|x_i-x_{i+1}|$$
である。この $10$ 人ゲームの純粋戦略のナッシュ均衡（行動の組 $(x_1,\dots ,x_{10})$）の個数を求めよ。

${\mathbb{F}}_2=\{0,1\}$ を 2 元体とし、$E={\mathbb{F}}_2^4\setminus \{0\}$（15 個のベクトルからなる集合）とする。$E$ 上のマトロイド $M$ を、部分集合 $I\subseteq E$ が ${\mathbb{F}}_2$ 上 1 次独立であるとき、かつそのときに限り独立集合であるものとして定める（$M$ の階数は $4$）。$M^{\ast }$ を $M$ の双対マトロイド、すなわち $M$ の基の補集合 $E\setminus B$ 全体を基の族とするマトロイドとする。

ベクトル $v\in E$ の成分のうち $1$ であるものの個数を $\mathrm{hw}(v)$ と書き、重み $w:E\to \mathbb{Z}$ を
$$w(v)=\{\begin{array}{ll}1& (\mathrm{hw}(v)=2,4)\\ 2& (\mathrm{hw}(v)=1)\\ 3& (\mathrm{hw}(v)=3)\end{array}$$
で定める。$M^{\ast }$ の基 $B^{\ast }$ の重みを $w(B^{\ast })={\sum }_{v\in B^{\ast }}w(v)$ とするとき、$w(B^{\ast })$ が最大となる $M^{\ast }$ の基 $B^{\ast }$ の個数を求めよ。

互いに異なる $8$ 個の数を並べた配列を、次のマージソートで昇順に並べかえる。

• 長さ $1$ の配列はそのまま返す。
• 長さ $2k$（$k$ は正の整数）の配列は、前半 $k$ 個と後半 $k$ 個に分け、それぞれを再帰的にこのマージソートで並べかえたあと、次の「マージ」で $1$ つの昇順の列にまとめる。
• マージ: 昇順に並んだ 2 つの列の先頭どうしを $1$ 回比較し、小さい方を取り出して出力の末尾に加える。これを一方の列が空になるまで繰り返し、空になったら、もう一方の列に残っている数を比較せずにそのまま出力の末尾に加える。

入力の $8$ 個の数の並び方は $8!$ 通りすべてが等確率で現れるものとする。このとき、ソート全体で行われる数どうしの比較回数の期待値を求めよ。

$n$ を正の整数とする。文字列 $s$ からいくつかの文字を取り除き（$0$ 個でもよい）、残りの文字を順序を変えずに並べた文字列を $s$ の部分列という。$2$ つの文字列の両方の部分列であるものを共通部分列といい、共通部分列のうち長さが最大のものを最長共通部分列という。

文字 $\mathrm{a},\mathrm{b},\mathrm{c}$ からなる次の $2$ つの文字列を考える。
$$X=\underset{\mathrm{abc}\text{を}n\text{回}}{\underbrace{\mathrm{abc}\mathrm{abc}\cdots \mathrm{abc}}},Y=\underset{n\text{個}}{\underbrace{\mathrm{c}\cdots \mathrm{c}}}\underset{n\text{個}}{\underbrace{\mathrm{b}\cdots \mathrm{b}}}\underset{n\text{個}}{\underbrace{\mathrm{a}\cdots \mathrm{a}}}$$
（$X$, $Y$ の長さはどちらも $3n$）

$X$ と $Y$ の最長共通部分列は、文字列として何通りあるか。$n$ の式で表せ（異なる位置から取り出しても同じ文字列になるものは $1$ 通りと数える）。

区別のできる $9$ 人のプレイヤー $1,2,\dots ,9$ が、ある共同プロジェクトに「出資する」か「出資しない」かを同時に 1 回だけ選ぶ（クラウドファンディングのような、返金保証のある閾値型の公共財ゲーム）。出資した人数を $k$ とする。

• $k\ge 4$ のときプロジェクトは成立し、全員（出資しなかったプレイヤーも含む）が便益 $10$ を受け取る。このとき出資したプレイヤー $i$ は費用 $c_i$ を支払う。
• $k\le 3$ のときプロジェクトは不成立で、出資金は全額返金される。このとき全員の利得は $0$ である。

すなわちプレイヤー $i$ の利得は、成立したとき出資していれば $10-c_i$、出資していなければ $10$、不成立のときは出資の有無によらず $0$ である。費用は
$$c_1=c_2=c_3=c_4=c_5=3,c_6=c_7=c_8=c_9=12$$
とする。

この $9$ 人の戦略形ゲームにおいて、純粋戦略のナッシュ均衡（$2^9$ 通りの戦略の組のうち、どのプレイヤーも 1 人だけ戦略を変えて利得を真に増やすことができないもの）の個数を求めよ。

頂点集合を $V=\{1,2,3,4,5\}$ とする完全グラフ $K_5$ の辺集合を $E$（$|E|=10$）とする。頂点 $v$ に接続する辺の集合を $\delta (v)$ と書く。$K_5$ の最大マッチング問題の整数計画の線形緩和として、${\mathbb{R}}^E$ の多面体
$$P=\left\{x\in {\mathbb{R}}^E|x_e\ge 0(e\in E),\sum _{e\in \delta (v)}{x}_e\le 1(v\in V)\right\}$$
を考える。$P$ の頂点のうち、整数ベクトルでない（少なくとも 1 つの成分が整数でない）ものの個数を求めよ。

二元体 ${\mathbb{F}}_2=\{0,1\}$ 上で、
$$g(x)=(x^4+x+1)(x^4+x^3+x^2+x+1)$$
を生成多項式とする符号長 $15$ の巡回符号 $C$ を考える。すなわち、$C$ は ${\mathbb{F}}_2[x]$ の次数 $14$ 以下の多項式のうち $g(x)$ で割り切れるもの全体であり、多項式 $c_0+c_{1}x+\cdots +c_{14}{x}^{14}$ を語 $(c_0,c_1,\dots ,c_{14})\in {\mathbb{F}}_2^{15}$ と同一視する（$g(x)$ は $x^{15}-1$ を割り切る）。

$C$ の最小ハミング距離を $d$ とする。また、${\mathbb{F}}_2^{15}$ を $C$ による剰余類（$v+C$ の形の集合）に分けたとき、ハミング重みが $2$ 以下の語を $1$ つも含まない剰余類の個数を $N$ とする。$(d,N)$ をこの順に組で求めよ。

正の整数 $m$ に対し $[m]=\{1,2,\dots ,m\}$ とし、$[0]=\varnothing$ とする。0 以上の整数 $m$ に対し、$[m]$ 上の同値関係の個数を $E(m)$ で表す（$\varnothing$ 上の同値関係は空関係ただ 1 つなので $E(0)=1$ である）。

集合 $S$ の分割とは、$S$ の空でない部分集合からなる集合族 $\mathcal{P}$ であって、$\mathcal{P}$ の相異なる 2 つの元は交わらず、$\mathcal{P}$ の元すべての和集合が $S$ になるものをいう（$\varnothing$ の分割は空集合族ただ 1 つである）。集合 $S$ 上の同値関係と $S$ の分割とは、同値関係にその同値類全体を対応させることで 1 対 1 に対応する。この事実は用いてよい。

任意の 0 以上の整数 $n$ に対して
$$E(n+1)=\sum _{j=0}^n\left(\genfrac{}{}{0ex}{}{n}{j}\right)E(j)$$
が成り立つことを証明せよ。

$n$ を $2$ 以上の整数とし、プレイヤーの集合を $N=\{1,2,\dots ,n\}$ とする。関数 $f:\{0,1,\dots ,n\}\to \mathbb{R}$ は $f(0)=0$ をみたすとし、提携 $S\subseteq N$ の値を $v(S)=f(|S|)$ で定める特性関数形ゲーム $(N,v)$ を考える（$|S|$ は $S$ の要素の個数）。

ベクトル $x=(x_1,\dots ,x_n)\in {\mathbb{R}}^n$ と $S\subseteq N$ に対し $x(S)={\sum }_{i\in S}{x}_i$（$x(\varnothing )=0$）とおく。$(N,v)$ のコアを
$$C(v)=\{x\in {\mathbb{R}}^n\mid x(N)=v(N),\text{and}x(S)\ge v(S)\text{for all}S\subseteq N\}$$
と定め、シャープレイ値 $\phi (v)=({\phi }_1,\dots ,{\phi }_n)$ を
$${\phi }_i=\sum _{S\subseteq N\setminus \{i\}}\frac{|S|!(n-|S|-1)!}{n!}(v(S\cup \{i\})-v(S))(i\in N)$$
で定める。

このとき、コア $C(v)$ が空でないことと、シャープレイ値 $\phi (v)$ が $C(v)$ に属することは同値であることを証明せよ。

$L=\{f\}$ を 1 変数関数記号 $f$ だけからなる一階の言語とし（等号は論理記号として常に真の等号と解釈する）、$L$ の文
$$\sigma :\forall x(f(f(f(x)))=f(x))$$
を考える。正の整数 $n$ に対して $[n]=\{1,2,\dots ,n\}$ とおき、$[n]$ を台集合とする $L$ 構造（$f$ の解釈 $f^{\mathcal{M}}:[n]\to [n]$ によって決まる。解釈が異なる構造は別のものとして数える）のうち、$\sigma$ のモデルであるものの個数を $a_n$ とする。

また、正の整数 $k$ に対し
$$I_k=\sum _{j=0}^{\lfloor k/2\rfloor }\frac{k!}{2^{j}j!(k-2j)!}$$
とおく。すべての正の整数 $n$ について
$$a_n=\sum _{k=1}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)I_k{k}^{n-k}$$
が成り立つことを証明せよ。

1 個のさいころを $n+1$ 回投げる。ただし、$n$ は正の整数とする。$k=1,2,\dots ,n+1$ に対して、$k$ 回目に出た目を $3$ で割った余りを $X_k$ とする。確率変数 $S$ を
$$S=X_1{X}_2+X_2{X}_3+X_3{X}_4+\cdots +X_n{X}_{n+1}=\sum _{k=1}^n{X}_k{X}_{k+1}$$
で定めるとき、$S$ の分散 $V(S)$ を $n$ の式で求めよ。

$+1$ と書かれたカード $13$ 枚と、$-2$ と書かれたカード $6$ 枚の、合計 $19$ 枚のカードがある。同じ数が書かれたカードは区別しない。これらをすべて横 $1$ 列に並べ、左端のカードから順に書かれた数を足していく。左から $1$ 枚目までの和、$2$ 枚目までの和、…、$19$ 枚目までの和がすべて正となる並べ方は何通りあるか。

$1$ 個のさいころを $10$ 回続けて投げる。$k=1,2,\dots ,10$ に対して、$1$ 回目から $k$ 回目までに出た目の和を $S_k$ とする。$10$ 個の数 $S_1,S_2,\dots ,S_{10}$ のうち、$7$ の倍数であるものがちょうど $2$ 個である確率を求めよ。

$m$ は正の整数とする。表と裏が出る確率がそれぞれ $\frac{1}{2}$ の硬貨を $2m$ 回投げ、表が出た回数と裏が出た回数の差の絶対値を $D$ とする。確率変数 $D$ の分散 $V(D)$ を $m$ の式で求めよ。

二元体 ${\mathbb{F}}_2=\{0,1\}$ 上で、次の $4\times 10$ 行列 $H$ を考える。
$$H=\left(\begin{array}{cccccccccc}1& 0& 0& 0& 1& 1& 1& 0& 0& 0\\ 0& 1& 0& 0& 1& 0& 0& 1& 1& 0\\ 0& 0& 1& 0& 0& 1& 0& 1& 0& 1\\ 0& 0& 0& 1& 0& 0& 1& 0& 1& 1\end{array}\right)$$
$H$ の列は、${\mathbb{F}}_2^4$ のベクトルのうちハミング重み（$1$ である成分の個数）が $1$ または $2$ であるもの全部（$10$ 個）を $1$ 回ずつ並べたものである。$H$ を検査行列とする符号長 $10$ の二元線形符号
$$C=\{x\in {\mathbb{F}}_2^{10}:H{x}^T=0\}$$
について、$C$ の最小距離を $d$ とし、$C$ に含まれるハミング重み $k$ の符号語の個数を $A_k$ とする。$d,A_d,A_{d+1}$ をこの順に組で求めよ。

二元体 ${\mathbb{F}}_2=\{0,1\}$ 上で、生成多項式
$$g(x)=(x+1)(x^4+x+1)=x^5+x^4+x^2+1$$
で定まる符号長 $15$ の巡回符号 $C$ を考える。すなわち、$C$ は ${\mathbb{F}}_2[x]$ の次数 $14$ 以下の多項式のうち $g(x)$ で割り切れるもの全体であり、多項式 $c_0+c_{1}x+\cdots +c_{14}{x}^{14}$ を語 $(c_0,c_1,\dots ,c_{14})\in {\mathbb{F}}_2^{15}$ と同一視する。また、$\alpha$ を ${\mathbb{F}}_{16}$ における $x^4+x+1$ の根とする（$\alpha$ の位数は $15$ である）。