ベルナンバー続き

id:Hie:20060219で同値関係の総数のお話を書きました．答えも書いたのですが，なんでそうなんねん！って声が聞こえてきたので，一応．

$R$ を有限集合 $X$ 上の同値関係とし，その商集合を $X/R$ とするとしましょう．このとき $f:X\rightarrow X/R$ を考えます．

同値関係をとると，その同値類は直和分割の形になっています*1．そこで， $X$ の要素を同値類に飛ばす写像 $f$ が全射(surjection)になっていると考えます．何故全射かというと，やりたいことは $X$ の要素を同値類に振り分けたいわけるということなのだから，すべての同値類に対して，写像 $f$ により振り分けられてくる $X$ 上の要素が存在しないとおかしいから．
とまぁ，ここで， $F(n,k) = |\{f | f:X\rightarrow X/R \quad \wedge \quad f:\quad \mbox{surjection}\}|$ (ただし， $n=|X|, k=|X/R|$ )としておきましょう．

ところで，全射の総数を考えた場合，どの同値類に振り分けられたか，ということも勘定されます．ちょっとわかりにくいですね．たとえばある写像のパターンにより， $X$ 上の $x_1,x_2,x_3$ が同じ同値類 $y$ に飛ばされるとしましょう．次のパターンでは， $x_1,x_2,x_3$ が先ほどとは違うけれども，やっぱり同値類 $z$ に飛ばされたとしましょう．ただ全射の総数というと，前者と後者はキッチリとカウントされてしまうのです．ところがどっこい，今回の問題では，同じグループ(同値類)になってくれれば，それだけで1パターンこっきり．要するに順序(?)はないわけです．というわけでして，写像 $f$ によって飛ばされる先のグループ(同値類)の数が $k$ 個なのだとしたら，同値関係のパターンは
$\displaystyle{\frac{F(n,k)}{k!}}$ ．
$k!$ は順序はどうでもいいからつきました．

で， $k$ は1から $n$ までとりうるわけで，その総和をとると，(全射の総数 $F(n,k)$ の一般式を知っていれば)
$\displaystyle{\sum_{k=1}^n~\frac{F(n,k)}{k!}}\qquad,\qquad\qquad~\displaystyle{F(n,~k)~=~\sum_{i=1}^k~(-1)^{k-i}~{k~\choose~i}i^n}$
と書けるとわかるわけですね．

お絵かきなしで説明すると難しいな〜．

*1:つまり， $X/R=$ 同値類の集合となっていて，同値類すべての積集合は空，かつ和集合は $X$ そのもの．