この問題は、利用者からの報告を受けて確認中です。答えや解説に誤りがあるかもしれません。

集合と位相の問題

難易度 2教科書の演習問題レベル大学数学集合と位相

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

この問題で使うもの

同値関係と集合の分割（説明と入口の問題）
写像・単射の個数と集合の濃度（説明と入口の問題）
組合せ（説明と入口の問題）

この問題を解けるようになるまで（8 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

同値関係を、 $A$ の分割（同値類への分け方）として扱い、分割ごとに条件を満たす $f$ の個数を数えて足し合わせましょう。

ヒント 2

条件は「各同値類 $B_{i}$ の像 $f (B_{i})$ が、ある 1 つの同値類に含まれる」ことと同値です。このことから、分割を固定したときの $f$ の個数は $\prod_{i} \sum_{j} ∣ B_{j} ∣^{∣ B_{i} ∣}$ になります。

ヒント 3

$5$ の分割の型は ${5}, {4, 1}, {3, 2}, {3, 1, 1}, {2, 2, 1}, {2, 1, 1, 1}, {1^{5}}$ の $7$ つで、それぞれの型の分割は $1, 5, 10, 10, 15, 10, 1$ 個あります。たとえば型 ${4, 1}$ では $f$ の個数が $(4^{4} + 1) (4 + 1) = 1285$ です。

答えと解説

答えを見る

39300

結果を記録する（このブラウザにだけ保存されます）:

解説を読む

方針. 同値関係 $R$ と $A$ の分割（同値類全体）は 1 対 1 に対応するので、分割ごとに条件を満たす $f$ の個数を数えて合計する。

条件の言いかえ. $R$ の同値類を $B_{1}, \dots, B_{k}$ とし、 $b_{i} = ∣ B_{i} ∣$ とおく。

条件が成り立つとする。 $B_{i}$ の元どうしはすべて $R$ で関係しているので、それらの像もすべて互いに $R$ で関係する。よって $f (B_{i})$ はある 1 つの同値類 $B_{j}$ に含まれる。
逆に、各 $B_{i}$ について $f (B_{i})$ がある 1 つの同値類に含まれるとする。 $x R y$ なら $x, y$ は同じ $B_{i}$ に属するので、 $f (x), f (y)$ は同じ同値類に属し、 $f (x) R f (y)$ となる。

したがって、条件は「各同値類 $B_{i}$ の像が 1 つの同値類に含まれる」ことと同値である。

分割を固定したときの $f$ の個数. $B_{i}$ から $B_{j}$ への写像は $b_{j}^{b_{i}}$ 個ある。 $B_{i} \neq = \emptyset$ で同値類どうしは交わらないので、 $j$ ごとの場合は重ならない。よって $B_{i}$ 上での $f$ の決め方は $\sum_{j = 1}^{k} b_{j}^{b_{i}}$ 通りである。各同値類での決め方は互いに独立なので、
$N (R) = i = 1 \prod k (j = 1 \sum k b_{j}^{b_{i}})$
となる。

分割の型ごとの計算. $5$ の分割の型それぞれについて、その型の分割の個数と $N (R)$ を求める。

型 ${5}$ ：分割は $1$ 個。 $N = 5^{5} = 3125$ 。合計 $3125$ 。
型 ${4, 1}$ ：分割は $(1 5) = 5$ 個。 $N = (4^{4} + 1^{4}) (4 + 1) = 257 \cdot 5 = 1285$ 。合計 $6425$ 。
型 ${3, 2}$ ：分割は $(2 5) = 10$ 個。 $N = (3^{3} + 2^{3}) (3^{2} + 2^{2}) = 35 \cdot 13 = 455$ 。合計 $4550$ 。
型 ${3, 1, 1}$ ：分割は $(3 5) = 10$ 個。 $N = (27 + 1 + 1) \cdot (3 + 1 + 1)^{2} = 29 \cdot 25 = 725$ 。合計 $7250$ 。
型 ${2, 2, 1}$ ：分割は $5 \cdot 3 = 15$ 個（ $1$ 元の類の選び方が $5$ 通り、残り $4$ 元を $2 + 2$ に分ける方法が $3$ 通り）。 $N = (4 + 4 + 1)^{2} \cdot (2 + 2 + 1) = 81 \cdot 5 = 405$ 。合計 $6075$ 。
型 ${2, 1, 1, 1}$ ：分割は $(2 5) = 10$ 個。 $N = (4 + 1 + 1 + 1) \cdot (2 + 1 + 1 + 1)^{3} = 7 \cdot 125 = 875$ 。合計 $8750$ 。
型 ${1, 1, 1, 1, 1}$ ：分割は $1$ 個。 $N = 5^{5} = 3125$ （どんな $f$ でも条件を満たす）。合計 $3125$ 。

分割の個数の合計は $1 + 5 + 10 + 10 + 15 + 10 + 1 = 52$ で、ベル数 $B_{5} = 52$ と一致する。

合計.
$3125 + 6425 + 4550 + 7250 + 6075 + 8750 + 3125 = 39300.$

別解

条件は、 $f$ が $R$ の各同値類をある同値類の中へ写すことと同じである。したがって、 $A$ の分割（同値関係と 1 対 1 に対応する）ごとに、条件を満たす $f$ の個数を数えて足せばよい。

分割のブロックを $B_{1}, \dots, B_{k}$ 、その大きさを $b_{1}, \dots, b_{k}$ とする。ブロック $B_{i}$ の行き先のブロック $B_{j}$ を選び、 $B_{i}$ の各元を $B_{j}$ の任意の元に写すと $b_{j}^{b_{i}}$ 通りある。よって $f$ の個数は $\prod_{i} (\sum_{j} b_{j}^{b_{i}})$ である。

分割の型ごとに計算する。
- ${5}$ （分割 1 個）: $5^{5} = 3125$ 。合計 3125。
- ${4, 1}$ （5 個）: $(4^{4} + 1) (1 + 4) = 257 \cdot 5 = 1285$ 。合計 $5 \cdot 1285 = 6425$ 。
- ${3, 2}$ （10 個）: $(27 + 8) (9 + 4) = 35 \cdot 13 = 455$ 。合計 4550。
- ${3, 1, 1}$ （10 個）: $(27 + 1 + 1) \cdot 5 \cdot 5 = 725$ 。合計 7250。
- ${2, 2, 1}$ （15 個）: $(4 + 4 + 1)^{2} \cdot 5 = 81 \cdot 5 = 405$ 。合計 6075。
- ${2, 1, 1, 1}$ （10 個）: $(4 + 1 + 1 + 1) \cdot 5^{3} = 7 \cdot 125 = 875$ 。合計 8750。
- ${1, 1, 1, 1, 1}$ （1 個）: $5^{5} = 3125$ 。合計 3125。

検算として分割の個数は $1 + 5 + 10 + 10 + 15 + 10 + 1 = 52$ で、ベル数 $B_{5} = 52$ と一致する。

総和は $3125 + 6425 + 4550 + 7250 + 6075 + 8750 + 3125 = 39300$ 。

集合と位相の問題

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題