数理論理学・集合論の問題

以下 $A=[n]$ とし、写像 $g:A\to A$ に対して ${\mathcal{M}}_g$ を $f$ を $g$ と解釈する構造とする。

手順 1（モデルであることの言い換え）. タルスキの真理定義により、${\mathcal{M}}_g\models \sigma$ であることは、すべての $a\in A$ について $g(g(g(a)))=g(a)$、すなわち写像として $g\circ g\circ g=g$ であることと同値である。また $[n]$ 上の $L$ 構造は写像 $g:A\to A$ と一対一に対応する。よって $a_n$ は $g^3=g$ を満たす写像 $g:A\to A$ の個数に等しい。

手順 2（構造定理）. 次の 3 つ組 $(S,\pi ,h)$ を考える。
- $S\subset A$ は空でない部分集合、
- $\pi :S\to S$ は対合（$\pi \circ \pi ={\mathrm{id}}_S$）、
- $h:A\setminus S\to S$ は任意の写像（$S=A$ のときは空写像）。

このような 3 つ組全体を $T$ とし、写像 $\Phi :T\to \{g:A\to A\mid g^3=g\}$ を
$$\Phi (S,\pi ,h)(a)=\{\begin{array}{ll}\pi (a)& (a\in S)\\ h(a)& (a\notin S)\end{array}$$
で定める。$\Phi$ が全単射であることを示す。

(i) $\Phi$ の値が実際に $g^3=g$ を満たすこと。$g=\Phi (S,\pi ,h)$ とおく。$g$ の値はすべて $S$ に入る（$\pi$ も $h$ も値は $S$ にある）。$a\in S$ なら $g(a)=\pi (a)\in S$ なので $g^2(a)={\pi }^2(a)=a$、$g^3(a)=g(a)$。$a\notin S$ なら $g(a)=h(a)\in S$ なので $g^2(a)=\pi (h(a))\in S$、$g^3(a)={\pi }^2(h(a))=h(a)=g(a)$。場合はこの 2 つで尽きるので $g^3=g$。

(ii) $\Phi (S,\pi ,h)$ の像は $S$ であること。(i) で見たとおり像は $S$ に含まれる。逆に $s\in S$ なら $\pi (s)\in S$ で $s=\pi (\pi (s))=g(\pi (s))$ なので $s$ は像に入る。よって $g(A)=S$。

(iii) 単射性。$\Phi (S,\pi ,h)=\Phi (S^{\prime },{\pi }^{\prime },h^{\prime })=g$ とすると、(ii) より $S=g(A)=S^{\prime }$。すると $\pi =g{|}_S={\pi }^{\prime }$、$h=g{|}_{A\setminus S}=h^{\prime }$ となる。

(iv) 全射性。$g^3=g$ とし、$S=g(A)$ とおく。$A\ne \varnothing$ なので $S\ne \varnothing$。$s\in S$ を $s=g(a)$ と書くと $g(g(s))=g^3(a)=g(a)=s$ であり、また $g(s)\in g(A)=S$。よって $\pi =g{|}_S$ は $S$ から $S$ への写像で $\pi \circ \pi ={\mathrm{id}}_S$ を満たす対合である。$h=g{|}_{A\setminus S}$ の値は $g(A)=S$ に入る。この $(S,\pi ,h)\in T$ について、$\Phi (S,\pi ,h)$ は $S$ 上で $\pi =g{|}_S$、$A\setminus S$ 上で $h=g{|}_{A\setminus S}$ に一致するので $\Phi (S,\pi ,h)=g$ である。

以上より $\Phi$ は全単射で、$a_n=|T|$ である。

手順 3（$k$ 元集合上の対合の個数は $I_k$）. $k\ge 1$ とし、$|S|=k$ の集合上の対合 $\pi$ に対し、$\{\{s,\pi (s)\}:s\in S,\pi (s)\ne s\}$ は $S$ の互いに素な 2 元部分集合の族である（$\{s,\pi (s)\}$ と $\{t,\pi (t)\}$ が共通元 $u$ をもてば、${\pi }^2=\mathrm{id}$ より $u$ と $\pi (u)$ でこの 2 つの集合はともに $\{u,\pi (u)\}$ に等しい）。逆に互いに素な 2 元部分集合の族 $\mathcal{P}$ が与えられれば、各対の 2 元を入れ替え、どの対にも入らない元を固定する写像は対合で、この 2 つの対応は互いに逆である。したがって対合の個数は、$S$ の中の互いに素な $j$ 個の対の族の個数を $j=0,1,\dots ,\lfloor k/2\rfloor$ について足したものである。$j$ 個の対の族は、対に使う $2j$ 元を $\left(\genfrac{}{}{0ex}{}{k}{2j}\right)$ 通りに選び、その $2j$ 元を $j$ 個の対に分ける。後者は、$2j$ 元の並べ方 $(2j)!$ 通りを前から 2 つずつ区切って対を作ると、各対の中の順序 $2^j$ 通りと対の並べ方 $j!$ 通りが同じ族を与えるので $\frac{(2j)!}{2^{j}j!}$ 通りである。よって
$$\#\{\text{対合}\}=\sum _{j=0}^{\lfloor k/2\rfloor }\left(\genfrac{}{}{0ex}{}{k}{2j}\right)\frac{(2j)!}{2^{j}j!}=\sum _{j=0}^{\lfloor k/2\rfloor }\frac{k!}{2^{j}j!(k-2j)!}=I_k.$$

手順 4（数え上げ）. $T$ の元を $|S|=k$（$1\le k\le n$）で分類する。$S$ の選び方は $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ 通り、$S$ 上の対合 $\pi$ は手順 3 より $I_k$ 通り、写像 $h:A\setminus S\to S$ は $n-k$ 個の元の各々の行き先を $k$ 通りずつ選ぶので $k^{n-k}$ 通り（$k=n$ のときは空写像 1 通りで、$n^0=1$ に一致する）。これらの選択は独立なので
$$|T|=\sum _{k=1}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)I_k{k}^{n-k}.$$

手順 1, 2 と合わせて、すべての正の整数 $n$ について
$$a_n=\sum _{k=1}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)I_k{k}^{n-k}$$
が成り立つ。$■$