組合せ論における組合せの定義と二項定理の証明
定義
- 有限集合の部分集合を組合せcombinationという。
- 濃度が$n$である集合において、濃度が$k$である部分集合の数を$\binom{n}{k}$あるいは$_{n}C_{k}$のように表し、二項係数binomial coefficientと呼ぶ。 $$ \binom{n}{k} = {}_{n}C_{k} = \frac{ n! }{ k! (n-k)! } $$
簡単な定義
互いに異なる$n$個の中から順序を考えずに$k$個を選ぶ場合の数を組合せcombinationといい、$\binom{n}{k}$あるいは$_{n}C_{k}$で表す。
$$ \binom{n}{k} = {}_{n}C_{k} = \frac{ n! }{ k! (n-k)! } = \frac{ _{n}P_{k} }{ k! } $$
ここで$_{n}P_{k}$は順列である。
定理
二項定理binomial theorem
$$ (x+y)^{n} = \sum_{k=0}^{n} \binom{n}{k} x^{k} y^{n-k} $$
パスカルの恒等式
$$ \binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1} $$
二項係数の和の公式
$$ 2^{n} = \sum_{k=0}^{n} \binom{n}{k} $$
二項係数の引き算の公式
$$ \binom{n}{k} \left( {\frac{ n }{ k }} \right)^{-1} = \binom{n-1}{k-1} $$
二項係数の二乗和の公式
$$ \binom{2n}{n} = \sum_{k=0}^{n} \binom{n}{k}^{2} $$
説明
なお、上記のうち二項定理を除く残りの公式の名前は、実際に使われている名称ではなく、単に便宜上呼びやすくするために任意に付けたものであることに注意せよ。
二項定理は組合せ論において最も有名かつ重要な定理であり、分野を問わず広く応用される。
証明
二項定理以外の証明は、各公式の文書で個別に扱う。
$(x+y)^{n}$を展開するとき、$x^{k} y^{n-k}$の係数は $$ (x+y)^{n} = (x+y)(x+y)(x+y) \cdots (x+y) $$ の各$(x+y)$の中から$x$を$n$個、$y$を$n-r$個選ぶことと同じである。したがって組合せの数$_n C _r$が$x^{k} y^{n-k}$の係数となるので、次が成り立つ。 $$ (x+y)^{n} = \sum_{k=0}^{n} {_n C _k} x^{k} y^{n-k} $$
■