組合せ論

組合せ論#

組合せ論（combinatorics）

前提知識：階乗

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

n! = \prod_{k = 1}^{n} k = n \times (n - 1) \times \dots \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{array}{r} _{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{array}

なので $_{5} C_{3} =_{5} C_{2}$ となる。

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

同様に

\begin{array}{r} _{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{array}

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

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

例えば $x + y$ は

\begin{array}{r} \begin{aligned} (x + y)^{2} & = (x + y) (x + y) \\ = x^{2} + 2 x y + y^{2} \\ (x + y)^{3} & = (x + y)^{2} (x + y) = (x^{2} + 2 x y + y^{2}) (x + y) \\ = x^{3} + 3 x^{2} y + 3 x y^{2} + y^{3} \\ ⋮ \end{aligned} \end{array}

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

例：

\begin{array}{r} \begin{aligned} (x + y)^{2} & = x^{2} + 2 x y + y^{2} \\ = (\binom{2}{0}) x^{2} + (\binom{2}{1}) x y + (\binom{2}{2}) y^{2} \\ = \sum_{r = 0}^{2} (\binom{2}{r}) x^{2 - r} y^{r} \end{aligned} \end{array}

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

二項定理

(x + y)^{n} = \sum_{r = 0}^{n} (\binom{n}{r}) x^{n - r} y^{r}

他の例：

\begin{array}{r} (1 + x)^{n} = (\binom{n}{0}) + (\binom{n}{1}) x^{1} + (\binom{n}{2}) x^{2} + \dots + (\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} + \dots + (\binom{n}{n - 1}) x^{1} y^{n - 1} + (\binom{n}{n}) y^{n} \end{array}