順列・円順列・重複順列

ある部活動には $8$ 人の部員がいる。この $8$ 人の中から、部長・副部長・会計を $1$ 人ずつ選ぶ。$1$ 人が $2$ つ以上の役を兼ねることはできないとき、選び方は全部で何通りあるか。

ある委員会には $9$ 人の委員がいる。この $9$ 人の中から、委員長・副委員長・書記を $1$ 人ずつ選ぶ。$1$ 人が $2$ つ以上の役を兼ねることはできないとき、選び方は全部で何通りあるか。

異なる $7$ 冊の本の中から $3$ 冊を選び、本棚に左から $1$ 列に並べる。並べ方は全部で何通りあるか。

A, B, C, D, E の 5 人が円形のテーブルに座る。回転して一致する座り方は同じものとみなすとき、A と B が隣り合う座り方は何通りあるか。

円を中心角が等しい 6 つの扇形に分け、赤・青・黄・緑・白・黒の 6 色をすべて 1 回ずつ使って、各扇形を 1 色で塗る。回転して一致する塗り方は同じものとみなす。赤と青の扇形が隣り合わず、かつ黄と緑の扇形も隣り合わない塗り方は何通りあるか。

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}}$ が集合として異なれば別に数える）。

$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-マルチコリジョン）が起こる」という。

3 個のさいころを同時に投げるとき、出た目の和が 10 になる確率を求めよ。

男子 $3$ 人、女子 $3$ 人、先生 $1$ 人の計 $7$ 人が、円形のテーブルのまわりに等間隔に並んだ $7$ つの席に座る。回転して一致する座り方は同じものとみなす。次の $2$ つの条件をともに満たす座り方は何通りあるか。

(条件1) 先生の両隣は、男子 $1$ 人と女子 $1$ 人である。

(条件2) 女子どうしはどの $2$ 人も隣り合わない。

$1$ から $9$ までの整数が $1$ つずつ書かれた $9$ 枚のカードがある。これらをよくまぜて、縦 $3$ 行・横 $3$ 列に並んだ $9$ つのマスに $1$ 枚ずつ無作為に置く。

$3$ つの行のうち、置かれた $3$ 枚のカードに書かれた数の和が $15$ である行が少なくとも $1$ つある確率を求めよ。

円周上に等間隔に並んだ $9$ か所の位置に、赤・青・黄の $3$ 色の玉を $1$ 個ずつ置く。各色の玉は何個でも使えて、使わない色があってもよい。ただし、隣り合う $2$ か所には異なる色の玉を置く。

回転して一致する置き方は同じものとみなすとき（裏返して一致するものは区別する）、置き方は全部で何通りあるか。

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

$n$ は $2$ 以上の整数とする。$1$ から $n$ までの整数が $1$ つずつ書かれた $n$ 枚のカードを、無作為に横一列に並べる。左から $k$ 番目のカードに書かれた数を $a_k$ $(k=1,2,\dots ,n)$ とし、$1\leqq k\leqq n-1$ を満たす整数 $k$ のうち $a_{k+1}=a_k+1$ となるものの個数を $X$ とする（例えば、$n=5$ で $(a_1,a_2,a_3,a_4,a_5)=(3,4,5,1,2)$ のとき $X=3$ である）。確率変数 $X$ の分散 $V(X)$ を $n$ の式で求めよ。

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

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

$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 つもないものの個数を求めよ。

通常のユークリッド距離による位相を入れた空間 ${\mathbb{R}}^3$ の部分集合
$$X=\{(x,y,z)\in {\mathbb{R}}^3\mid xyz(x^2-y^2)(y^2-z^2)(z^2-x^2)\ne 0\}$$
に相対位相を入れる。$X$ の連結成分の個数を求めよ。

頂点集合を $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 つの成分が整数でない）ものの個数を求めよ。

1 個のさいころを $6$ 回続けて投げる。$6$ 回のうちから異なる $2$ 回を選び、その $2$ 回に出た目の和を $7$ にすることができる確率を求めよ。

円周上に等間隔に $8$ つの位置があり、それぞれの位置に赤・青・黄のいずれかの色の玉を $1$ 個ずつ置く。各色の玉は十分な個数があり、同じ色の玉どうしは区別しない。次の $2$ つの条件をともに満たす置き方は何通りあるか。ただし、回転して一致する置き方は同じものとみなし、裏返して一致するだけのものは異なるものとみなす。

$(1)$ 隣り合う $2$ つの位置には、異なる色の玉を置く。

$(2)$ 赤・青・黄の $3$ 色すべてを少なくとも $1$ 回ずつ使う。

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

$1$ から $7$ までの番号が $1$ つずつ書かれた番号札をつけた $7$ 人が、円形のテーブルのまわりに等間隔に並んだ $7$ つの席に座る。回転して一致する座り方は同じものとみなし、裏返して一致する座り方は異なるものとみなす。

番号の差が $1$ である $2$ 人（$1$ と $2$、$2$ と $3$、$\dots$、$6$ と $7$）がどこでも隣り合わないような座り方は何通りあるか。ただし、$7$ と $1$ の差は $6$ であり、この $2$ 人は隣り合ってもよい。