# 場合の数：順列・組合せと数え上げの原理

> 和の法則・積の法則から順列・組合せ・円順列・重複組合せ・全射の個数・玉と箱の 12 通りを証明し、平面と空間の分割の最大個数、5 点の凸四角形（ハッピーエンド）まで進む。
> https://rikai.mugen-giken.com/mathematics/hs-probability/counting

## 0. この記事の要点

場合の数とは、「何通りあるか」を漏れも重複もなく数える技術です。たとえば、5 人から委員長と副委員長を選ぶ方法は何通りか、トランプ 52 枚の並べ方は何通りか、といった問いに答えます。この記事を読むと、公式を丸暗記しなくても、「足す」「掛ける」という 2 つの基本ルールから順列や組合せの公式が出てくる理由が分かります。箱に玉を入れる数え方や、直線で平面を分ける個数まで、同じ考え方で数えられるようになります。以下の箇条書きは、その内容を専門用語でまとめたものです。

- 数え上げの土台は 2 つの原理だけです。**和の法則**（重ならない場合を足す）と**積の法則**（段階を踏む選び方を掛ける）。この記事ではこれを有限集合の元の個数の定理として証明し、残りの公式をすべてここから導きます。
- **順列** $n(n-1)\cdots(n-k+1)$、**組合せ** $\binom nk$、**円順列** $(n-1)!$、**同じものを含む順列** $\dfrac{n!}{n_1!\cdots n_r!}$、**重複組合せ** $\binom{n+k-1}{k}$ は、「各値が同じ個数ずつ重なっている写像で割る」という 1 つの考え方で統一的に証明できます。
- **包除原理**を使うと、全射の個数 $\sum_j(-1)^j\binom Kj(K-j)^N$ と完全順列の個数が出ます。
- 玉と箱の数え方（玉・箱が区別できるか、入れ方の条件は何か）は $3\times4=12$ 通りの表になります。全部の欄を証明つきで埋めます。
- 直線 $n$ 本が一般の位置にあるとき平面は $1+n+\binom n2$ 個、平面 $n$ 枚が一般の位置にあるとき空間は $\binom n0+\binom n1+\binom n2+\binom n3$ 個の領域に分かれます。
- 平面上のどの 3 点も同一直線上にない 5 点からは、必ず凸四角形をつくる 4 点が選べます（ハッピーエンド問題）。

<Aside type="tip" title="この記事で使う事前知識">

