2014/10/29

写像の個数(写像12相)

分野: 場合の数  レベル: マニアック

$n$ 個の玉を $k$ 個の箱に入れる場合の数を数える問題を考えます。状況によって12パターンの問題設定が考えられるので写像12相(Twelvefold way)と呼ばれている有名な問題です。

写像という言葉は知らなくても理解できる問題です。後半はかなり難しいので読めるとこまで読んでみてください。

写像12相の概要

$n$ 個の玉を区別するのかしないのか,$k$ 個の箱を区別するのかしないのかで4通りの問題設定が考えられます。さらに,条件として,
1:何も条件がない場合
2:全ての箱の中身が一つ以下
3:全ての箱の中身が一つ以上

という3つの条件が考えられ,全部で12通りの問題設定が与えられています。

なお,$n$ 個の玉それぞれをいずれかの箱に対応させる写像とみなすと,2の条件は「単射」に対応し,3の条件は「全射」に対応します。

$n > k$ のときは玉が箱より多いので条件2を満たす入れ方は存在しません(単射は存在しない)。よって,条件2のパターンに関しては $n\leq k$ のもとで考えます。

同様に,$n <k$ のときは箱が玉より多いので条件3を満たす入れ方は存在しません(全射は存在しない)。よって,条件3のパターンに関しては $n\geq k$ のもとで考えます。

以上の問題設定のもと,下の表12マスを順々に埋めてみます!

$n$ 個の玉 $k$ 個の箱 なんでも 単射(1つ以下) 全射(1つ以上)
区別する 区別する 1:易 2:易 3:難
区別しない 区別する 4:普通 5:易 6:普通
区別する 区別しない 7:難 8:易 9:難
区別しない 区別しない 10:無理 11:易 12:無理

記事の最後に埋め終わった表があります。

単射の個数(易ゾーン)

まずは単射の個数を中心に,易ゾーン5マスを埋めます。単射については同じ箱に二つ以上玉が入らないので簡単です。

1:$n$ 個の区別する玉を $k$ 個の区別する箱に入れる場合の数(条件なし)は $k^n$ 通りです。

2:$n$ 個の区別する玉を $k$ 個の区別する箱に入れる場合の数(全ての箱に一つ以下)は${}_k\mathrm{P}_n$ 通りです。

5:$n$ 個の区別しない玉を $k$ 個の区別する箱に入れる場合の数(全ての箱に一つ以下)は,玉を入れる箱を $n$ 個選ぶ場合の数なので${}_k\mathrm{C}_n$ 通りです。

8,11:箱を区別せず,全ての箱に一つ以下の場合,$n$ 個の玉を $n$ グループに分ける場合の数なのでただ1通りです。

仕切りで考える(普通ゾーン)

大学入試としては易しいレベルですが,重要な考え方です。

4:$n$ 個の区別しない玉を $k$ 個の区別する箱に入れる場合の数(条件なし)は,$n$ 個の玉と $k-1$ 個の仕切りを一列に並べる場合の数なので,${}_{n+k-1}\mathrm{C}_{n}$ 通り。

6:さらに,全ての箱に一つ以上という条件がある場合について。 $n$ 個の玉を並べると玉と玉の隙間が $n-1$ 箇所できるが,その隙間から $k-1$ 個選んで仕切りを入れる場合の数なので,${}_{n-1}\mathrm{C}_{k-1}$ 通り。

全射の個数など(難ゾーン)

ここはかなり手強いです。詳細は別記事で説明しています。→全射の個数の証明とベル数

3:全射の個数は包除原理を用いて求めることができます:$\displaystyle\sum_{i=1}^k(-1)^{k-i}{}_k\mathrm{C}_{i}i^n$

9:スターリング数と呼ばれる有名な数です。 $k$ 個の箱を区別する場合,3の場合を $k!$ で割ったものになります:$S(n,k)=\dfrac{1}{k!}\displaystyle\sum_{i=1}^k(-1)^{k-i}{}_k\mathrm{C}_{i}i^n$

7:ベル数と呼ばれる有名な数です。9の場合を足し合わせます:
$B(n,k)=\displaystyle\sum_{j=1}^kS(n,j)=\displaystyle\sum_{j=1}^k\dfrac{1}{j!}\sum_{i=1}^j(-1)^{j-i}{}_jC_{i}i^n$

分割数(無理ゾーン)

残る二つは分割数と呼ばれ,$n$ と $k$ の簡単な式で表す公式は見つかっていません。

12:正の整数 $n$ を $k$ 個の正の整数の和に分解する場合の数。ここでは $P(n,k)$ と書きます。

10:正の整数 $n$ を $k$ 個の非負の整数の和に分解する場合の数。これは,正の整数 $n+k$ を $k$ 個の正の整数の和に分解する場合の数と等しく,$P(n+k,k)$ となります。

$n$ や $k$ が小さい場合は入試などで出題されるかもしれませんが,$P(n)$ に関する漸化式を立てるなり気合いで数えるなりするしかありません。→自然数の分割とヤング図形

写像12相まとめ

$n$ 個の玉 $k$ 個の箱 なんでも 単射(1つ以下) 全射(1つ以上)
区別する 区別する $k^n$ ${}_k\mathrm{P}_n$ $\sum_{i=1}^k(-1)^{k-i}{}_k\mathrm{C}_{i}i^n$
しない する ${}_{n+k-1}\mathrm{C}_{n}$ ${}_k\mathrm{C}_n$ ${}_{n-1}\mathrm{C}_{k-1}$
する しない $B(n,k)$ $1$ $S(n,k)$
しない しない $P(n+k,k)$ $1$ $P(n,k)$
僕は難ゾーンの3マスが好きです。
分野: 場合の数  レベル: マニアック