電気通信大学 情報理工学研究科 情報・ネットワーク工学専攻 2021年8月実施 選択問題 離散数学とオートマトン

标签：

• University-of-Electro-Communications
• Cardinality
• Combinatorics
• Binary-Relations

Author

祭音Myyura (co-authored with GPT 5.6 SOL)

Description

問1

$$A=\{a,b,c,d,e,f\},\qquad B=\{1,2,3,4,5,6\},\qquad C=\{\alpha,\beta\}$$

とし、写像の集合

$$F=\{f\mid f:A\to B\},\qquad G=\{g\mid g:B\to C\}$$

を考える。

1. $|F|,|G|$ を求めよ。
2. $F,G$ に含まれる全射の個数を求めよ。
3. $F$ に含まれる全単射の個数を求めよ。

問2

$A$ を $n$ 元集合とする。

1. $A$ 上の反射的関係の個数を求めよ。
2. 反射的かつ対称的な関係の個数を求めよ。
3. 反対称的な関係の個数を求めよ。
4. $A$ の分割 $P$ に対して
   $$R=\bigcup_{Y\in P}Y\times Y$$
   と定めるとき、$R$ が同値関係であることを示せ。

题目描述

计算三个有限集合之间的映射、满射和双射数量；再计算有限集上满足反射、对称或反对称条件的二元关系数量，并证明由集合分割诱导的关系是等价关系。

Kai

問1

(1)

各定義域要素の像を独立に選べるので

$$\boxed{|F|=6^6=46656,\qquad |G|=2^6=64}.$$

(2)

$A,B$ はともに 6 元なので、$F$ の全射は全単射である。したがって

$$\boxed{6!=720}.$$

$G$ では定値写像 2 個だけが全射でないので

$$\boxed{2^6-2=62}.$$

(3)

$$\boxed{6!=720}.$$

問2

(1)

対角成分 $n$ 個は必ず含み、それ以外の $n^2-n$ 個は自由に選べる。よって

$$\boxed{2^{n^2-n}}.$$

(2)

対角成分は必ず含む。相異なる二元の非順序対ごとに、両方向をともに含むか、ともに含まないかの 2 通りなので

$$\boxed{2^{\binom n2}=2^{n(n-1)/2}}.$$

(3)

対角成分は各々自由で $2^n$ 通りである。相異なる二元の非順序対 $\{x,y\}$ ごとに、どちらも含まない、$(x,y)$ だけを含む、$(y,x)$ だけを含む、の 3 通りである。したがって

$$\boxed{2^n3^{\binom n2}=2^n3^{n(n-1)/2}}.$$

(4)

任意の $x\in A$ は分割のある要素 $Y\in P$ に属するので $(x,x)\in Y\times Y\subseteq R$ であり、$R$ は反射的である。

$(x,y)\in R$ なら、ある $Y\in P$ について $x,y\in Y$ である。よって $(y,x)\in Y\times Y\subseteq R$ であり、対称的である。

$(x,y),(y,z)\in R$ とする。$x,y$ を含む分割要素と $y,z$ を含む分割要素は $y$ を共有するため同一である。したがって $(x,z)\in R$ であり、推移的である。

以上より

$$\boxed{R\text{ は同値関係である}}.$$