陥没地帯 (274) - ノリの悪い日記

年度はわからないが, 名古屋市大の問題らしい. 長い問題文だが, $m$ 個の要素をもつ集合 $A$ から $n$ 個の要素をもつ集合 $B$ への全射写像の個数を求める問題である. 全射なのだから $m \geq n$ という条件がある. ディユドネが, 「現代数学では, 写像を $1$ つのモノと考えることが基本的で, $1$ つの点や $1$ つの数と同格に扱わねばならない. そして, 写像 $\mathrm{F}$ と値 $\mathrm{F}(x)$ とを明確に区別することが大事である」と書いていたことを思い出したが, 問題文の「その送受信はいっせいに行われる」という記述は, このことを断っておきたかったんだと思う.

【問】
$m$ 箇所の送信施設を持つ $A$ 国から, $n$ 箇所の受信施設を持つ $B$ 国へ信号を送る. $A$ 国の各施設は $B$ 国の施設の中のただ $1$ 箇所に必ず信号を送るものとし, その送受信はいっせいに行われる. いま $m \geq n$ とし, $B$ 国のどの受信施設も $A$ 国のどこかの送信施設からの信号を少なくとも $1$ つは受信する場合を考える. このような送信パターンの数を $f(m,n)$ と表す. 以下で $m$ , $n$ を変化させて考えるとき, 次の問いに答えよ.

$(1)$ $n = 3$ のとき $f(m, 3)$ を $m$ を用いて表せ. ただし, $m \geq 3$ とする.
$(2)$ $f(m+1,n)$ を $f(m,n)$ および $f(m,n-1)$ を用いて表せ. ただし $n \geq 2$ とする.
$(3)$ $f(m+1,m)$ を $m$ を用いて表せ.

【解】
$(1)$ これは, すでに記事 $(272)$ の問 $(3)$ で扱った問題である. 集合 $A$ から集合 $B$ への写像全体の集合を $\mathrm{Map}(A,B)$ と書いたりする. $\mathrm{Map}(A,B)$ の要素の個数は, $n^m$ である. いまは, $n =3$ だから, $3^n$ である. $B$ の要素を $\{1,2,3\}$ と書けば, 全射写像の個数は, $3^n$ から, $1$ または $2$ または $3$ に値を持たない写像の個数を引けば求めることができ, これを重複を考慮して数えるには, 集合の包除原理を使えばよい.

$f(m, 3) = 3^m - 3\cdot 2^m +3$

$(2)$ これは, 直前の記事の奈良女子大の入試問題で証明した以下のスターリング数の漸化式を使うのが楽である.

$S(m+1, n) = S(m, n-1) + nS(m, n)$

全射写像の個数とスターリング数は,

$f(m, n) = n! S(m, n)$

の関係がある.

証明: 以下, $B$ を $\{1,2, \cdots, n\}$ と表わす.

$A$ から $B$ への任意の全射写像を $\mathrm{F}$ とすると, 逆像 $A_1= \mathrm{F}^{-1}(\{1\})$ , $A_2=\mathrm{F}^{-1}(\{2\})$ , $\cdots$ , $A_n=\mathrm{F}^{-1}(\{n\})$ は, いずれも空集合ではなく, $\Omega = \{ A_1, A_2, \cdots, A_n\}$ は, $A$ を $n$ 個の異なる類に分ける類別となっている. この全射写像 $\mathrm{F}$ が自然に誘導した類別 $\Omega$ は (集合の準同型定理により) 集合 $B$ と同型になる *1. つまり, $\mathrm{F} = \overline{\mathrm{F}}\circ \pi$ をみたす, 類別 $\Omega$ から $B$ への全単射写像 $\overline{\mathrm{F}}$ がただ $1$ つ定まる (ここで, $\pi$ は $A$ から類別 $\Omega$ への自然な射影 *2を表わす).

逆に $A$ を $n$ 個の類に分ける任意の類別, $\Omega = \{A_1, A_2, \cdots, A_n\}$ がひとつあったとする. ここで, $B = \{1,2, \cdots, n\}$ の要素を全部使った重複のない順列を $1'2' \cdots n'$ とする. $A_1$ に含まれる任意の要素を $A_1$ に (自然) 射影し, さらに $A_1$ から $1$ を経て $1'$ に対応させる. 次に $A_2$ に含まれる任意の要素を $A_2$ に射影し, さらに $A_2$ から $2$ を経て $2'$ に対応させる $\cdots$ . 以下 $A_n$ の任意の要素までこれを続けることで, $A$ から $B$ への写像 $\mathrm{F}$ を $\mathrm{F} = \overline{\mathrm{F}}\circ \pi$ として定める ( $\pi$ は自然な射影, $\overline{\mathrm{F}}$ は $A_i$ を $i'$ に対応させる任意の全単射写像). すると $\pi$ は (どの類も空集合でないので) 全射, $\overline{\mathrm{F}}$ は全単射であることから全射であり, $2$ つの写像の合成により定まる $\mathrm{F}$ は全射である.

また, $B$ の要素の順列の各配置に対応して, 異なる全単射写像 $\overline{\mathrm{F}}$ がそれぞれひとつ得られることから, 類別 $\Omega$ ひとつにつき, $n!$ 個の異なる全射写像 $\mathrm{F}$ があることがわかる. よって, 数え上げの積の法則から, $f(m, n) = n! S(m, n)$ である.
//

したがって, 最初のスターリング数の漸化式に $n!$ をかけて

$n!S(m+1, n) \\ \quad = n! S(m, n-1) + n\cdot n!S(m, n)$

これから,

$\begin{eqnarray} f(m+1, n) &=& nf(m, n-1) + nf(m, n)\\ &=& n\{f(m, n-1) + f(m, n)\} \end{eqnarray}$

を得る.

$(3)$ この問も, スターリング数の漸化式を使う方が簡単だろう.

$S(m+1, n) = S(m, n-1) + nS(m, n)$

で, $n =m$ として,

$S(m+1, m) = S(m, m-1) + mS(m, m)$

だが, 明らかに $S(m, m) = 1$ なので,

$S(m+1, m) = S(m, m-1) + m$

である. $x_m = S(m+1, m)$ として,

$x_{m} = x_{m-1} + m$

の階差数列を解けばよい. ここで, $x_1=S(2,1) =1$ である. すると,

$\begin{eqnarray} x_m &=& 1 +2 + \cdots + m\\ &=& \frac{m(m+1)}{2} \end{eqnarray}$

であり,

$\displaystyle{S(m+1, m) = \frac{m(m+1)}{2}}$

これから,

$\begin{eqnarray} f(m+1, m) &=& m!\cdot \frac{m(m+1)}{2}\\ &=& \frac{m}{2}(m+1)! \end{eqnarray}$

となる.//

*1:全単射を通じて, $\Omega$ と $B$ は同一視できるという普遍性の観点から, 「同型を除いて一意的である (unique upto isomorphism)」という, 最初に出くわすと頭の中が真っ白になる言い方もある.

*2:考えている集合が類別されているとき、その集合の各要素をそれが属する類へと送る写像のことをこういう. 商写像, 標準射影, 自然な全射などともいうが, そのニュアンスの違いはよくわからない. 尚, 「標準」と訳されているのは, 統計力学や解析力学で「正凖」と訳されている “canonical” のことで, まさに神がかった言葉づかいである.