場合の数の数え方の体系
概要
場合の数の数え方の体系（twelvefold way）とは、$n$ 個の玉を $k$ 個の箱に入れる方法を、玉・箱を区別するか否かと、制約なし・各箱に高々 1 個・1 個以上で 12 通りに分けて数える整理である。入れ方を写像 $f\colon\{1,\dots,n\}\to\{1,\dots,k\}$ とみると、高々 1 個は単射、1 個以上は全射にあたる。重複順列 $k^n$、順列 $k(k-1)\cdots(k-n+1)$、重複組合せ $\binom{n+k-1}{n}$、組合せ $\binom{k}{n}$ はその 4 つである。区別する玉と箱での全射の数は包除原理により $\sum_{j=0}^{k}(-1)^j\binom{k}{j}(k-j)^n=k!\,S(n,k)$（$S(n,k)$ は第 2 種 Stirling 数）であり、玉も箱も区別しないときは分割数が現れる。
高校での出発点：4 つの公式
高校で習う場合の数の公式を、数値つきで並べる。
$3$ 人それぞれに、$4$ 種類の飲み物から 1 つずつ配る（同じ飲み物を何人がもらってもよい）。$4^3=64$ 通り。
$4$ 脚の椅子に $3$ 人が座る（1 脚に 1 人まで）。${}_4\mathrm{P}_3=4\cdot3\cdot2=24$ 通り。
$4$ 脚の椅子から座る $3$ 脚を選ぶ。${}_4\mathrm{C}_3=4$ 通り。
$4$ 種類の味から、同じ味を何個選んでもよいとしてアイスを $3$ 個選ぶ。${}_4\mathrm{H}_3={}_6\mathrm{C}_3=20$ 通り。
問題文を読んで、この 4 つのどれを使うかを決めるのが高校の場合の数である。しかし、4 つの公式がなぜこの 4 つなのか、ほかにどんな数え方がありうるのかは、教科書ではあまり説明されない（→ thm-sc-twelvefold）。
4 つの問題は、どれも「$n$ 個の玉を $k$ 個の箱に入れる」という形に書き直せる。飲み物の問題（ex-sc-drinks）では、人が玉、飲み物が箱である（人 $i$ がもらう飲み物を「玉 $i$ を入れる箱」とみなす）。椅子の問題（ex-sc-chairs）では、人が玉、椅子が箱で、1 つの箱に玉は高々 1 個である。組合せ（ex-sc-choose-chairs）は、椅子の問題で玉（座る人）を区別せず、どの椅子が埋まるかだけを問う場合である。アイスの問題（ex-sc-ice）では、選ぶ 3 個のアイスが玉、味が箱であり、玉どうしは区別しない（どのアイスが何番目に選ばれたかは問わない）。
すると、問題を分ける観点は 2 つにまとまる。
- 玉を区別するか、箱を区別するか（区別する・しないの組は $2\times2=4$ 通り）。
- 入れ方に制約をつけるか：制約なし、各箱に高々 1 個、各箱に 1 個以上（$3$ 通り）。
合わせて $4\times3=12$ 通りの数え方がある。これを twelvefold way（12 通りの数え方）という。高校の 4 つの公式はそのうちの 4 つであり、残りの 8 つの中には、高校では名前の付いていない数（第 2 種 Stirling 数、分割数）が現れる。本記事では、12 通りを写像の言葉で定義し、それぞれの個数を証明つきで求め（→ thm-sc-twelvefold）、よくある数え間違いがどの区別の見落としから生じるかを反例で示す（→ ex-sc-give-one-first、ex-sc-divide-by-factorial、ex-sc-divide-multiset）。
高校の計算と大学の概念の対応（$N$、$K$ は次節の玉と箱の集合）：高校 大学 ボックス 重複順列 写像全体 $K^N$ prop-sc-maps-injections 順列 単射 prop-sc-maps-injections 組合せ $K$ の $n$ 元部分集合 thm-sc-stars-bars 重複組合せ 個数の列 thm-sc-stars-bars 組分け 集合の分割、Stirling 数 def-sc-stirling-partition $n!$・$k!$ で割る 同値類の大きさがそろう prop-sc-surj-stirling
取り出すべき構造：写像とその同一視
以下、$n\ge1$、$k\ge1$ とし、玉の集合を $N:=\{1,2,\dots,n\}$、箱の集合を $K:=\{1,2,\dots,k\}$ とする。玉 $i$ を箱 $f(i)$ に入れることで、入れ方と写像 $f\colon N\to K$ が一対一に対応する。$N$ から $K$ への写像全体を $K^N$ と書く。
- $f$ が単射（$i\ne j$ なら $f(i)\ne f(j)$）であることは、各箱に玉が高々 1 個であることと同じである。
- $f$ が全射（どの $x\in K$ にも $f(i)=x$ となる $i$ がある）であることは、空の箱がないことと同じである。
箱 $x$ に入った玉の集合 $f^{-1}(x):=\{i\in N\mid f(i)=x\}$ を $x$ のファイバーと呼ぶ。
「玉を区別しない」とは、玉の番号を付け替えて一致する 2 つの入れ方を同じとみなすことである。番号の付け替えは全単射 $\sigma\colon N\to N$ で表され、付け替えた後の入れ方は $f\circ\sigma$ である（新しい番号 $i$ の玉は、もとの番号 $\sigma(i)$ の玉で、箱 $f(\sigma(i))$ に入っている）。箱についても同様である。
$f,g\in K^N$ について、次のように定める。
- 玉を区別しないとき同じ：全単射 $\sigma\colon N\to N$ で $g=f\circ\sigma$ となるものがある。
- 箱を区別しないとき同じ：全単射 $\tau\colon K\to K$ で $g=\tau\circ f$ となるものがある。
- 玉も箱も区別しないとき同じ：全単射 $\sigma\colon N\to N$、$\tau\colon K\to K$ で $g=\tau\circ f\circ\sigma$ となるものがある。
いずれも同値関係である（恒等写像、逆写像、合成をとればよい）。玉・箱を区別しないときの入れ方の数とは、それぞれの同値類の個数のことである。単射・全射であることは全単射との合成で変わらないので、「単射である入れ方の数」「全射である入れ方の数」も同値類の個数として意味をもつ。
$n=k=2$ とし、写像 $f$ を $(f(1),f(2))$ と書くと、$K^N$ は $(1,1),(1,2),(2,1),(2,2)$ の $4$ 個である。
- 玉を区別しないと、同値類は $\{(1,1)\}$、$\{(1,2),(2,1)\}$、$\{(2,2)\}$ の $3$ 個である。大きさが $1,2,1$ とそろわないので、$4/2!=2$ とは合わない。
- 箱を区別しないと、同値類は $\{(1,1),(2,2)\}$ と $\{(1,2),(2,1)\}$ の $2$ 個である。玉も箱も区別しないときも $2$ 個である。
同値類の個数を直接数えるのは難しい。そこで、各同値類を具体的なデータで言い表す。
$f,g\in K^N$ について次が成り立つ。
- 玉を区別しないとき $f$ と $g$ が同じであるのは、すべての箱 $x\in K$ で $|f^{-1}(x)|=|g^{-1}(x)|$ となるとき、そのときに限る。さらに、$a_1+\cdots+a_k=n$ を満たす $0$ 以上の整数の列 $(a_1,\dots,a_k)$ には、$|f^{-1}(x)|=a_x$（$x\in K$）となる $f$ がある。
- 箱を区別しないとき $f$ と $g$ が同じであるのは、空でないファイバーの集まり $\pi(f):=\{f^{-1}(x)\mid x\in K,\ f^{-1}(x)\ne\emptyset\}$ が $\pi(g)$ と一致するとき、そのときに限る。
- 玉も箱も区別しないとき $f$ と $g$ が同じであるのは、空でないファイバーの大きさを大きい順に並べた列が一致するとき、そのときに限る。
- $g=f\circ\sigma$ なら $g^{-1}(x)=\sigma^{-1}(f^{-1}(x))$ であり、$\sigma^{-1}$ は単射なので大きさは等しい。逆に、すべての $x$ で $|f^{-1}(x)|=|g^{-1}(x)|$ なら、$x$ ごとに全単射 $\sigma_x\colon g^{-1}(x)\to f^{-1}(x)$ を選び、$i\in g^{-1}(x)$ について $\sigma(i):=\sigma_x(i)$ と定める。$N$ は $g^{-1}(1),\dots,g^{-1}(k)$ に、また $f^{-1}(1),\dots,f^{-1}(k)$ に互いに交わらずに分かれるので $\sigma\colon N\to N$ は全単射であり、$i\in g^{-1}(x)$ について $f(\sigma(i))=x=g(i)$ となる。よって $g=f\circ\sigma$ である。後半は、玉 $1,\dots,a_1$ を箱 $1$ に、続く $a_2$ 個を箱 $2$ に、…と入れればよい。
- $g=\tau\circ f$ なら $g^{-1}(\tau(x))=f^{-1}(x)$ であり、$\tau$ は全単射なので $\pi(g)=\pi(f)$ である。逆に $\pi(f)=\pi(g)$ とする。$f$ の像 $f(N)$ の元 $x$ について、$f^{-1}(x)\in\pi(g)$ なので $g^{-1}(y)=f^{-1}(x)$ となる $y\in g(N)$ がちょうど 1 つあり、$\tau_0(x):=y$ と定める。異なるファイバーは互いに交わらないので $\tau_0\colon f(N)\to g(N)$ は全単射である。$K\setminus f(N)$ と $K\setminus g(N)$ は同じ個数 $k-|\pi(f)|$ の元をもつので、その間の全単射を合わせて $\tau_0$ を全単射 $\tau\colon K\to K$ に延ばせる。$i\in N$ について $x:=f(i)$ とすると $i\in f^{-1}(x)=g^{-1}(\tau(x))$ なので $g(i)=\tau(f(i))$ である。
- $g=\tau\circ f\circ\sigma$ なら、1 と 2 から空でないファイバーの大きさの集まりは変わらない。逆に、大きい順に並べた列が一致するなら、$f$ と $g$ の空でないファイバーの個数は等しく、大きさが等しいファイバーどうしを対応させる箱の全単射 $\tau$（空の箱どうしも対応させる）をとれば、すべての $x$ で $|(\tau\circ f)^{-1}(x)|=|g^{-1}(x)|$ となる。1 により $g=\tau\circ f\circ\sigma$ となる $\sigma$ がある。$\square$
2 の $\pi(f)$ は、$N$ を空でない互いに交わらない部分集合（ブロック）に分けたもの、すなわち $N$ の集合の分割である。逆に、ブロックの個数が $k$ 以下の分割は、ブロックを相異なる箱に入れることで必ずある $f$ の $\pi(f)$ として現れる。3 の列は、$n$ を正の整数の和に表したもので、$n$ の分割という。例えば $n=4$ の分割は $4,\ 3+1,\ 2+2,\ 2+1+1,\ 1+1+1+1$ の $5$ 個である。
lem-sc-invariants により、12 通りの数え上げは次の 4 種類のデータの数え上げに言い換わる。
| 玉 | 箱 | 入れ方を表すデータ |
|---|---|---|
| 区別する | 区別する | 写像 $f\colon N\to K$ そのもの |
| 区別しない | 区別する | 個数の列 $(a_1,\dots,a_k)$、$a_x\ge0$、$\sum a_x=n$ |
| 区別する | 区別しない | $N$ の集合の分割（ブロックは $k$ 個以下） |
| 区別しない | 区別しない | $n$ の分割（項は $k$ 個以下） |
単射・全射の条件は、それぞれ「各 $a_x\le1$（ブロックの大きさがすべて $1$）」「各 $a_x\ge1$（ブロックがちょうど $k$ 個）」と読み替えられる。
主定理：12 通りの表
表に現れる記号を定める。$k^{\underline n}:=k(k-1)\cdots(k-n+1)$（$n$ 個の積。$n>k$ なら因数 $0$ を含むので $0$）を下降階乗冪という。二項係数 $\binom ab$ は $a$ 元集合の $b$ 元部分集合の個数で、$0\le b\le a$ なら $\frac{a!}{b!\,(a-b)!}$、$b>a$ なら $0$ である。条件 $P$ について $[P]$ は、$P$ が成り立てば $1$、成り立たなければ $0$ を表す。
$n\ge0$、$j\ge0$ とする。
- $n$ 元集合を、空でない互いに交わらない $j$ 個の部分集合（ブロック）に分ける方法の数を $S(n,j)$ と書き、第 2 種 Stirling 数という。ブロックの順序は区別しない。$S(0,0):=1$ とし、$n\ge1$ なら $S(n,0)=0$、$S(0,j)=0$（$j\ge1$）である。
- $n$ を $j$ 個の正の整数の和に表す方法の数を $p_j(n)$ と書く。項の順序は区別しない（大きい順に並べた列 $\lambda_1\ge\cdots\ge\lambda_j\ge1$、$\lambda_1+\cdots+\lambda_j=n$ の個数）。$p_0(0):=1$、$n\ge1$ なら $p_0(n)=0$ である。$p(n):=\sum_{j=0}^np_j(n)$ を $n$ の分割数という。
$\{1,2,3\}$ を 2 ブロックに分ける方法は $\{1\}\{2,3\}$、$\{2\}\{1,3\}$、$\{3\}\{1,2\}$ なので $S(3,2)=3$ である。$6$ を 3 項に分ける方法は $4+1+1$、$3+2+1$、$2+2+2$ なので $p_3(6)=3$ である。
$n\ge1$、$k\ge1$ とする。$n$ 個の玉を $k$ 個の箱に入れる方法の数は次の表のとおりである。
| 玉 | 箱 | 制約なし | 各箱に高々 1 個（単射） | 各箱に 1 個以上（全射） |
|---|---|---|---|---|
| 区別する | 区別する | $k^n$ | $k^{\underline n}$ | $k!\,S(n,k)$ |
| 区別しない | 区別する | $\binom{n+k-1}n$ | $\binom kn$ | $\binom{n-1}{k-1}$ |
| 区別する | 区別しない | $\sum_{j=1}^kS(n,j)$ | $[n\le k]$ | $S(n,k)$ |
| 区別しない | 区別しない | $\sum_{j=1}^kp_j(n)$ | $[n\le k]$ | $p_k(n)$ |
さらに、区別する玉を区別する箱に入れる全射の個数は
$$
k!\,S(n,k)=\sum_{j=0}^k(-1)^j\binom kj(k-j)^n
$$
である。
証明は次節で、行ごとに与える。表の各項が何に当たるかを先に見ておく。第 1 行の 3 つは重複順列・順列・（高校では名前のない）全射の個数である。第 2 行は重複組合せ・組合せと、「各箱に 1 個以上の重複組合せ」である。第 3 行と第 4 行は箱を区別しない場合で、高校では「組分け」として一部だけを扱う。単射の列の $[n\le k]$ は、箱を区別しないと「すべての玉を別々の箱に入れる」入れ方が 1 通りしかないことを表している。
証明
箱を区別する場合
$|K^N|=k^n$ であり、単射 $N\to K$ の個数は $k^{\underline n}$ である。
玉 $1,2,\dots,n$ の行き先を順に決める。制約がなければ各玉に $k$ 通りの選び方があり、積の法則により $k^n$ 通りである。単射では、玉 $i$ の行き先は、すでに使った $i-1$ 個の箱を除いた $k-(i-1)$ 通りから選ぶので、$k(k-1)\cdots(k-n+1)=k^{\underline n}$ 通りである（$n>k$ なら玉 $k+1$ の選び方が $0$ 通りで、全体も $0$）。$\square$
玉を区別しない場合は、lem-sc-invariants の 1 により、個数の列 $(a_1,\dots,a_k)$ を数えればよい。
$n\ge0$、$k\ge1$ とする。
- $a_1+\cdots+a_k=n$ を満たす $0$ 以上の整数の列 $(a_1,\dots,a_k)$ の個数は $\binom{n+k-1}n=\binom{n+k-1}{k-1}$ である。
- $n\ge1$ のとき、$a_1+\cdots+a_k=n$ を満たす $1$ 以上の整数の列の個数は $\binom{n-1}{k-1}$ である（$n< k$ なら $0$）。
- 1 の列のうち、各 $a_x$ が $0$ または $1$ であるものの個数は $\binom kn$ である。
- 列 $(a_1,\dots,a_k)$ に対し、$\circ$ を $a_1$ 個、仕切り $|$ を 1 本、$\circ$ を $a_2$ 個、仕切りを 1 本、…、$\circ$ を $a_k$ 個と並べた記号列を対応させる。これは $\circ$ が $n$ 個、$|$ が $k-1$ 個の、長さ $n+k-1$ の記号列である。逆に、そのような記号列が与えられると、仕切りで区切られた $k$ 個の区間の $\circ$ の個数として列 $(a_1,\dots,a_k)$ がただ 1 つ定まる。したがって列の個数は、$n+k-1$ 個の位置から $\circ$ を置く $n$ 個を選ぶ方法の数 $\binom{n+k-1}n$ に等しい。例えば $n=3$、$k=4$ で $\circ|\,|\circ\circ|$ は列 $(1,0,2,0)$ を表す。
- $b_x:=a_x-1$ とおくと、$a_x\ge1$ の列と、$b_1+\cdots+b_k=n-k$ を満たす $b_x\ge0$ の列が一対一に対応する。$n\ge k$ なら 1 によりその個数は $\binom{(n-k)+k-1}{n-k}=\binom{n-1}{n-k}=\binom{n-1}{k-1}$ である。$n< k$ なら $a_x\ge1$ の和は $k>n$ 以上になるので列はなく、$\binom{n-1}{k-1}=0$ と一致する。
- $a_x\in\{0,1\}$ の列は、$a_x=1$ となる $x$ の集合（$K$ の $n$ 元部分集合）と一対一に対応する。$\square$
高校の記号では ${}_k\mathrm{H}_n={}_{n+k-1}\mathrm{C}_n$ が 1 の主張である（ex-sc-ice は $n=3$、$k=4$ の場合で $\binom63=20$）。2 は「先に各箱に 1 個ずつ入れてから、残りを自由に入れる」と言い換えられる。玉を区別しないときはこの言い換えで正しく数えられるが、玉を区別するときには重複して数えてしまう（ex-sc-give-one-first）。
最後に、区別する玉を区別する箱に入れる全射を数える。そのために包除原理を用意する。
有限集合 $X$ とその部分集合 $A_1,\dots,A_k$ について、$I\subset K=\{1,\dots,k\}$ に対し $A_I:=\bigcap_{x\in I}A_x$（$A_\emptyset:=X$）とおくと、どの $A_x$ にも属さない $X$ の元の個数は
$$
\sum_{I\subset K}(-1)^{|I|}|A_I|=\sum_{j=0}^k(-1)^j\sum_{|I|=j}|A_I|
$$
である。
左辺は、各元 $u\in X$ について、$u\in A_I$ となる $I$ にわたる $(-1)^{|I|}$ の和を足し合わせたものである。$u$ がちょうど $m$ 個の $A_x$ に属するとし、その添字の集合を $M$ とすると、$u\in A_I$ となるのは $I\subset M$ のときなので、$u$ の寄与は
$$
\sum_{I\subset M}(-1)^{|I|}=\sum_{j=0}^m\binom mj(-1)^j=(1-1)^m
$$
である（二項定理）。これは $m=0$ なら $1$、$m\ge1$ なら $0$ である。よって左辺は、どの $A_x$ にも属さない元の個数に等しい。$\square$
全射 $N\to K$ の個数は $\displaystyle\sum_{j=0}^k(-1)^j\binom kj(k-j)^n$ である。
$X:=K^N$、$A_x:=\{f\in X\mid x\notin f(N)\}$（箱 $x$ が空になる入れ方）とする。全射とは、どの $A_x$ にも属さない $f$ のことである。$|I|=j$ のとき、$A_I$ は $I$ の箱をすべて空にする写像、すなわち $N$ から $K\setminus I$（$k-j$ 元）への写像の全体なので、prop-sc-maps-injections と同じ理由で $|A_I|=(k-j)^n$ である。$j$ 元部分集合 $I$ は $\binom kj$ 個あるので、lem-sc-inclusion-exclusion から主張を得る。$\square$
包除原理を指示関数の期待値から導く方法は 期待値の線形性と数え上げ で扱う。
$n=5$、$k=3$ では $3^5-3\cdot2^5+3\cdot1^5-0=243-96+3=150$ である。
箱を区別しない場合
lem-sc-invariants の 2 により、区別する玉を区別しない箱に入れる方法は、$N$ の集合の分割でブロックが $k$ 個以下のものと一対一に対応し、全射であることはブロックがちょうど $k$ 個であることにあたる。よって、全射の入れ方の数は $S(n,k)$、制約のない入れ方の数は $\sum_{j=1}^kS(n,j)$ である。単射ではすべてのブロックが 1 元集合になり、そのような分割は $n\le k$ のときだけ 1 つある。これで thm-sc-twelvefold の第 3 行が示された。第 1 行の全射の個数を $S(n,k)$ で書くには、次の命題を使う。
全射 $N\to K$ の個数は $k!\,S(n,k)$ である。したがって
$$
S(n,k)=\frac1{k!}\sum_{j=0}^k(-1)^j\binom kj(k-j)^n
$$
である。
全射 $f$ に、ブロックがちょうど $k$ 個の分割 $\pi(f)$ を対応させる。ブロックが $k$ 個の分割 $\{B_1,\dots,B_k\}$ を 1 つ固定すると、$\pi(f)$ がこの分割になる全射 $f$ は、各ブロックに相異なる箱を 1 つずつ割り当てる方法、すなわち $\{B_1,\dots,B_k\}$ から $K$ への全単射と一対一に対応し、その個数は $k!$ である。よって全射の個数は $k!\,S(n,k)$ である。後半は prop-sc-surjections と合わせて得られる。$\square$
ex-sc-surj-5-3 から $S(5,3)=150/3!=25$ である。「$k!$ で割る」ことが正しいのは、どの全射も $k!$ 個ずつ同じ分割を与えるからである。空の箱がありうる場合にはこれが崩れる（ex-sc-divide-by-factorial）。
Stirling 数は、公式よりも次の漸化式で計算するほうが速い。
$n\ge1$、$j\ge1$ について $S(n,j)=S(n-1,j-1)+j\,S(n-1,j)$ である。
$\{1,\dots,n\}$ の $j$ ブロックの分割を、元 $n$ が 1 元のブロック $\{n\}$ をなすかどうかで分ける。なすものは、$\{n\}$ を除くと $\{1,\dots,n-1\}$ の $j-1$ ブロックの分割になり、これは一対一の対応なので $S(n-1,j-1)$ 個ある。なさないものは、$n$ を取り除くと $\{1,\dots,n-1\}$ の $j$ ブロックの分割になる（$n$ のいたブロックは空にならない）。逆に $\{1,\dots,n-1\}$ の $j$ ブロックの分割から、$n$ をどのブロックに加えるかで $j$ 通りの分割が得られ、それらは互いに異なる。よってこの種類は $j\,S(n-1,j)$ 個ある。$\square$
漸化式から、例えば $S(4,2)=S(3,1)+2\,S(3,2)=1+2\cdot3=7$ である。こうして求めた $S(n,j)$ の表（$1\le j\le n\le7$）は次のとおりである。
| $n\backslash j$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 1 | 1 | ||||||
| 2 | 1 | 1 | |||||
| 3 | 1 | 3 | 1 | ||||
| 4 | 1 | 7 | 6 | 1 | |||
| 5 | 1 | 15 | 25 | 10 | 1 | ||
| 6 | 1 | 31 | 90 | 65 | 15 | 1 | |
| 7 | 1 | 63 | 301 | 350 | 140 | 21 | 1 |
行の和 $B_n:=\sum_{j}S(n,j)$ は $1,2,5,15,52,203,877$（$n=1,\dots,7$）であり、$n$ 元集合の分割の総数を表す（Bell 数）。$n\le k$ なら、区別する $n$ 個の玉を区別しない $k$ 個の箱に入れる方法の数は $B_n$ である。
写像全体をファイバーの分割で分類すると、第 1 行と第 3 行を結ぶ等式が得られる。
$n\ge1$、$k\ge1$ について
$$
k^n=\sum_{j=1}^nS(n,j)\,k^{\underline j}
$$
である。
写像 $f\colon N\to K$ を分割 $\pi(f)$ で分類する。ブロックが $j$ 個の分割 $\{B_1,\dots,B_j\}$ を固定すると、$\pi(f)$ がこの分割になる $f$ は、各ブロックに相異なる箱を割り当てる方法、すなわちブロックの集合から $K$ への単射と一対一に対応し、prop-sc-maps-injections によりその個数は $k^{\underline j}$ である（$j>k$ なら $0$）。$j$ について足すと $|K^N|=k^n$ になる。$\square$
下降階乗冪でべき和の公式を導く話は 数列の和と差分 で扱う。
$n=3$ では $k^3=k+3k(k-1)+k(k-1)(k-2)$ であり、右辺を展開すると両辺は $k$ の多項式として等しい。例えば $k=2$ では $8=2+6+0$ である。
玉も箱も区別しない場合：分割数
lem-sc-invariants の 3 により、区別しない $n$ 個の玉を区別しない $k$ 個の箱に入れる方法は、$n$ の分割で項が $k$ 個以下のものと一対一に対応する。全射は項がちょうど $k$ 個の分割、単射はすべての項が $1$ の分割（$n\le k$ のときだけ 1 つ）にあたる。これで thm-sc-twelvefold の第 4 行が示された。
$p_j(n)$ には、prop-sc-surj-stirling のように二項係数と冪だけで書ける簡単な式がない。計算には次の漸化式を使うのが基本である。
$n\ge1$、$j\ge1$ について $p_j(n)=p_{j-1}(n-1)+p_j(n-j)$ である。ただし $m<0$ なら $p_j(m):=0$ とする。
$n=\lambda_1+\cdots+\lambda_j$（$\lambda_1\ge\cdots\ge\lambda_j\ge1$）を、$\lambda_j=1$ かどうかで分ける。$\lambda_j=1$ のものは、最後の $1$ を除くと $n-1$ の $j-1$ 項の分割になり、この対応は一対一なので $p_{j-1}(n-1)$ 個ある。$\lambda_j\ge2$ のものは、各項から $1$ を引くと $n-j$ の $j$ 項の分割 $(\lambda_1-1)+\cdots+(\lambda_j-1)$ になり、逆に各項に $1$ を足せば戻るので $p_j(n-j)$ 個ある（$n< j$ なら $0$ 個）。$\square$
分割数を母関数の係数として数える方法は 分割の母関数 で扱う。
漸化式から $p_3(6)=p_2(5)+p_3(3)=2+1=3$ となり、ex-sc-small-stirling と一致する。$p(n)$ は $n=1,2,\dots,10$ で $1,2,3,5,7,11,15,22,30,42$ であり、$p(100)=190569292$ である。
分割数には母関数 $\sum_{n\ge0}p(n)x^n=\prod_{m\ge1}\frac1{1-x^m}$（Bog17 §4.2 の Problem 203、p. 82 で問題として導かせる）や漸近式など多くの結果があるが、本記事では扱わず、証明もしない。
高校の公式は表のどこにあるか
高校の記号で書くと、thm-sc-twelvefold の上 2 行は次のとおりである（$k$ 個の箱に $n$ 個の玉）。
| 制約なし | 単射 | |
|---|---|---|
| 玉も箱も区別する | 重複順列 ${}_k\Pi_n=k^n$ | 順列 ${}_k\mathrm{P}_n=k^{\underline n}$ |
| 玉を区別しない | 重複組合せ ${}_k\mathrm{H}_n={}_{n+k-1}\mathrm{C}_n$ | 組合せ ${}_k\mathrm{C}_n$ |
「組合せは順列を $n!$ で割ったもの」という関係 ${}_k\mathrm{C}_n={}_k\mathrm{P}_n/n!$ は、単射の列で玉の区別を外すことにあたる。高校の「組分け」は第 3 行の全射の列の一部である。
6 人を 3 つの組に分ける方法（組に名前はなく、どの組も 1 人以上）は $S(6,3)=90$ 通りで、組の人数で分けると
- $4,1,1$ 人：4 人組を選ぶ $\binom64=15$ 通り、
- $3,2,1$ 人：$\binom63\binom32=60$ 通り、
- $2,2,2$ 人：$\binom62\binom42\binom22/3!=15$ 通り
であり、$15+60+15=90$ となる。最後の場合は、2 人組を選ぶ順序の $3!$ 通りを同じとみなすので $3!$ で割る（$4,1,1$ 人では 4 人組を選べば残りは決まる）。
区別を外すときに「$n!$ で割る」「$k!$ で割る」が正しい条件は、次のようにまとめられる。単射 $f$ では $f\circ\sigma=f$ なら $\sigma$ は恒等写像である（$f(\sigma(i))=f(i)$ と単射性から $\sigma(i)=i$）。したがって、玉の付け替え $n!$ 通りは $f$ から相異なる $n!$ 個の単射を作り、玉を区別しないときの同値類はどれもちょうど $n!$ 個の単射からなる。同様に全射 $f$ では $\tau\circ f=f$ なら $\tau$ は $f(N)=K$ の各点を動かさないので恒等写像であり、箱を区別しないときの同値類はどれもちょうど $k!$ 個の全射からなる（prop-sc-surj-stirling）。この条件が外れると、割り算は正しくない。
例と反例
| 外した仮定 | 崩れる主張 | ボックス |
|---|---|---|
| 玉を区別しない | 先に 1 個ずつ配る数え方 | ex-sc-give-one-first |
| 全射 | $k!$ で割れば箱の区別を外せる | ex-sc-divide-by-factorial |
| 単射 | $n!$ で割れば玉の区別を外せる | ex-sc-divide-multiset |
5 個の玉を 3 個の箱に、どの箱も空にならないように入れる。玉も箱も区別するなら $3!\,S(5,3)=150$ 通り、玉を区別せず箱を区別するなら $\binom42=6$ 通り（個数の列 $(3,1,1),(1,3,1),(1,1,3),(2,2,1),(2,1,2),(1,2,2)$）、玉を区別し箱を区別しないなら $S(5,3)=25$ 通り、どちらも区別しないなら $p_3(5)=2$ 通り（$3+1+1$ と $2+2+1$）である。
区別する 5 個の玉を区別する 3 個の箱に、どの箱も空にならないように入れる。「まず各箱に 1 個ずつ入れる（$5\cdot4\cdot3=60$ 通り）、残りの 2 個を自由に入れる（$3^2=9$ 通り）」と数えると $540$ 通りになるが、正しくは $150$ 通りである。この数え方は、各入れ方を 1 回ずつ数えるという条件を満たさない。箱 1 に玉 $\{1,2,3\}$、箱 2 に玉 $4$、箱 3 に玉 $5$ という入れ方は、「最初に箱 1 に入れた玉」が $1,2,3$ のどれでもよいので 3 回数えられる。個数が $(3,1,1)$ 型の入れ方（60 通り）は 3 回ずつ、$(2,2,1)$ 型（90 通り）は $2\cdot2=4$ 回ずつ数えられ、$60\cdot3+90\cdot4=540$ となる。玉を区別しないときは「最初の 1 個」を選ぶ自由がないので、同じ方法で正しく数えられる（thm-sc-stars-bars の 2。5 個なら $\binom{2+3-1}2=6=\binom42$）。
区別する 2 個の玉を、区別しない 3 個の箱に入れる。正しい数は $S(2,1)+S(2,2)=2$ 通り（同じ箱か、別々の箱か）である。「区別する箱なら $3^2=9$ 通りなので、$3!$ で割る」と $\frac96=1.5$ となり、整数にもならない。$9$ 個の写像のうち「2 個とも同じ箱」の 3 個と「別々の箱」の 6 個がそれぞれ 1 つの同値類をなし、同値類の大きさが $k!=6$ にそろっていない。写像が全射でないと、空の箱どうしを入れ替える $\tau\ne\mathrm{id}$ で $\tau\circ f=f$ となりうるからである。「$k!$ で割る」という含意は、全射という仮定を外すと成り立たない。
3 種類の味から、同じ味を選んでもよいとしてアイスを 2 個選ぶ。玉（アイス）を区別しない入れ方で、正しくは $\binom{2+3-1}2=6$ 通りである。「区別すれば $3^2=9$ 通り、アイスの順序 $2!$ で割る」と $4.5$ となり誤りである。9 通りのうち、味の異なる選び方は順序違いで 2 回ずつ現れるが、同じ味を 2 個選ぶ 3 通りはアイスを入れ替えても変わらないので 1 回ずつしか現れず、$2!$ で割ると半分に数えられてしまう。「$n!$ で割る」は、単射という仮定を外すと成り立たない。これは高校で「重複組合せは組合せの公式から直接は出ない」理由でもあり、thm-sc-stars-bars のように別の対応を作る必要がある。
数学オリンピックの問題から
1989 年第 6 問：隣り合う組の包除
集合 $\{1,2,\dots,2n\}$（$n$ は正の整数）の順列 $(x_1,x_2,\dots,x_{2n})$ が性質 $P$ をもつとは、$\{1,2,\dots,2n-1\}$ の少なくとも 1 つの $i$ について $|x_i-x_{i+1}|=n$ となることをいう。各 $n$ について、性質 $P$ をもつ順列のほうが、もたない順列より多いことを示せ。
出典：第 30 回国際数学オリンピック（1989 年）第 6 問の和訳（原文の $x_m$ は $x_{2n}$ とした）Oly89。
$k=1,\dots,n$ について、$k$ と $k+n$ が隣り合う順列の集合を $A_k$ とする。性質 $P$ をもつ順列の集合は $A_1\cup\cdots\cup A_n$ である。$k$ と $k+n$ を 1 つのかたまりとみなすと、かたまりの内部の順序が 2 通り、かたまりと残り $2n-2$ 個の並べ方が $(2n-1)!$ 通りなので $|A_k|=2\,(2n-1)!$ である。同様に $j\ne k$ なら $|A_j\cap A_k|=4\,(2n-2)!$ である。
ここで $\sum_k|A_k|=2n\cdot(2n-1)!=(2n)!$ となり、順列の総数と等しい。しかしこれは「すべての順列が性質 $P$ をもつ」ことを意味しない。2 つ以上の $A_k$ に属する順列を重複して数えているからである。重複を除くために、次の不等式を使う：どの有限集合 $A_1,\dots,A_n$ についても
$$
|A_1\cup\cdots\cup A_n|\ge\sum_k|A_k|-\sum_{j< k}|A_j\cap A_k|.
$$
実際、ちょうど $m\ge1$ 個の $A_k$ に属する元は右辺で $m-\binom m2=1-\binom{m-1}2\le1$ 回数えられ、どの $A_k$ にも属さない元は $0$ 回数えられるので、右辺は左辺以下である。これを使うと
$$
|A_1\cup\cdots\cup A_n|\ge(2n)!-\binom n2\cdot4\,(2n-2)!=(2n)!-\frac{n-1}{2n-1}(2n)!=\frac n{2n-1}(2n)!>\frac{(2n)!}2
$$
となり、性質 $P$ をもつ順列は全体の半分より多い。$\square$
1 つ目の等式 $\sum_k|A_k|=(2n)!$ は、「無作為な順列で隣り合う組 $\{k,k+n\}$ の個数の期待値が $1$」と言い換えられる。期待値が $1$ でも、その値が $0$ になる確率が小さいとは限らない。上の不等式は包除原理を 2 項で打ち切ったもので、Bonferroni の不等式の 1 つ（2 項で打ち切った下からの評価）である。全部の項を使えば lem-sc-inclusion-exclusion から正確な個数
$$
|A_1\cup\cdots\cup A_n|=\sum_{j=1}^n(-1)^{j-1}\binom nj2^j(2n-j)!
$$
が得られ（$j$ 組のかたまりを作る数え方）、$n=2,3,4$ で $16,480,26496$（全体の $0.667,0.667,0.657$ 倍）となる。$n\to\infty$ でこの割合は $1-\frac1e=0.632\ldots$ に近づく（本記事では証明しない）。「重複して数えたものを包除原理で直す」という ex-sc-give-one-first と同じ構図が、ここでは不等式の形で使われている。
さらに先へ
- 群の作用による統一：def-sc-identification の 3 つの同一視は、対称群 $S_n$、$S_k$、$S_n\times S_k$ の $K^N$ への作用の軌道である。軌道の数を不動点の数の平均として数える Burnsideの補題 や Pólyaの数え上げ定理 は、回転で重なる塗り分けのような、他の群による同一視にも使える。
- 第 1 種 Stirling 数：cor-sc-power-falling は、多項式の基底 $x^n$ を下降階乗冪 $x^{\underline j}$ で表す係数が $S(n,j)$ であることを示している（両辺は多項式で、すべての正の整数で一致するから）。逆向きに $x^{\underline n}$ を $x^j$ で表す係数は、置換を巡回の個数で数える第 1 種 Stirling 数（符号つき）である（本記事では証明しない。係数としての定義は Bog17 §3.2 の Problem 154、p. 62）。
- 母関数：$S(n,k)$ は指数型母関数 $\sum_nS(n,k)\frac{x^n}{n!}=\frac{(e^x-1)^k}{k!}$、分割数は通常型母関数 $\prod_m\frac1{1-x^m}$ で扱うのが自然である（母関数。本記事では証明しない。指数型母関数は Bog17 付録 C の Problem 408、p. 162）。
twelvefold way の表の形は Bog17 §3.1.1 の Table 3.1.1（p. 52。「twentyfold way」の形で、$k$ 個を $n$ 人に配る記法）、Stirling 数と全射は同書 §3.2（pp. 58–61）、分割数は §3.3（p. 63 以降）にある。仕切りの方法は Lev24 §3.5（p. 244 以降）、包除原理による全射の数え上げは KT17 §7.3 の Theorem 7.9（p. 146）にある。
関連項目
- 前提: 写像, 全射, 単射, 二項係数, 二項定理
- 次に読む: 確率の定義と条件付き確率, 二項定理と組合せの恒等式, 同じものを含む順列と多項定理, 円順列とじゅず順列
- 関連（高校数学）: 数列の和と差分, 分割の母関数, 期待値の線形性と数え上げ, 最短経路の数え上げと鏡像原理
- 道具: 包除原理, 同値関係, 集合の分割
- 発展: Burnsideの補題, Pólyaの数え上げ定理, 母関数, 数え上げ組合せ論, 第2種Stirling数, 分割数, Bell数
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
