書記が数学やるだけ#700 全射の個数とスターリング数・ベル数

組み合わせ論における数え方として，新たに全射の個数を考えていく。

問題

原題は長いので途中でカットした。

説明

有限集合の間の写像の数え上げ問題を，写像の条件と同値関係から以下の12個に分類することができる。

前回扱った重複組み合わせもその一つである：

全射の個数は「n 個の区別する玉をk個の区別する箱（各箱1つ以上ある）に入れる場合の数」に相当する。これが求められると，箱の区別を無くして第2種スターリング数，さらに各箱1つ以上という条件を無くしてベル数が求められる。

全射の個数を証明する上で，包除原理が鍵となる：

解答

まずは簡単な数字から，実際に数えてみる。

r=3となると3つの和集合を求める必要がある，ここで包除原理を用いることになる。原題ではr=4もあったがこれはかなり手強い。

ここではr=kの場合を考えることにする，これはまさしく全射の個数である。

全射の個数を用いて，第2種スターリング数とベル数を計算する。

ベル数に関して，以下の漸化式が知られている。

本記事のもくじはこちら：