大阪大学 情報科学研究科 情報工学 2025年8月実施 離散構造

标签：

• 大阪大学
• 偏序集与链
• 计数

Author

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

Description

$I(n)=\{1,2,\ldots,n\}$ とし、有限集合 $S$ のべき集合を $2^S$、要素数を $|S|$ とする。有限半順序集合において、任意の二元が比較可能な部分集合を鎖、任意の相異なる二元が比較不能な部分集合を反鎖とする。

(1)

包含関係で順序付けた次の集合族を考える。

$$\begin{aligned} \mathcal F=\{& \{1,2\},\{2,3\},\{1,2,3\},\{1,2,4\},\{1,2,5\},\\ &\{1,2,5,6\},\{1,2,5,7\},\{1,2,3,4,5,6,7\}\}. \end{aligned}$$

• (1-1) $(\mathcal F,\subseteq)$ の極大元と極小元をすべて列挙せよ。
• (1-2) サイズ4の鎖を一つ示せ。
• (1-3) サイズが最大の反鎖を一つ示せ。

(2)

有限半順序集合の鎖 $X$ について、$X\cup\{s\}$ も鎖となる $s\notin X$ が存在しないとき、$X$ を極大鎖とする。

• (2-1) $(2^{I(4)},\subseteq)$ の極大鎖を一つ示せ。

• (2-2) $(2^{I(n)},\subseteq)$ の鎖を

  $$C_1\subset C_2\subset\cdots\subset C_{|C|}$$

  とする。$C$ が極大鎖であるための必要十分条件が次の三条件であることを示せ。

  $$|C_1|=0,\qquad |C_{|C|}|=n,\qquad |C_{i+1}|=|C_i|+1\quad(1\le i<|C|).$$

• (2-3) $(2^{I(n)},\subseteq)$ の相異なる極大鎖の数を求めよ。

• (2-4) $0\le k\le n$ とする。$|C'|=k$ である固定した $C'\subseteq I(n)$ を含む極大鎖の数を求めよ。

题目描述

本题从具体集合族中的极大元、极小元、链和反链出发，要求证明 Boolean lattice 的极大链恰好逐次增加一个元素，并进一步通过元素加入顺序计算极大链总数及经过固定集合的极大链数。

Kai

(1)

(1-1)

$$\boxed{\text{極大元： }\{1,2,3,4,5,6,7\}},$$

$$\boxed{\text{極小元： }\{1,2\},\ \{2,3\}}.$$

(1-2)

例えば

$$\boxed{ \{1,2\} \subset\{1,2,5\} \subset\{1,2,5,6\} \subset\{1,2,3,4,5,6,7\} }.$$

(1-3)

例えば

$$\boxed{ \bigl\{ \{2,3\},\{1,2,4\},\{1,2,5,6\},\{1,2,5,7\} \bigr\} }$$

はサイズ4の反鎖である。

さらに $\mathcal F$ は次の4本の鎖に分割できる。

$$\begin{aligned} &\{1,2\}\subset\{1,2,5\}\subset\{1,2,5,6\} \subset\{1,2,3,4,5,6,7\},\\ &\{2,3\}\subset\{1,2,3\},\\ &\{1,2,4\},\\ &\{1,2,5,7\}. \end{aligned}$$

反鎖は各鎖から高々一元しか取れないため、そのサイズは高々4であり、上の反鎖は最大である。

(2)

(2-1)

例えば

$$\boxed{ \varnothing \subset\{1\} \subset\{1,2\} \subset\{1,2,3\} \subset\{1,2,3,4\} }.$$

(2-2)

必要性を示す。$C$ が極大鎖であるとする。

• $C_1\ne\varnothing$ なら $\varnothing$ を追加できるので、$|C_1|=0$。

• $C_{|C|}\ne I(n)$ なら $I(n)$ を追加できるので、$|C_{|C|}|=n$。

• $|C_{i+1}|\ge|C_i|+2$ なら、$x\in C_{i+1}\setminus C_i$ を一つ取り

  $$C_i\subset C_i\cup\{x\}\subset C_{i+1}$$

  として鎖へ追加できる。よって $|C_{i+1}|=|C_i|+1$。

次に十分性を示す。三条件が成立すれば、$C$ はサイズ $0,1,\ldots,n$ の集合を一つずつ含む。$D\notin C$ を追加できると仮定し、$|D|=k$ とする。$D$ は同じサイズを持つ $C_{k+1}$ と比較可能でなければならない。同じ有限サイズの集合の間で包含関係が成立すれば等しいため

$$D=C_{k+1},$$

となり $D\notin C$ に反する。したがって $C$ は極大鎖である。

(2-3)

極大鎖は、$\varnothing$ から始めて $I(n)$ の元を一つずつ追加する順序と一対一に対応する。この順序は $I(n)$ の順列なので

$$\boxed{n!}.$$

(2-4)

$C'$ に属する $k$ 元は最初の $k$ 回で追加され、その順序は $k!$ 通りである。残りの $n-k$ 元の順序は $(n-k)!$ 通りである。よって

$$\boxed{k!(n-k)!}.$$