- **集合と部分集合**: ものの集まりを集合といい、集合 $A$ の中身の一部を集めたものを $A$ の部分集合という。→ [部分集合](/mathematics/foundations/sets-and-logic#def-subset)
- **写像（単射・全射・全単射）**: 集合 $X$ の各元に $Y$ の元をひとつ対応させる規則が写像。異なる元が異なる元に写るものが単射、$Y$ のどの元にも写ってくるものが全射、その両方を満たすものが全単射。
- **二項係数**: $n$ 個から $k$ 個を選ぶ選び方の個数を表す $\binom nk$。→ [二項係数](/mathematics/combinatorics/enumeration-generating-functions#def-binomial-coefficient)
- **階乗**: $n!=n(n-1)\cdots2\cdot1$。1 から $n$ までの整数の積。

</Aside>

## 1. 動機

「場合の数」は高校数学で最初に出会う難所です。公式の数は多く、問題ごとに使い分けが違い、数え間違い（重複や漏れ）も起きやすい。しかし公式は互いに無関係ではありません。順列も組合せも円順列も、**「数えやすいものを数えて、重なりの個数で割る」**か**「数えやすい段階に分けて掛ける」**かのどちらかで出てきます。

この記事は、その考え方を最初に定理として固定します。後の記事（確率）では「同様に確からしい事象の確率は、場合の数の比」になるので、数え方が正しいことは確率の正しさに直結します。

注意: 高校の教科書では、これらの公式は「図や例から明らか」とされることが多い。ここでは、段階を分けるとは何か、重ならないとは何か、を集合と写像の言葉で言い切ります。

## 2. 準備：有限集合の元の個数

$\mathbb{N}=\{1,2,\dots\}$、$[n]=\{1,2,\dots,n\}$（$[0]=\varnothing$）とします。

<Definition id="def-cardinality" title="有限集合の元の個数">
集合 $A$ から $[n]$ への全単射があるとき、$A$ は**有限集合**であるといい、その $n$ を $A$ の**元の個数**（要素の個数）といって $|A|$ と書く。空集合の元の個数は $0$ である。
</Definition>

「$n$ は $A$ から決まるか」を確かめておきます。これは鳩の巣原理から出ます。

<Proposition id="prop-card-well-defined" title="元の個数は一意に定まる">
集合 $A$ から $[n]$ への全単射と $[m]$ への全単射があるならば $n=m$ である。
</Proposition>

<Proof of="prop-card-well-defined">
全単射 $\alpha:A\to[n]$、$\beta:A\to[m]$ をとると、$\beta\circ\alpha^{-1}:[n]\to[m]$ は全単射である。$n>m$ とすると、この写像は $[n]$ から元の個数の少ない $[m]$ への単射になり、<Ref to="mathematics/combinatorics/enumeration-generating-functions#thm-pigeonhole" text="鳩の巣原理" />（1 で $k=1$）に反する。同様に逆写像 $\alpha\circ\beta^{-1}:[m]\to[n]$ を考えて $m>n$ も起こらない。よって $n=m$ である。
</Proof>

以下、有限集合を $A,B,\dots$ と書くときは、いつも有限集合を考えます。[部分集合](/mathematics/foundations/sets-and-logic#def-subset) $B\subseteq A$ も有限集合です（$A\to[n]$ の全単射を制限して、順序を詰めれば $B\to[m]$ の全単射が作れるため）。

## 3. 和の法則と積の法則

<Theorem id="thm-sum-product-rules" title="和の法則・積の法則">
1. （和の法則）$A_1,\dots,A_m$ が互いに交わらない有限集合ならば $\bigl|A_1\cup\cdots\cup A_m\bigr|=|A_1|+\cdots+|A_m|$。
2. （積の法則）$|A\times B|=|A|\,|B|$。
3. （逆像が同じ大きさのときの原理）写像 $f:A\to B$ について、すべての $b\in B$ で $|f^{-1}(b)|=c$ （同じ値）ならば $|A|=c\,|B|$。
4. （補集合の原理）$B\subseteq A$ ならば $|A\setminus B|=|A|-|B|$。
</Theorem>

<Proof of="thm-sum-product-rules">
1. まず $m=2$ を示す。$|A|=a$、$|B|=b$、全単射 $\alpha:A\to[a]$、$\beta:B\to[b]$ をとる。$A\cap B=\varnothing$ なので、$\gamma(x)=\alpha(x)$（$x\in A$）、$\gamma(x)=a+\beta(x)$（$x\in B$）で $\gamma:A\cup B\to[a+b]$ が定まり、$[a]$ と $\{a+1,\dots,a+b\}$ に分けて見れば全単射である。よって $|A\cup B|=a+b$。一般の $m$ は、$A_1\cup\cdots\cup A_{m-1}$ と $A_m$ が交わらないことを使った $m$ についての帰納法で出る。
2. $A\times B=\bigcup_{x\in A}\bigl(\{x\}\times B\bigr)$ は互いに交わらない和であり、各 $\{x\}\times B$ は $y\mapsto(x,y)$ で $B$ と全単射だから元の個数 $|B|$ である。1. より $|A\times B|=\sum_{x\in A}|B|=|A|\,|B|$。
3. $A=\bigcup_{b\in B}f^{-1}(b)$ は互いに交わらない和で、各項の元の個数が $c$ なので、1. より $|A|=c\,|B|$。
4. $A=(A\setminus B)\cup B$ は互いに交わらない和なので、1. より $|A|=|A\setminus B|+|B|$。
</Proof>

3. が今回の主役です。「$|A|$ が数えにくいとき、$A$ から数えやすい $B$ への写像 $f$ を作り、各 $b$ の逆像が同じ大きさ $c$ だと示せば、$|A|=c|B|$」という道具です。この記事の定理の多くは、これを使っています。

ここで逆像 $f^{-1}(b)$ とは、$b$ に写る $A$ の元全体の集合のことです。たとえば $A$ を生徒 30 人、$B$ を 5 つのクラス、$f$ を各生徒の所属クラスとします。どのクラスの逆像（そのクラスの生徒全員）も 6 人ならば、全員の数は $6\times5=30$ だと分かります。

<Proposition id="prop-map-count" title="写像の個数">
有限集合 $X,Y$ について、$X$ から $Y$ への写像全体の集合 $Y^X$ の元の個数は $|Y|^{|X|}$ である。$X$ が $k$ 元集合ならば $Y^X$ は直積 $Y^k$ と同一視でき、$|Y^k|=|Y|^k$ である。
</Proposition>

<Proof of="prop-map-count">
$|X|=k$ についての帰納法。$k=0$ のとき、空写像がちょうど 1 つあり $|Y|^0=1$。$k\ge1$ とし、$x_0\in X$ を 1 つ選び $X'=X\setminus\{x_0\}$ とおく。$f\mapsto(f|_{X'},f(x_0))$ は $Y^X$ から $Y^{X'}\times Y$ への全単射である。帰納法の仮定と <Ref to="thm-sum-product-rules" /> の 2. より $|Y^X|=|Y|^{k-1}\cdot|Y|$。
</Proof>

とくに有限集合 $A$ の部分集合は $2^{|A|}$ 個です（<Ref to="mathematics/foundations/sets-and-logic#thm-powerset-card" text="べき集合の元の個数" />）。

<Example id="ex-double-count" title="数え間違いの典型を全単射で直す">
「5 人から委員長 1 人と副委員長 1 人を選ぶ」を、「先に 2 人を選んで（$\binom52=10$）、次に役を決める」と考えると $10\times2=20$ 通り、「先に委員長（5 通り）、次に副委員長（4 通り）」と考えると $5\times4=20$ 通りで一致します。一方、「委員長を 5 通りで決め、副委員長を 5 通りで決める」と数えて 25 通りとするのは、委員長と副委員長が同じ人になる 5 通りを含めた誤りです。
どちらが正しいかは、数えたい集合 $A=\{(x,y):x\neq y\}$ を明示すれば決まります。$A=([5]\times[5])\setminus\{(x,x)\}$ なので、<Ref to="thm-sum-product-rules" /> の 4. から $25-5=20$。「何の集合の元の個数を数えているのか」を書くのが、数え間違いを防ぐ最初の一歩です。
</Example>

## 4. 順列と組合せ

<Definition id="def-injection" title="順列">
$k$ 元集合から $n$ 元集合への単射を、$n$ 個から $k$ 個を取り出す**順列**（正確には $k$ 個の順序つき選び方）といい、その個数を ${}_nP_k$ と書く。$k=n$ の単射（＝全単射）は $n$ 個の並べ替えである。$n!=n(n-1)\cdots2\cdot1$（$0!=1$）。
</Definition>

<Theorem id="thm-permutations" title="順列の個数">
$0\le k\le n$ のとき ${}_nP_k=n(n-1)\cdots(n-k+1)=\dfrac{n!}{(n-k)!}$。$k>n$ のとき ${}_nP_k=0$。とくに $n$ 個の並べ替えは $n!$ 通りである。
</Theorem>

<Proof of="thm-permutations">
$k>n$ のとき、鳩の巣原理（<Ref to="mathematics/combinatorics/enumeration-generating-functions#thm-pigeonhole" />）により単射がない。$k\le n$ とし、$k$ についての帰納法で、「任意の $n$ 元集合 $X$ について、$[k]\to X$ の単射は $n(n-1)\cdots(n-k+1)$ 個」を示す。$k=0$ は空写像 1 個。
$k\ge1$ とする。単射 $f:[k]\to X$ を $f(k)=x$ の値で分類する。$f(k)=x$ となる単射の集合は、$f\mapsto f|_{[k-1]}$ により、$[k-1]\to X\setminus\{x\}$ の単射全体と全単射対応する（$f$ が単射なら $f|_{[k-1]}$ の像は $x$ を含まないから）。$X\setminus\{x\}$ は $n-1$ 元なので、帰納法の仮定でその個数は $(n-1)(n-2)\cdots(n-k+1)$。$x$ は $n$ 通りで、逆像が互いに交わらず元の個数が等しいから <Ref to="thm-sum-product-rules" /> の 1. により、全体は $n\cdot(n-1)\cdots(n-k+1)$ である。
</Proof>

<Theorem id="thm-combinations" title="組合せの個数">
$n$ 元集合の $k$ 元部分集合の個数 $\binom nk$（<Ref to="mathematics/combinatorics/enumeration-generating-functions#def-binomial-coefficient" text="二項係数" />）は、$0\le k\le n$ で
$$
\binom nk=\frac{{}_nP_k}{k!}=\frac{n!}{k!\,(n-k)!}
$$
である。すなわち $k!\binom nk={}_nP_k$。
</Theorem>

<Proof of="thm-combinations">
$n$ 元集合 $X$ について、単射 $f:[k]\to X$ の全体 $I$ から、$k$ 元部分集合の全体 $\mathcal{S}$ への写像 $\Phi(f)=f([k])$ を考える。$\Phi$ は全射である。部分集合 $S$ の逆像 $\Phi^{-1}(S)$ は、$S$ への全単射 $[k]\to S$ 全体であり、その個数は <Ref to="thm-permutations" /> で $k$ 元集合の並べ替えとして $k!$ 個。<Ref to="thm-sum-product-rules" /> の 3. より $|I|=k!\,|\mathcal{S}|$、すなわち ${}_nP_k=k!\binom nk$。後半は <Ref to="thm-permutations" /> から従う（<Ref to="mathematics/combinatorics/enumeration-generating-functions#prop-pascal" /> の閉じた式とも一致する）。
</Proof>

組合せで頻出の対称性 $\binom nk=\binom n{n-k}$ は、「$k$ 個を選ぶ」ことと「選ばない $n-k$ 個を選ぶ」ことの全単射（補集合をとる）です。

<Example id="ex-factorial-size" title="階乗の大きさ">
$10!=3628800$、$20!=2432902008176640000\approx2.4\times10^{18}$、$52!\approx8.07\times10^{67}$。トランプ 52 枚の並べ方の個数は $52!$ で、宇宙の歴史の秒数（約 $4\times10^{17}$）よりはるかに大きい。「全部を書き出して調べる」方法が、場合の数が大きくなると使えないことが分かります。
</Example>

## 5. 円順列・じゅず順列・同じものを含む順列

異なる $n$ 個のものを円形に並べる、回すと一致するものは同じとみなす、という数え方です。座席に番号をつけた並べ方を $\mathbb{Z}_n=\{0,1,\dots,n-1\}$ （$n$ を法とする整数）から物の集合 $X$（$|X|=n$）への全単射 $f$ とし、回転 $\rho(i)=i+1$ に対して $f\sim f\circ\rho^j$ を「同じ円順列」とします。

小さな例で見ると、3 人 A, B, C を円に並べる並べ方は $3!=6$ 通りありますが、回すと重なるもの（ABC, BCA, CAB の 3 つ、ACB, CBA, BAC の 3 つ）を同じとみなすと 2 通りで、$(3-1)!=2$ と合います。以下の証明は「並べ方 $n!$ 通りは、回して重なる $n$ 個ずつの組に分かれる」ことを示して $n$ で割るものです。$\mathbb{Z}_n$ は、$n$ で割った余りで整数を分類したもの、つまり円卓の $n$ 個の席に番号を振ったものと思ってください。

<Theorem id="thm-circular" title="円順列とじゅず順列">
$n\ge1$ 個の異なるものの円順列は $(n-1)!$ 通り。$n\ge3$ のとき、裏返して重なるものも同じとみなす**じゅず順列**は $\dfrac{(n-1)!}{2}$ 通りである。
</Theorem>

<Proof of="thm-circular">
並べ方の全体 $\mathrm{Bij}(\mathbb{Z}_n,X)$ は <Ref to="thm-permutations" /> から $n!$ 個である。
円順列: $f\sim f'$ を $f'=f\circ\rho^j$ となる $j$ があること、と定める。これは[同値関係](/mathematics/foundations/equivalence-relations#def-equivalence)であり（$\rho^j$ の合成と逆が $\rho$ のべきで書ける）、類の個数が答えである。$f$ の類 $\{f\circ\rho^j:0\le j<n\}$ の元の個数は $n$ である：$f\circ\rho^i=f\circ\rho^j$ なら $f$ が単射なので $\rho^i=\rho^j$ で、$i\equiv j\pmod n$ だから、$0\le i,j<n$ では $i=j$。そこで類を対応させる写像の逆像がすべて $n$ 個で、<Ref to="thm-sum-product-rules" /> の 3. により類の個数は $n!/n=(n-1)!$。
じゅず順列: $\sigma(i)=-i$ とおき、$G=\{\rho^j\}\cup\{\sigma\rho^j\}$ とする（$\sigma\rho^j(x)=-(x+j)$）。$G$ は合成で閉じる（$\sigma\rho^j\sigma\rho^k=\rho^{k-j}$ など）。$n\ge3$ のとき $G$ の $2n$ 個の写像は互いに異なる：$\rho^j$ どうし、$\sigma\rho^j$ どうしは異なり、もし $\sigma\rho^j=\rho^i$ なら $x=0,1$ を代入して $-j=i$、$-1-j=1+i$ より $2\equiv0\pmod n$ となって $n\le2$ に反する。$f\sim f'$ を $f'=f\circ g$（$g\in G$）と定めると、類の元の個数は $2n$ なので、類の個数は $n!/(2n)=(n-1)!/2$。
</Proof>

<Theorem id="thm-multiset-permutations" title="同じものを含む順列">
$n=n_1+\cdots+n_r$ とし、$r$ 種類の文字を第 $i$ 種が $n_i$ 個ずつ並べる並べ方（長さ $n$ の列）の個数は
$$
\frac{n!}{n_1!\,n_2!\cdots n_r!}.
$$
</Theorem>

<Proof of="thm-multiset-permutations">
$[n]$ を連続した区間 $B_1,\dots,B_r$（$|B_i|=n_i$）に分ける。$[n]$ の並べ替え $\pi:[n]\to[n]$（全部で $n!$ 個）に、列 $w(\pi)=(w_1,\dots,w_n)$、$w_p=i\iff\pi(p)\in B_i$ を対応させる。$w(\pi)$ は第 $i$ 種が $n_i$ 個の列である。逆に列 $w$ が与えられたとき、$w(\pi)=w$ となる $\pi$ は、各 $i$ について「$w_p=i$ となる位置の集合（$n_i$ 元）から $B_i$ への全単射」を選ぶことと同じなので、$n_1!\cdots n_r!$ 個ある（積の法則）。逆像の大きさが一定だから、<Ref to="thm-sum-product-rules" /> の 3. で列の個数は $n!/(n_1!\cdots n_r!)$。
</Proof>

<Example id="ex-multiset-permutations" title="A, A, B, B, C の並べ替え">
5 文字を並べる並べ方は $\dfrac{5!}{2!\,2!\,1!}=30$ 通り。隣り合う A がないものは、B, B, C の並べ方 $\dfrac{3!}{2!}=3$ 通りの 4 つの隙間から A の位置 2 箇所を選んで $3\times\binom42=18$ 通り。「A が隣り合う」場合は $30-18=12$ 通りで、A, A を 1 つのかたまりにして A', B, B, C を並べる $\dfrac{4!}{2!}=12$ と一致します。
</Example>

## 6. 重複組合せと最短経路

<Theorem id="thm-multichoose" title="重複組合せ">
$n\ge1$、$k\ge0$ のとき、非負整数 $x_1,\dots,x_n$ で $x_1+\cdots+x_n=k$ を満たす組の個数は $\binom{n+k-1}{k}$ である。また、正の整数の解の個数は $\binom{k-1}{n-1}$（$k\ge n$）である。
</Theorem>

証明の方針は、解の組を「$k$ 個の玉と $n-1$ 本の仕切りを一列に並べた、長さ $n+k-1$ の列」に対応させ、仕切りの位置を選ぶ問題（組合せ）に直すことです。$s_i$ は $i$ 番目の仕切りの位置を表します。たとえば $n=3$、$k=2$ で $(x_1,x_2,x_3)=(1,0,1)$ なら、列は「玉 仕切り 仕切り 玉」で、仕切りの位置は $s_1=2$、$s_2=3$ です。

<Proof of="thm-multichoose">
$(x_1,\dots,x_n)$ に対し $s_i=x_1+\cdots+x_i+i$（$1\le i\le n-1$）とおくと、$1\le s_1<s_2<\cdots<s_{n-1}\le n+k-1$（$s_{i+1}-s_i=x_{i+1}+1\ge1$、$s_{n-1}\le k+n-1$）なので、$\{s_1,\dots,s_{n-1}\}$ は $[n+k-1]$ の $(n-1)$ 元部分集合である。逆に $(n-1)$ 元部分集合 $s_1<\cdots<s_{n-1}$ から $x_1=s_1-1$、$x_i=s_i-s_{i-1}-1$（$2\le i\le n-1$）、$x_n=n+k-1-s_{n-1}$ を作ると、これらは非負整数で和は $k$ になり、2 つの操作は互いに逆である。したがって解の個数は $\binom{n+k-1}{n-1}=\binom{n+k-1}{k}$（<Ref to="thm-combinations" /> と $\binom mj=\binom m{m-j}$）。$n=1$ のときは $s$ が空で、解は $x_1=k$ の 1 つだけ（$\binom kk=1$）である。正の解は $y_i=x_i-1$ と置き換えて、$y_1+\cdots+y_n=k-n$ の非負解の個数 $\binom{k-1}{k-n}=\binom{k-1}{n-1}$。
</Proof>

この対応は「玉を $k$ 個、仕切りを $n-1$ 本、並べる」という高校の説明（星と棒）の、数学的な言い直しです。

<Theorem id="thm-lattice-paths" title="最短経路の数">
格子点 $(0,0)$ から $(a,b)$ へ、右（$R$）か上（$U$）への 1 歩ずつで進む経路は $\binom{a+b}{a}$ 通りである。
</Theorem>

<Proof of="thm-lattice-paths">
経路は、$R$ を $a$ 個、$U$ を $b$ 個含む長さ $a+b$ の列と 1 対 1 に対応する。その個数は <Ref to="thm-multiset-permutations" /> で $\dfrac{(a+b)!}{a!\,b!}=\binom{a+b}{a}$。
</Proof>

<Figure caption="格子点 (0,0) から (5,4) への最短経路の 1 つ（太線）。(2,2) を通る経路は 6 × 10 = 60 通り">
<svg viewBox="0 0 320 250" width="100%" role="img" aria-label="格子と最短経路">
  <g stroke="currentColor" stroke-width="0.5" opacity="0.35">
    <line x1="30" y1="210" x2="280" y2="210" /><line x1="30" y1="170" x2="280" y2="170" />
    <line x1="30" y1="130" x2="280" y2="130" /><line x1="30" y1="90" x2="280" y2="90" />
    <line x1="30" y1="50" x2="280" y2="50" />
    <line x1="30" y1="50" x2="30" y2="210" /><line x1="80" y1="50" x2="80" y2="210" />
    <line x1="130" y1="50" x2="130" y2="210" /><line x1="180" y1="50" x2="180" y2="210" />
    <line x1="230" y1="50" x2="230" y2="210" /><line x1="280" y1="50" x2="280" y2="210" />
  </g>
  <polyline points="30,210 80,210 80,170 130,170 130,130 180,130 230,130 230,90 280,90 280,50" fill="none" stroke="var(--sl-color-accent)" stroke-width="3" />
  <circle cx="30" cy="210" r="4" fill="currentColor" /><circle cx="280" cy="50" r="4" fill="currentColor" />
  <circle cx="130" cy="130" r="4" fill="var(--sl-color-accent)" />
  <text x="12" y="226" font-size="12" fill="currentColor">(0,0)</text>
  <text x="258" y="40" font-size="12" fill="currentColor">(5,4)</text>
  <text x="136" y="124" font-size="12" fill="currentColor">(2,2)</text>
</svg>
</Figure>

<Example id="ex-lattice-via" title="途中の点を通る経路">
$(0,0)$ から $(5,4)$ への最短経路は $\binom94=126$ 通り。$(2,2)$ を通るものは、$(0,0)\to(2,2)$ が $\binom42=6$ 通り、$(2,2)\to(5,4)$ が $\binom52=10$ 通りで、積の法則により $60$ 通りです（通る点が 1 つなので、この 60 通りは重なりません）。
</Example>

## 7. 包除原理の使い方：全射と完全順列

包除原理（<Ref to="mathematics/combinatorics/posets-mobius#thm-inclusion-exclusion" />）は、「少なくとも 1 つの条件に反するもの」を「どの条件にも反しないもの」の個数に変換します。ここでは、その使い方を 2 つの定理で見ます。

<Theorem id="thm-surjections" title="全射の個数">
$N\ge1$、$K\ge1$ とする。$[N]$ から $[K]$ への全射の個数は
$$
\sum_{j=0}^{K}(-1)^j\binom Kj(K-j)^N
$$
である。
</Theorem>

<Proof of="thm-surjections">
$X$ を $[N]\to[K]$ の写像全体（<Ref to="prop-map-count" /> で $K^N$ 個）とし、$A_i=\{f\in X:\ i\notin f([N])\}$（$i\in[K]$）とおく。全射の集合は $X\setminus\bigcup_iA_i$ である。$S\subseteq[K]$ について $A_S=\bigcap_{i\in S}A_i$ は $[N]\to[K]\setminus S$ の写像の全体なので $|A_S|=(K-|S|)^N$。<Ref to="mathematics/combinatorics/posets-mobius#thm-inclusion-exclusion" text="包除原理" /> により、全射の個数は $\sum_{S\subseteq[K]}(-1)^{|S|}(K-|S|)^N$。$|S|=j$ となる $S$ は $\binom Kj$ 個なので、題意の式になる。
</Proof>

<Proposition id="prop-derangements" title="完全順列の個数">
$n$ 個の並べ替え $\pi$ で、どの $i$ についても $\pi(i)\ne i$ となるもの（**完全順列**）の個数 $D_n$ は
$$
D_n=n!\sum_{k=0}^n\frac{(-1)^k}{k!}
$$
である。
</Proposition>

<Proof of="prop-derangements">
$X$ を $[n]$ の並べ替え全体（$n!$ 個）、$A_i=\{\pi:\pi(i)=i\}$ とする。$S\subseteq[n]$ について $A_S$ は $S$ の元を固定する並べ替えで、残り $n-|S|$ 個の並べ替えと同一視できるので $|A_S|=(n-|S|)!$（<Ref to="thm-permutations" />）。<Ref to="mathematics/combinatorics/posets-mobius#thm-inclusion-exclusion" text="包除原理" /> により $D_n=\sum_{S}(-1)^{|S|}(n-|S|)!=\sum_{k=0}^n(-1)^k\binom nk(n-k)!=\sum_{k=0}^n(-1)^kn!/k!$。
</Proof>

$D_4=24-24+12-4+1=9$、$D_5=44$、$D_6=265$。比 $D_n/n!$ は $\sum(-1)^k/k!$ に急速に近づきます（確率の記事で再び現れます）。

## 8. 玉と箱の 12 通り

$N$ 個の玉を $K$ 個の箱に入れる入れ方を、次の 3 つの選択で分類します。

- 玉が**区別できるか**（できる＝D、できない＝I）。
- 箱が区別できるか（D か I）。
- 入れ方の条件：制限なし／**単射**（どの箱にも高々 1 個）／**全射**（どの箱にも少なくとも 1 個）。

入れ方を写像 $f:[N]\to[K]$ で表します（玉 $p$ を箱 $f(p)$ に入れる）。玉が区別できないとは、$[N]$ の並べ替えで移り合う写像を同じとみなすこと（各箱の個数 $(n_1,\dots,n_K)$ だけが問題）、箱が区別できないとは、$[K]$ の並べ替えで移り合う写像を同じとみなすことです。

やさしく言えば、「区別できる」とは玉や箱に番号や名前が付いていること、「区別できない」とは見分けがつかず、入れ替えても同じ入れ方だと考えることです。まず $N=2$、$K=2$（制限なし）で見ます。玉 D・箱 D は $2^2=4$ 通り。玉 I・箱 D は箱ごとの個数が $(2,0),(1,1),(0,2)$ の 3 通り。玉 D・箱 I は「2 個が同じ箱」「別々の箱」の 2 通り。玉 I・箱 I は個数の組 $\{2,0\}$ と $\{1,1\}$ の 2 通りです。以下の定理は、これを一般の $N,K$ で数えたものです。

<Definition id="def-stirling-partition" title="第 2 種 Stirling 数と整数の分割">
1. $N$ 元集合を、空でない部分集合（**ブロック**）に、順序を区別せずに互いに交わらないように分割する分け方のうち、ブロックがちょうど $K$ 個のものの個数を**第 2 種 Stirling 数** $S(N,K)$ とする（$S(0,0)=1$、$N\ge1$ で $S(N,0)=0$、$K\ge1$ で $S(0,K)=0$）。
2. 自然数 $N$ を、順序を区別せずにちょうど $K$ 個の正の整数の和として表す表し方（$N=n_1+\cdots+n_K$、$n_1\ge\cdots\ge n_K\ge1$）の個数を $p_K(N)$ とする（$p_0(0)=1$、$m\ge1$ で $p_0(m)=0$、$p_K(0)=0$ ($K\ge1$)）。
</Definition>

<Proposition id="prop-stirling-recurrence" title="Stirling 数と分割数の漸化式">
$N,K\ge1$ について
$$
S(N,K)=S(N-1,K-1)+K\,S(N-1,K),\qquad p_K(N)=p_{K-1}(N-1)+p_K(N-K).
$$
ただし $p_K(m)=0$（$m<0$）とする。
</Proposition>

<Proof of="prop-stirling-recurrence">
$S$ の漸化式: $[N]$ の $K$ ブロックへの分割を、元 $N$ が単独のブロックをなすかどうかで分ける。単独なら、残りは $[N-1]$ の $K-1$ ブロックへの分割で、$S(N-1,K-1)$ 通り。そうでなければ、$N$ を除いた $[N-1]$ の $K$ ブロックへの分割に、$N$ を $K$ 個のブロックのどれかに加える $K$ 通りで、$K\,S(N-1,K)$ 通り（逆に $N$ を除けば元に戻る）。
$p$ の漸化式: $K$ 個の正の整数への分割を、最小の項が $1$ かどうかで分ける。最小の項が $1$ なら、その 1 を除いて $N-1$ の $K-1$ 個への分割になる（逆に $1$ を加えれば元に戻る）。最小の項が $2$ 以上なら、すべての項から $1$ を引いて $N-K$ の $K$ 個への分割になる（逆に $1$ ずつ加えれば元に戻る）。それぞれ $p_{K-1}(N-1)$、$p_K(N-K)$ 通り。
</Proof>

<Theorem id="thm-twelvefold" title="12 通りの数え方">
$N,K\ge1$ とする。玉の入れ方の個数は、次の表のとおりである。

| | 制限なし | 単射（各箱に高々 1 個） | 全射（各箱に 1 個以上） |
|---|---|---|---|
| 玉 D・箱 D | $K^N$ | $\dfrac{K!}{(K-N)!}$（$N\le K$、それ以外は $0$） | $K!\,S(N,K)=\sum_{j=0}^K(-1)^j\binom Kj(K-j)^N$ |
| 玉 I・箱 D | $\binom{N+K-1}{N}$ | $\binom KN$（$N\le K$、それ以外は $0$） | $\binom{N-1}{K-1}$ |
| 玉 D・箱 I | $\sum_{j=1}^{K}S(N,j)$ | $1$（$N\le K$）、$0$（$N>K$） | $S(N,K)$ |
| 玉 I・箱 I | $\sum_{j=1}^{K}p_j(N)$ | $1$（$N\le K$）、$0$（$N>K$） | $p_K(N)$ |
</Theorem>

<Proof of="thm-twelvefold">
同一視の確認: 2 つの写像 $f,g$ が、玉の並べ替え $\pi$ と箱の並べ替え $\tau$ を許して $g=\tau\circ f\circ\pi$ と移り合うことを、玉が区別できなければ $\pi$ だけ、箱が区別できなければ $\tau$ だけ許して、「同じ入れ方」とみなす。各箱の個数 $(n_j)=(|f^{-1}(j)|)$ が一致すれば玉の並べ替えで移り合い（各箱の玉を同じ個数ずつ対応させればよい）、$f$ の逆像のつくる $[N]$ の分割（空でない逆像の全体）が一致すれば、空でない逆像どうしを対応させる箱の並べ替え（空の箱どうしも対応させて $[K]$ 全体の並べ替えに延ばせる）で移り合う。逆も明らかなので、以下の同一視は次の 3 つの言い換えになる：玉 I・箱 D は各箱の個数の組 $(n_1,\dots,n_K)$、玉 D・箱 I は $[N]$ の（高々 $K$ ブロックの）分割、玉 I・箱 I は個数の組を並べ替えて同じとみなしたもの、すなわち $N$ の分割。
**玉 D・箱 D**: 入れ方は写像 $[N]\to[K]$ そのもの。制限なしは <Ref to="prop-map-count" /> で $K^N$。単射は <Ref to="thm-permutations" />（$N\le K$、$N>K$ は鳩の巣原理で 0）。全射の個数は <Ref to="thm-surjections" /> の式に一致する。さらに全射 $f$ に、その逆像の分割 $\{f^{-1}(b)\}$（$K$ 個のブロック）を対応させると、全射の集合から「$K$ ブロックの分割」の集合への全射になり、1 つの分割の逆像は、$K$ 個のブロックに箱の名前 $1,\dots,K$ を 1 つずつ割り当てる方法の個数 $K!$ に等しい。<Ref to="thm-sum-product-rules" /> の 3. より全射の個数は $K!\,S(N,K)$。
**玉 I・箱 D**: 入れ方は各箱の個数 $(n_1,\dots,n_K)$（$n_1+\cdots+n_K=N$）。制限なしは <Ref to="thm-multichoose" /> で $\binom{N+K-1}{N}$。全射は $n_j\ge1$ なので正の解の個数 $\binom{N-1}{K-1}$。単射は $n_j\in\{0,1\}$ で和が $N$ なので、1 が入る $N$ 個の箱の選び方 $\binom KN$（<Ref to="thm-combinations" />）。
**玉 D・箱 I**: 入れ方は箱の名前を忘れた「玉の集合 $[N]$ の分割」（空の箱は見えない）。ブロックの個数 $j$ は $1\le j\le K$ で、制限なしは $\sum_{j=1}^KS(N,j)$。全射は空の箱がないことで、ちょうど $K$ ブロック、$S(N,K)$。単射はすべてのブロックが 1 個の玉だけからなる分割で、そのような分割はちょうど 1 つあり（$N\le K$）、$N>K$ では箱が足りず 0。
**玉 I・箱 I**: 入れ方は箱の個数を並べた多重集合、すなわち $N$ の分割（空の箱は見えない）。ちょうど $j$ 個の正の整数への分割が $p_j(N)$ 個なので、制限なしは $\sum_{j=1}^Kp_j(N)$、全射は $p_K(N)$。単射は全部の項が 1 の分割ただ 1 つ（$N\le K$）、$N>K$ では 0。
</Proof>

<Example id="ex-twelvefold-n4k3" title="$N=4$、$K=3$ の表">
値を計算すると次のとおり。$S(4,1)=1$、$S(4,2)=7$、$S(4,3)=6$。$p_1(4)=1$、$p_2(4)=2$、$p_3(4)=1$。

| | 制限なし | 単射 | 全射 |
|---|---|---|---|
| 玉 D・箱 D | $81$ | $0$ | $36$ |
| 玉 I・箱 D | $15$ | $0$ | $3$ |
| 玉 D・箱 I | $14$ | $0$ | $6$ |
| 玉 I・箱 I | $4$ | $0$ | $1$ |

$4$ 個の玉を $3$ 個の箱に入れて空の箱を許さないと、玉 D・箱 D で $36$ 通り。これは $3!\,S(4,3)=6\times6$ とも、$3^4-3\cdot2^4+3=36$ とも合います。
</Example>

## 9. 平面と空間の分割

直線 $n$ 本で平面はいくつの領域に分かれるでしょうか。直観的な数え方（「新しい直線は $n$ 個の交点で $n+1$ 個に切れ、領域が $n+1$ 個増える」）を、定義から証明します。

$d=1,2,3$ とし、$\mathbb{R}^d$ の**超平面** $H_i=\{g_i=0\}$（$g_i$ は定数でない 1 次式。$d=1$ は点、$d=2$ は直線、$d=3$ は平面）を $n$ 個とります（超平面とは、直線や平面のように、空間を 2 つの側に分ける平らな図形のことです）。符号の組 $\varepsilon\in\{+1,-1\}^n$ に対し $R_\varepsilon=\{x:\varepsilon_ig_i(x)>0\ (i=1,\dots,n)\}$ とおき、空でない $R_\varepsilon$ を（これら $n$ 個の超平面が作る）**領域**、その個数を $r_d(H_1,\dots,H_n)$ と書きます。$R_\varepsilon$ は有限個の開半空間の共通部分なので凸であり、異なる領域は超平面で隔てられます。

<Definition id="def-general-position" title="一般の位置">
$d=2$ の直線 $n$ 本が**一般の位置**にあるとは、どの 2 本も平行でなく、どの 3 本も 1 点で交わらないこと。$d=3$ の平面 $n$ 枚が一般の位置にあるとは、どの 2 枚も平行でなく（一致もせず）、どの 3 枚もちょうど 1 点で交わり、どの 4 枚も共通点をもたないこと。$d=1$ では $n$ 個の点が互いに異なること。
</Definition>

次の補題は、直線を 1 本足すと、領域が「その直線が通り抜ける領域の数」だけ増える、という事実を式にしたものです。たとえば 2 本の直線が作る 4 個の領域に、その 2 本と交わる 3 本目を引くと、3 本目は 2 つの交点で 3 つの区間に切られ、3 個の領域を通り抜けるので、領域は $4+3=7$ 個になります（公式 $1+3+\binom32=7$ と一致します）。証明では、領域が凸（領域内の 2 点を結ぶ線分が領域からはみ出さない）という性質を使います。

<Lemma id="lem-add-hyperplane" title="超平面を 1 つ加えたときの領域の増え方">
$H=\{g=0\}$ を新しい超平面とし、$H_1,\dots,H_n$ のどれとも平行でない（$H\cap H_i\ne\varnothing$、$H_i\neq H$）とする。$H_i\cap H$ は $H$ の中の超平面（$d=2$ なら点、$d=3$ なら直線）である。このとき
$$
r_d(H_1,\dots,H_n,H)=r_d(H_1,\dots,H_n)+r_{d-1}\bigl(H\cap H_1,\dots,H\cap H_n\bigr)
$$
（右辺の第 2 項は、$H$ の中で $H\cap H_i$ が作る領域の個数）。
</Lemma>

<Proof of="lem-add-hyperplane">
$H_1,\dots,H_n$ の領域 $R_\varepsilon\ne\varnothing$ を 1 つ取り、$H$ との関係で調べる。
(a) $R_\varepsilon\cap H=\varnothing$ のとき。$R_\varepsilon$ は凸で、$g$ は連続（1 次式）なので、$g$ は $R_\varepsilon$ 上で符号を変えない（$g(p)>0>g(q)$ なら線分 $pq$ 上で $g=0$ となる点が $R_\varepsilon$ にあることになるため）。よって新しい領域のうち $R_\varepsilon$ の中にあるものは、$g>0$ の側か $g<0$ の側かのちょうど一方で、1 個。
(b) $R_\varepsilon\cap H\ne\varnothing$ のとき。$p\in R_\varepsilon\cap H$ をとると $R_\varepsilon$ は開集合なので $p$ のまわりの小球を含み、その小球は $g>0$ の点も $g<0$ の点も含む。よって新しい領域が 2 個。
したがって増える領域の数は、$H$ に交わる $R_\varepsilon$ の個数である。$R_\varepsilon\cap H=\{x\in H:\varepsilon_ig_i(x)>0\}$ で、$g_i|_H$ は仮定より $H$ 上の定数でない 1 次式（$H_i$ が $H$ と平行でないため）であり、その零点集合が $H\cap H_i$ である。よって $R_\varepsilon\cap H\ne\varnothing$ となる $\varepsilon$ の個数は、$H$ の中の超平面 $H\cap H_i$ の領域の個数に等しい。
</Proof>

<Theorem id="thm-plane-division-lines" title="直線と平面による分割">
一般の位置にある $n$ 個の超平面について、領域の個数は
$$
r_d=\sum_{j=0}^{d}\binom nj\qquad(d=1,2,3)
$$
である。とくに、一般の位置にある直線 $n$ 本は平面を $1+n+\binom n2=\dfrac{n^2+n+2}{2}$ 個の領域に分け、一般の位置にある平面 $n$ 枚は空間を $1+n+\binom n2+\binom n3$ 個の領域に分ける。
</Theorem>

<Proof of="thm-plane-division-lines">
$d=1$: 相異なる $n$ 点 $t_1<\cdots<t_n$ を零点とする 1 次式の符号の組は、$t$ より小さい点の個数 $0,1,\dots,n$ で決まり、どれも実現されるので $n+1=\binom n0+\binom n1$ 個。
$d=2,3$: $n$ についての帰納法。$n=0$ なら領域は全空間 1 個で $\binom00=1$。$n\ge1$ とし、$H=H_n$ を最後に加える超平面とみなす。一般の位置の仮定より、$H$ は他の超平面と平行でない（$d=2$：どの 2 本も平行でない。$d=3$：定義でどの 2 枚も平行でも一致でもない。$n\le2$ のときも、この条件が要る）。また $H\cap H_1,\dots,H\cap H_{n-1}$ は $H$ の中で一般の位置にある（$d=2$：$n-1$ 個の相異なる点。2 直線 $H_i,H_j$ が $H$ 上の同じ点で交われば 3 本が共点になってしまう。$d=3$：$H$ の中の 2 直線 $H\cap H_i,H\cap H_j$ は $H\cap H_i\cap H_j$ がちょうど 1 点なので、ちょうど 1 点で交わり、3 直線が共点なら $H$ を含む 4 枚が共点になって矛盾）。<Ref to="lem-add-hyperplane" /> により $r_d(n)=r_d(n-1)+r_{d-1}(n-1)$。帰納法の仮定（$d-1$ については $n-1$ 個で、$d$ については $n-1$ 個で成り立つ）から
$$
r_d(n)=\sum_{j=0}^d\binom{n-1}{j}+\sum_{j=0}^{d-1}\binom{n-1}{j}=\binom{n-1}0+\sum_{j=1}^d\Bigl[\binom{n-1}{j}+\binom{n-1}{j-1}\Bigr]=\sum_{j=0}^d\binom nj.
$$
最後は Pascal の漸化式（<Ref to="mathematics/combinatorics/enumeration-generating-functions#prop-pascal" />）である。
</Proof>

<Example id="ex-cake-numbers" title="平面 4 枚で空間は 15 個">
平面 $n=1,2,3,4,5$ 枚で空間は $2,4,8,15,26$ 個の領域に分かれます。$2^n$ に見えて、$n=4$ で $16$ ではなく $15$ になります。平行な 2 本の直線は 3 個にしか平面を分けない（$1+2+1=4$ の公式より少ない）ように、一般の位置からずれると個数は減ります（平行な平面 2 枚が空間を 3 個にしか分けないのも同じです）。
</Example>

<Remark id="rem-circles-division">
円による平面の分割（どの 2 円もちょうど 2 点で交わり、どの 3 円も共有点をもたない場合、$n^2-n+2$ 個）は、領域が凸でないので上の議論はそのまま使えません。[平面グラフ](/mathematics/math-columns/famous-mathematicians#def-planar)の Euler の公式 $V-E+F=2$ を使うと証明できます（Euler の公式は <Ref to="mathematics/math-columns/four-color-theorem#prop-euler" /> にあります）。ただし、辺が曲線なので、直線の場合にはない Jordan の曲線定理の類の議論が要ります。この記事は証明を与えないため、定理にはせず、公式だけを注意として記します。
</Remark>

## 10. ハッピーエンド問題（5 点）

平面上の 4 点が**凸位置**にあるとは、どの 1 点も他の 3 点がつくる三角形（内部と周を含む）に含まれないことです。このとき 4 点は凸四角形の頂点をなします。

平面上の有限個の点 $S$ について、$S$ の点の**凸結合**（$\sum\lambda_sP_s$、$\lambda_s\ge0$、$\sum\lambda_s=1$）全体を $\mathrm{conv}(S)$ と書きます（$S$ を含む最小の[凸集合](/mathematics/hs-geometry/plane-vectors#def-convex)、つまり「$S$ を囲む輪ゴムの内側」です）。

<Lemma id="lem-minimal-hull" title="凸包をつくる最小の点集合">
有限集合 $S$ に対し、部分集合 $T\subseteq S$ で、$\mathrm{conv}(T)=\mathrm{conv}(S)$ であり、かつ $T$ のどの点 $P$ も $\mathrm{conv}(T\setminus\{P\})$ に含まれないものが存在する。
</Lemma>

<Proof of="lem-minimal-hull">
$\mathrm{conv}(T)=\mathrm{conv}(S)$ となる $T\subseteq S$ のうち、元の個数が最小のものをとる（$T=S$ が候補なので存在する）。もし $P\in T$ が $\mathrm{conv}(T\setminus\{P\})$ に含まれるなら、$T$ の点の凸結合に現れる $P$ を $T\setminus\{P\}$ の凸結合で置き換えることで $\mathrm{conv}(T\setminus\{P\})=\mathrm{conv}(T)=\mathrm{conv}(S)$ となり、$T$ の最小性に反する。
</Proof>

<Theorem id="thm-happy-ending" title="ハッピーエンド問題（5 点）">
平面上の 5 点で、どの 3 点も同一直線上にないものは、4 点を選んで凸位置にできる（凸四角形をつくれる）。
</Theorem>

証明の方針は、5 点を輪ゴムで囲んだとき、輪ゴムの角になる点だけを残した集合 $T$ の大きさで分けることです。$T$ が 4 点以上ならそこから 4 点を選べば済みます。$T$ が 3 点（三角形）のときは、残りの 2 点が三角形の内側にあることを使い、2 点を通る直線が三角形の頂点を 1 点と 2 点に分けることから、凸位置の 4 点を見つけます。

<Proof of="thm-happy-ending">
5 点の集合を $S$ とし、<Ref to="lem-minimal-hull" /> の $T$ をとる。$|T|\le2$ だと $S\subseteq\mathrm{conv}(S)=\mathrm{conv}(T)$ が 1 本の線分に入り、3 点共線に反する。よって $|T|\ge3$。
$|T|\ge4$ のとき: $T$ から 4 点を選ぶ。どの点 $P$ も $P\notin\mathrm{conv}(T\setminus\{P\})$ であり、他の 3 点の三角形はこの凸包に含まれるから、$P$ は他の 3 点の三角形に入らない。よって凸位置。
$|T|=3$ のとき: $T=\{A,B,C\}$（3 点共線でないので三角形をなす）、$S$ の残りを $D,F$ とおく。$D,F\in\mathrm{conv}(S)=\mathrm{conv}(A,B,C)$ で、$D,F$ は $A,B,C$ のどれとも異なる。
(i) 直線 $DF$ は $A,B,C$ のどれも通らない（3 点共線に反する）。$g$ を直線 $DF$ を零点とする 1 次式とすると、$g(A),g(B),g(C)\neq0$。3 つが全部同符号だとすると、その凸結合である $g(D)$ も $0$ でなくなり $g(D)=0$ に反する。よって符号は 2 対 1 に分かれる。$A$ だけが別の側、$B,C$ が同じ側とする（他の場合は文字を入れ替える）。
(ii) $B\notin\mathrm{conv}(C,D,F)$ である。$A,B,C$ は 1 直線上にないので、$\beta(A)=\beta(C)=0$、$\beta(B)=1$ となる 1 次式 $\beta$ がある。$\mathrm{conv}(A,B,C)$ の点では $\beta$ の値は凸結合における $B$ の重みなので $0\le\beta\le1$ で、$\beta(X)=1$ となるのは $X=B$ のときに限る。もし $B=\lambda C+\mu D+\nu F$（$\lambda,\mu,\nu\ge0$、和は 1）なら $1=\beta(B)=\mu\beta(D)+\nu\beta(F)$ だが、$\beta(D),\beta(F)<1$ なので右辺は $\mu+\nu\le1$ 未満（$\mu=\nu=0$ なら $0$）で矛盾する。同様に $C\notin\mathrm{conv}(B,D,F)$。
(iii) $D\notin\mathrm{conv}(B,C,F)$ である。もし $D\in\mathrm{conv}(B,C,F)$ なら、3 点共線がないので $D=\lambda B+\mu C+\nu F$（$\lambda,\mu,\nu>0$、和は 1）と書け、$D-F=\lambda(B-F)+\mu(C-F)$。$g(x)=\ell(x)+c$（$\ell$ は 1 次の部分）とすると $\ell(D-F)=g(D)-g(F)=0$ なので $0=\lambda\ell(B-F)+\mu\ell(C-F)=\lambda g(B)+\mu g(C)$（$g(F)=0$）。$\lambda,\mu>0$ なので $g(B),g(C)$ は異符号になり、$B,C$ が同じ側という (i) に反する。$F\notin\mathrm{conv}(B,C,D)$ も同様。
(ii)(iii) より $B,C,D,F$ は凸位置である。
</Proof>

<Remark id="rem-erdos-szekeres">
一般に、どの 3 点も同一直線上にない $2^{m-2}+1$ 個の点は $m$ 角形の凸位置の部分集合を含む、というのが Erdős–Szekeres 予想です。$m=4$（5 点）は上の定理で、$m=5$（9 点）と $m=6$（17 点）でも成り立つことが知られています。一般の $m$ については $2^{m+o(m)}$ の上界が知られている段階です（Suk, "On the Erdős–Szekeres convex polygon problem", *J. Amer. Math. Soc.* 30 (2017)）。予想の全体は未解決のため、ここでは定理にしません。
</Remark>

## 11. 大学ではどこへ続くか

- [母関数](/mathematics/hs-algebra/recurrences-generating-functions#def-generating-function)（形式的冪級数）による数え上げ、指数公式、Lagrange 反転と Cayley の木の公式は [数え上げと母関数](/mathematics/combinatorics/enumeration-generating-functions)、包除原理の一般化（半順序集合上の Möbius 反転）は [半順序集合と Möbius 反転](/mathematics/combinatorics/posets-mobius) で学びます。
- 12 通りの数え方は、対称群の作用による軌道の個数の問題に一般化されます（Burnside の補題・Pólya の数え上げ）。
- 平面や空間の超平面配置の領域の個数は、超平面配置の特性多項式と Möbius 関数で一般に表されます（Zaslavsky の定理）。
- ハッピーエンド問題は組合せ幾何と Ramsey 型の問題の入口です。

## 12. 演習

<Exercise id="exr-circle-alternate" difficulty="易">
男子 4 人、女子 4 人が円形のテーブルに座る。回転して一致するものは同じとみなす。男女が交互に座る座り方は何通りか。
<Solution>
先に男子 4 人の円順列（<Ref to="thm-circular" />）を決める。$(4-1)!=6$ 通り。男子の間の 4 つの空き席に女子を並べる並べ方は $4!=24$ 通り。男子を先に固定した時点で回転が消えているので、積の法則で $6\times24=144$ 通り。
</Solution>
</Exercise>

<Exercise id="exr-nonneg-solutions" difficulty="標準">
$x_1+x_2+x_3+x_4=10$ を満たす非負整数の組のうち、$x_1\ge2$ かつ $x_2\ge1$ を満たすものは何個あるか。
<Solution>
$y_1=x_1-2$、$y_2=x_2-1$ と置くと、$y_1,y_2,x_3,x_4\ge0$ で $y_1+y_2+x_3+x_4=7$。<Ref to="thm-multichoose" /> より $\binom{7+4-1}{7}=\binom{10}{3}=120$ 個。
</Solution>
</Exercise>

<Exercise id="exr-surjection-count" difficulty="標準">
区別できる 5 個の玉を、区別できる 3 個の箱に、空の箱がないように入れる入れ方は何通りか。また箱を区別しない場合は何通りか。
<Solution>
<Ref to="thm-surjections" /> から $3^5-3\cdot2^5+3\cdot1^5-0=243-96+3=150$ 通り。箱を区別しないと、<Ref to="thm-twelvefold" /> の（玉 D・箱 I）全射の欄から $S(5,3)=150/3!=25$ 通り。
</Solution>
</Exercise>

<Exercise id="exr-planes-count" difficulty="標準">
一般の位置にある平面 $5$ 枚が空間を分ける領域の個数を求めよ。
<Solution>
<Ref to="thm-plane-division-lines" /> から $1+5+\binom52+\binom53=1+5+10+10=26$ 個。
</Solution>
</Exercise>

## 参考文献

1. Ronald L. Graham, Donald E. Knuth, Oren Patashnik, *Concrete Mathematics*, 2nd ed., Addison-Wesley, 1994 — 第 5 章（二項係数）、第 6 章（Stirling 数）。
2. Richard P. Stanley, *Enumerative Combinatorics, Volume 1*, 2nd ed., Cambridge University Press, 2012 — 第 1 章（玉と箱の 12 通りの数え方 §1.9）。
3. Martin Aigner, Günter M. Ziegler, *Proofs from THE BOOK*, Springer — 鳩の巣原理と二重の数え上げ、Erdős–Szekeres の章。
4. Jiří Matoušek, *Lectures on Discrete Geometry*, Springer, 2002 — 超平面配置と凸位置の点の章。
5. W. Morris, V. Soifer, "The Erdős–Szekeres problem on points in convex position — a survey", *Bull. Amer. Math. Soc.* 37 (2000).