組合せ論

組合せ論（combinatorics）

前提知識：階乗

\(1\)から\(n\)までのすべての整数の積のことを \(n\) の 階乗（factorial） と呼び、\(n!\)と表す。

\[ n! = \prod_{k=1}^n k = n \times (n-1) \times \cdots \times 3 \times 2 \times 1 \]

なお、実用性の関係上、ゼロについては\(0! =1\)と定める。

置換

置換

\(n\)個の要素をもつ集合の並べ替えのパターン数を 置換 (permutation) といい、\(n!\)で求めることができる。

例えば、集合 \(\{1, 2, 3\}\) の置換は、

\[ (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1) \]

の6パターンとなる。

一般に\(n!\)個になる。

順列

順列

\(n\)個のものから\(r\)個を取り出して並べる並べ方のパターン数を 順列 (partial permutation, sequence without repetition) といい\({}_{n}P_{r}\)と表す。また以下の式で計算できる

\[ {}_{n}P_{r} = \frac{n!}{(n-r)!} \]

例：トランプのカードの並べ方は何通りあるか？

52枚あるので、52枚から52枚を取り出して並べることになる

\[ {}_{52}P_{52} = \frac{52!}{0!} = 52! \approx 8.065817517094 \times 10^{67} \]

これは 無量大数（\(10^{68}\)）に近い大きさになる

組み合わせ

組み合わせ

\(n\)個のものから\(r\)個を取り出す組み合わせのパターン数のことを 組み合わせ (combination, choose) といい\({}_{n}C_{r}\) や \(\binom{n}{r}\)と表す。また以下の式で計算できる

\[ {}_{n}C_{r} = \binom{n}{r} = \frac{n!}{r!(n-r)!} \]

実用的な覚え方

例えば\({}_{5}C_{3}\)だと \(3 \times 2 \times 1\) が分母と分子の両方に出てくるので

\[ {}_{5}C_{3} = \frac{5!}{3!(5-3)!} = \frac{5\times 4 \times 3 \times 2 \times 1}{3\times 2\times 1 \times 2 \times 1} = \frac{5\times 4}{2 \times 1} \]

と簡略化できる。つまり

\[ {}_{5}C_{3} = \frac{5から2個の数を降順に掛けた数}{2!} \]

であり、一般化すると

\[ {}_{n}C_{r} = \frac{nから(n-r)個の数を降順に掛けた数}{(n-r)!} \]

逆の数

\[\begin{split} {}_{5}C_{3} = \frac{5\times 4}{2 \times 1}\\ {}_{5}C_{2} = \frac{5\times 4 \times 3}{3 \times 2 \times 1} \end{split}\]

なので\({}_{5}C_{3} = {}_{5}C_{2}\)となる。

「5個から3個を取り出す」と「5個から2個を残す」が表裏一体でありパターン数がおなじになるため。

同様に

\[\begin{split} {}_{n}C_{0} = \frac{n!}{0!(n-0)!} = \frac{n!}{0!n!} = 1 \\ {}_{n}C_{n} = \frac{n!}{n!(n-n)!} = \frac{n!}{n!0!} = 1 \end{split}\]

で\({}_{n}C_{0} = {}_{n}C_{n}\)となるが、これも「\(n\)個から\(n\)個を取り出す」と「\(n\)個から\(0\)個を残す」が同じのため。そしてこれらは1通りしかパターンがないので1になる。

（参考）二項定理

二項式（2つの単項式の和；例えば\(ax^m + by^n\)（\(a,b,x,y\in\mathbb{R}, n,m\in\mathbb{N}\)）のような式）の冪乗を展開したものを 二項展開 と呼ぶ。

例えば\(x + y\)は

\[\begin{split} \begin{aligned} (x + y)^2 &= (x + y) (x + y) \\ &= x^2 + 2xy + y^2\\ (x + y)^3 &= (x + y)^2 (x + y) = (x^2 + 2xy + y^2)(x + y) \\ &= x^3 + 3 x^2 y + 3xy^2 + y^3\\ &~ \vdots \end{aligned} \end{split}\]

というふうに展開できる。これら二項展開の中に出てくる係数を 二項係数 とよび、組み合わせの数に等しいので\({}_{n}C_{r}\) や \(\binom{n}{r}\)と表す。

例：

\[\begin{split} \begin{aligned} (x + y)^2 &= x^2 + 2xy + y^2\\ &= \binom{2}{0} x^2 + \binom{2}{1} x y + \binom{2}{2} y^2\\ &= \sum^2_{r=0} \binom{2}{r} x^{2 - r} y^{r} \end{aligned} \end{split}\]

一般には以下の 二項定理 (binomial theorem) で表される。

二項定理

\[ (x+y)^n = \sum^n_{r=0} \binom{n}{r} x^{n-r} y^r \]

他の例：

\[\begin{split} (1+x)^n=\binom{n}{0}+\binom{n}{1} x^1+\binom{n}{2} x^2+\cdots+\binom{n}{n-1} x^{n-1}+\binom{n}{n} x^n=\sum_{k=0}^n\binom{n}{k} x^k \\ (x+y)^n=\binom{n}{0} x^n+\binom{n}{1} x^{n-1} y^1+\binom{n}{2} x^{n-2} y^2+\cdots+\binom{n}{n-1} x^1 y^{n-1}+\binom{n}{n} y^n \end{split}\]