写像12相（場合の数の有名問題）

$n$ 個の玉を $k$ 個の箱に入れる方法が何通りあるかを数えましょう。

以下のように12パターンの問題設定が考えられます。

• $n$ 個の玉を区別する or しない
• $k$ 個の箱を区別する or しない
• 「条件なし」or「全ての箱の中身が1つ以下という条件つき」or 「全ての箱の中身が1つ以上という条件つき」

全部で $2\times 2\times 3=12$ パターンの問題があります。

まずは，12パターンのうちの1つを見てみましょう。

これは簡単ですね。残りの11パターンも順番に考えていきましょう。以下の表の2～12を埋めるのが目標です。

ただし，

• 玉が箱より多い場合「各1つ以下」を満たす入れ方は存在しません。よって，「各1つ以下」のパターンに関しては $n\leqq k$ のもとで考えます。
• 同様に，箱が玉より多い場合「各1つ以上」を満たす入れ方は存在しません。よって，「各1つ以上」のパターンに関しては $n\geqq k$ のもとで考えます。

では，残り11個頑張りましょう。難易度順に「2,5,8,11」→「4,6」→「3,7,9」→「10,12」と解説していきます。記事の最後に埋め終わった表があります。

まずは，「各1つ以下」という条件の場合（2,5,8,11）を考えます。同じ箱に2つ以上玉が入らないので簡単です。

• 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}$ 通り。

詳しくは 重複組合せの公式と例題（玉，整数解の個数）で解説しています。4と6が難しかった人はぜひご覧ください。

3はかなり手強いです。3ができればそこから3→9→7とわかります。詳細は別記事で説明しています。→全射の個数の証明とベル数

• 3：$n$ 個の区別する玉を $k$ 個の区別する箱に入れる場合の数（全ての箱に1つ以上）は，
  $\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：ベル数と呼ばれる有名な数です。「各1つ以上」という条件が無いので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}{}_j\mathrm{C}_{i}i^n$

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

• 12：玉も箱も区別せず，各1つ以上です。これは，正の整数 $n$ を $k$ 個の正の整数の和に分解する場合の数です。ここでは $P(n,k)$ と書きます。

• 10：玉も箱も区別せず，条件なしです。これは，正の整数 $n$ を $k$ 個の非負の整数の和に分解する場合の数です。これは，正の整数 $n+k$ を $k$ 個の正の整数の和に分解する場合の数と等しく，$P(n+k,k)$ となります。

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

• $n$ 個の玉をそれぞれをいずれかの箱に対応させる「写像」が何通りあるか数える問題です。
• 問題設定が12パターンあります。

写像12相という名前はかっこいいですね。

ちなみに，「各1つ以下」という条件は「単射」に対応し，「各1つ以上」という条件は「全射」に対応します。