組合せ論 - データサイエンス関連+αのメモ

組合せ論（combinatorics）

置換¶

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

(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)

の6パターンとなる。

一般に $n!$ 個になる。

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

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

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

これは無量大数（10⁶⁸）に近い大きさになる

例えば ${}_{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)!}

{}_{5}C_{3} = \frac{5\times 4}{2 \times 1}\\ {}_{5}C_{2} = \frac{5\times 4 \times 3}{3 \times 2 \times 1}

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

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

同様に

{}_{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

で ${}_{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{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}

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

例：

\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}

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

他の例：

(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