OMC229(C)

　正の整数 $n$ に対し $S_n=\{1,\ldots,n\}$とおき，$S_n$の部分集合全体を $T_n$ とする．写像 $f:S_n\to T_n$ であって，以下を満たすものの個数を $a_n$ とする．$a_n$ は $|S_n|$ のみに依存することに注意せよ．

• $a,b\in S_n$ に対し，$a\in f(b)\iff f(a)\subset f(b)$
• $a,b\in S_n$ に対しある $c\in S_n$ が存在し，$f(a)\cup f(b)=f(c)$

　任意の $a\in S_n$ に対し $f(a)\subset f(a)$ より $a\in f(a)$ ．これと，$2$ つめの条件を繰り返し使うことで，ある $m\in S_n$ が存在し，

$$S_n=\{1,\ldots,n\}\subset \bigcup_{k\in S_n} f(k)=f(m)$$

すなわち $f(m)=S_n$ となる $m\in S_n$ が存在することがわかる．すなわち次の集合$M$は空集合でない．

$$M=\{a\in S_n\ |\ f(a)=S_n\}$$

$M$ の元の個数を $k\ (1\leq k\leq n)$ とする．任意の $m\in M$ および $a\notin M$ に対し，

$$f(m)=S_n\not\subset f(a)$$

が成り立つので，$2$ つ目の条件より，$m\notin f(a)$ となる．よって，任意の $a\in S_n\setminus M$ に対し $f(a)\subset S_n\setminus M$ である．よって，$f$ を $S_n\setminus M$ に制限し， $S_n\setminus M$ を $S_{n-k}$ と同一視することで，問題文の $2$ 条件を満たす $f:S_{n-k}\to T_{n-k}$ が得られる．逆に $f:S_{n-k}\to T_{n-k}$ が与えられたとき，$S_{n-k}$ に $k$ 個の元を付け加えたものを $S_n$ とみなし，付け加えた元に対する $f$ の値を $S_n$ とすることで，上記の $2$ 条件を満たす $f:S_n\to T_n$ が得られる．$M$ の元の選び方は ${}_n\mathrm{C}_{k}$ 通りであるから，$a_0=1$ と定義することで，漸化式

$$a_{n}=\sum_{k=1}^n {}_{n}\mathrm{C}{}_k a_{n-k}=\sum_{k=0}^{n-1} {}_{n}\mathrm{C}{}_k a{}_k$$

が得られる．これを用いると，

$$a_0=1, ~ a_1=1, ~ a_2=3, ~ a_3=13, ~ a_4=75, ~ a_5=541$$

となるので，特に解答すべき値は $\bold{541}$ である．