　正の整数 $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}$ である．
公式解説
https://onlinemathcontest.com/contests/omc229/editorial/11962
　$S=\\{1,2,3,4,5\\}$ とおき，$S$ の部分集合全体の集合を $T$ とします．写像 $f:S\to T$ であって，以下をみたすものの個数を求めてください．
- 任意の $a,b\in S$ に対し，$a\in f(b)\iff f(a)\subset f(b)$ である．
- 任意の $a,b\in S$ に対し，ある $c\in S$ が存在し，$f(a)\cup f(b)=f(c)$ をみたす．