分野: 場合の数


包除原理:
$|A\cup B|=|A|+|B|-|A\cap B|$
$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|B\cap C|-|C\cap A|+|A\cap B\cap C|$
$|A_1\cup A_2\cup\cdots\cup A_n|=\displaystyle\sum_{k=1}^n(-1)^{k-1}$ ($k$ 個の「かつ」の総和)
$=\displaystyle\sum_{i}|A_i|-\sum_{i < j}|A_i\cap A_j|
+\sum_{i < j < k}|A_i\cap A_j\cap A_k|-\cdots +(-1)^{n-1}|A_1\cap\cdots\cap A_n|$


$1, 2,\cdots, n$ を並び替えてできる順列のうち,全ての $i=1, 2, \cdots, n$ に対して $i$ 番目が $i$ でないものの個数 $a_n$ は,以下の式で表される:
$a_n=n!\displaystyle\sum_{k=2}^n\dfrac{(-1)^k}{k!}$


ヴァンデルモンドの畳み込み:
以下の恒等式が成立する:
$\displaystyle\sum_{k=0}^n{}_p\mathrm{C}_k\cdot {}_q\mathrm{C}_{n-k}={}_{p+q}\mathrm{C}_n$
ただし,$p < k$ のとき${}_p\mathrm{C}_k=0$ と約束する。


1987年国際数学オリンピックキューバ大会の第一問の2通りの解法を紹介します。

問題

$p_n(k)$ を不動点をちょうど $k$ 個持つ $n$ 次の置換の数とする。
このとき,$\displaystyle\sum_{k=0}^nk\cdot p_n(k)=n!$ を証明せよ。

ただし,$n$ 次の置換とは,集合 $S=\{1,2,\cdots,n\}$ から $S$ への一対一対応であり,$f(i)=i$ を満たすとき $i$ を置換 $f$ の不動点と呼ぶ。


$n$ 人を区別のある(ちょうど)$k$ 個のチームに分ける場合の数は,
$\displaystyle\sum_{i=1}^k(-1)^{k-i}{}_kC_{i}i^n$

$k=2,\:3$ の問題は大学入試として適度な難易度です。覚える必要はありませんが,導出できるようになっておきましょう。


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

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


Erdos-Ko-Radoの定理:$n$ 個の要素からなる集合 $\{1,2,\cdots,n\}$ から要素数が $k$ の部分集合たちを以下の条件を満たすようにできるだけたくさん選びたい。
条件:選んだ部分集合のどの二つを選んでも共通元が存在する。
$n\geq 2k$ のとき,選べる部分集合の限界 $N$ は,$N={}_{n-1}C_{k-1}$ 個である。

組み合わせの有名な定理です。証明は数学オリンピックの練習問題としては難し目ですが,非常にエレガントです。


Erdos–Szekeresの定理:$a,b$ を正の整数とする。各項が相異なる長さ $ab+1$ の数列があるとき,以下の二つのうち少なくとも一つは必ず存在する。
1:長さ $a+1$ の部分列で,単調増加なもの
2:長さ $b+1$ の部分列で,単調減少なもの


定期試験や入試で頻出の「道順の場合の数を求める問題(最短経路問題)」について。有名なテクニックである書き込み方式について解説します。漸化式を使って場合の数を求める,動的計画法の入り口。


確率 $\dfrac{1}{2}$ で$+1$ ポイント,$\dfrac{1}{2}$ で$-1$ ポイントとなるゲームを繰り返すような確率モデルを一次元ランダムウォークと言う。

ランダムウォークは入試にも頻繁に登場する&現実の様々な現象の記述に使える重要なモデルです。


$\mathcal{F}$ を $E=\{e_1,\dots,e_n\}$ の部分集合族とする。
$E$ の各要素 $e_i$ に重み $w(e_i)$ を割り当てる。 $w(e_i)$ はそれぞれ独立に $\{1,\dots,N\}$ の中から一様ランダムに選ぶ。

$F\in \mathcal{F}$ の重みを $w(F)=\displaystyle\sum_{e\in F}w(e)$ と定義する。

このとき,確率 $1-\dfrac{n}{N}$ 以上で $\mathcal{F}$ の要素の中で重みを最小にするものはただ一つである。


多項定理:
$(x_1+x_2+\cdots +x_k)^n$ を展開したときの $x_1^{e_1}x_2^{e_2}\cdots x_k^{e_k}$ の係数は
$e_1+e_2+\cdots +e_k=n$ かつ各 $e_i$ が非負なら $\dfrac{n!}{e_1!e_2!\cdots e_k!}$
(そうでないなら $0$)

多項定理は二項定理の拡張です($k=2$ のときは二項定理)。前半は具体例,後半は証明です。