九州大学 1993年度 前期日程 第2次学力試験理系数学 第3問

(1) $n$ 個の数字を $n-1$ 個の空でない部分に分けるには，ちょうど1つの部分だけが2個の数字を含み，残りの $n-2$ 個の部分は1個ずつでなければならない。したがって，2個組にする数字を選べば分割は一意に決まる。よって $$S_n(n-1)={}_n{\mathrm{C}}_2$$ である。

(2) $n$ 個の数字を $n-2$ 個の空でない部分に分けるには，$n$ 個の単独部分から部分の個数を2だけ減らす必要がある。可能性は次の2通りである。

1つ目は，3個の数字が同じ部分に入る場合である。この場合は3個を選べばよいので ${}_n{\mathrm{C}}_3$ 通りである。

2つ目は，2個組が2つできる場合である。この場合は，まず4個の数字を選び，その4個を2組に分ける。4個を2組に分ける方法は $${\displaystyle \frac{{}_4{\mathrm{C}}_2}{2}}=3$$ 通りであるから，$3{}_n{\mathrm{C}}_4$ 通りである。

以上より $$S_n(n-2)={}_n{\mathrm{C}}_3+3{}_n{\mathrm{C}}_4$$ である。

(3)
2つの部分を一時的に区別して，各数字をどちらか一方に入れると考えると，割り当て方は $2^n$ 通りある。このうち片方が空になる割り当てが2通りあるので，両方が空でない割り当ては $2^n-2$ 通りである。

ただし，本問では2つの部分の名前を区別しない。同じ分割は，2つの部分の入れ替えにより2回数えられている。したがって $$S_n(2)={\displaystyle \frac{2^n-2}{2}}=2^{n-1}-1$$ である。

(4) $1,2,\dots ,n+1$ を $k$ 個の空でない部分に分けることを考える。

まず，$n+1$ が単独で1つの部分を作る場合がある。このとき残りの $1,2,\dots ,n$ は $k-1$ 個の空でない部分に分かれるので，$S_n(k-1)$ 通りである。

次に，$n+1$ が単独でない場合を考える。先に $1,2,\dots ,n$ を $k$ 個の空でない部分に分け，その後で $n+1$ をその $k$ 個の部分のどれか1つに入れればよい。したがって $k{S}_n(k)$ 通りである。

この2つの場合は重ならないから，$$S_{n+1}(k)=S_n(k-1)+k{S}_n(k)$$ である。

部分に一時的に番号を付け，「番号付きの箱への全射」を数えてから箱の番号を外す。(1)(2)では箱ごとの人数構成を使い，(3)では2個の番号付き箱への割り当てから空箱を生じるものを除く。(4)では $n+1$ を除いたときに箱が消えるか残るかで分類する。

(1)
$n-1$ 個の部分に一時的に番号を付ける。全射にするには，1つの箱だけに2個入り，残りには1個ずつ入る。2個組の選び方は$${}_n{\mathrm{C}}_2$$通りで，その後の $n-1$ 個の部分への番号の付け方は $(n-1)!$ 通りである。部分の番号を外すには $(n-1)!$ で割ればよいから$$S_n(n-1)={}_n{\mathrm{C}}_2$$である。

(2)
$n-2$ 個の番号付き部分への全射を考える。人数構成は$$3,1,\dots ,1\text{または}2,2,1,\dots ,1$$の2種類だけである。

前者は3個組を選んだ後に部分へ番号を付けるので$${}_n{\mathrm{C}}_3(n-2)!$$通りである。後者は4個を選び，その4個を2組に分けてから番号を付けるので$${}_n{\mathrm{C}}_4\cdot 3\cdot (n-2)!$$通りである。最後に $(n-2)!$ で割って$$S_n(n-2)={}_n{\mathrm{C}}_3+3{}_n{\mathrm{C}}_4$$を得る。

(3)
2つの部分を $A,B$ と区別すると，各数字の行き先は2通りずつあるので $2^n$ 通りである。ただし $A$ または $B$ が空になる2通りを除く必要がある。さらに，部分の名前を外すと各分割を2回ずつ数えているから$$S_n(2)={\displaystyle \frac{2^n-2}{2}}=2^{n-1}-1$$である。

(4)
$n+1$ を含む部分に注目する。その部分が $\{n+1\}$ なら，残りは $k-1$ 個の部分への分割であり $S_n(k-1)$ 通りである。その部分がほかの数字も含むなら，$n+1$ を取り除いても $k$ 個の部分が残る。先に $1,\dots ,n$ を $k$ 個に分け，$n+1$ を入れる部分を選ぶので $k{S}_n(k)$ 通りである。よって$$S_{n+1}(k)=S_n(k-1)+k{S}_n(k)$$となる。