C~コンビネーションとは何か
例えば1~5まで番号づけられた5つのボールから2つ取り出すことを考えます。これは全部で何通りでしょう。
これは$${_5 C _2=10}$$通りであると計算できます。
この$${C}$$について解説します。
定義
まず具体例から考えます。
先ほどの例の$${_5 C _2}$$を使いましょう。実際には
$$
_5 C_2=\frac{5\times 4}{2\times 1}
$$
と計算しています。分母には$${_5 C _2}$$の$${2}$$から始めて$${1}$$になるまで掛け算します。分子は同じ個数だけ$${_5 C _2}$$の左の$${5}$$から一つずつ下がって掛け算していきます。もう一つくらい例として計算してみましょう。例えば$${_7 C_3}$$であったら
$$
_7 C_3=\frac{7\times 6\times 5}{3\times 2\times 1}
=35
$$
計算結果は必ず整数になります。ではここで問題。
$${_8 C_5}$$は何でしょう。答え合わせは後ほど。
階乗
階乗とは
$$
n!=n\cdot (n-1)\cdots 2\cdot 1
$$
です。例えば$${1!=1,2!=2\cdot 1=2,3!=3\cdot 2\cdot 1=6,4!=4\cdot 3\cdot 2\cdot 1=24,…}$$といった具合です。
これは「順列」に対応していると考えることができます。
$${2,4,6,8}$$と書かれたカードで4桁の数字を作ることを想定します。
千の位は$${2,4,6,8}$$の4通り、百の位は千のくらいで選ばなかった3通り、十の位は残りの2通り、一の位は余った1通り。
つまりできる4桁の数字は全部で
$$
4\times 3\times 2\times 1
$$
の$${4!=24}$$通りと計算できます。
なぜかけ算になるのか疑問に思ったらぜひ樹形図を書いてみてください。
では順列との対応は後で見ることにしてこの階乗を用いて$${C}$$を明示的な式として定義していきましょう。
（補足）
$${0!=1}$$と約束します。
nCr
$${n,r}$$は正の整数で$${n\ge r}$$とします。
先ほどと同じように考えていきます。
まず、分母は$${r}$$から始めて$${1}$$まで$${r}$$個のかけ算が来ます；
$${r\cdot (r-1) \cdots 2\cdot 1}$$
分子は$${n}$$から始まりカウントダウンしていき分母と同じ$${r}$$個のかけ算がきますから
$${n\cdot (n-1)\cdots (n-r+1)}$$
となります。
$$
_n C_r=\frac{ n\cdot (n-1)\cdots (n-r+1)}{r \cdot (r-1) \cdots 2\cdot 1}
$$
最後が$${n-r}$$ではなく$${n-r+1}$$となるのは
$$
n \gets n-0 \\
n-1 \gets n-1 \\
\cdots \\
n-r+1 \gets n-(r-1)
$$
と思うと、$${n}$$から引く数が$${0,1,\cdots r-1}$$の$${r}$$個となっていることがわかるでしょうか。
また次のようにも考察できます。
唐突ですが$${n}$$から$${1}$$まですべて並べてしまいます；
$${n \cdot (n-1) \cdots 2\cdot 1}$$
こいつから$${1}$$から$${n-r}$$を削ったものが分子です。すなわち、
$${n \cdot (n-1) \cdots (n-r+1)\cdot (n-r)\cdots 2\cdot 1}$$の
後半の$${n-r}$$個のかけ算($${(n-r)\cdots 2\cdot 1}$$)を割り算して
$$
(分子)=\frac{ \overbrace{n \cdot (n-1) \cdots (n-r+1)}^{r個} \cdot \overbrace{(n-r)\cdots 2\cdot 1}^{n-r個}}{(n-r)\cdots 2\cdot 1}
$$
さてこれらの考察から階乗をつかってきれいに書き直すことができます。
分子は$${\frac{n!}{(n-r)!}}$$,分母は$${r!}$$であるから
$$
_n C_r=\frac{n!}{r!(n-r)!}
$$
となります。これを明示的な定義と思うことにします。
順列と組み合わせ
ここで$${C}$$の組み合わせとしての意味を順列に対応する$${P}$$との関係からはっきり捉えましょう。
Pの定義
具体例から始めましょう。
$${2,4,6,8}$$の$${4}$$枚のカードを用いて二桁の数字は何通りできるでしょうか。
まず十の位の候補は$${2,4,6,8}$$の$${4}$$通りであり
一の位は残りの$${3}$$通りですから求めるのは
$$
4\times 3=12
$$
です。これを$${4}$$枚から$${2}$$つのものの順列を考えるという意味で
$${_4 P_2}$$と表します。これは$${4}$$から始めて$${2}$$つだけカウントダウンしてかけ算することで計算します。
例えば$${_8 P_3}$$であったら
$$
_8 P_3=8\times 7\times 6=336
$$
といった具合です。
区別するのか区別しないのか
最初に示した例を用いましょう。
1~5で番号付けられたボールが袋に入っているとします。
ここから二つのボールを取り出して二けたの数字をつくる。
これは全部で$${_5 P_2=5\times 4=20}$$通りです。
一方で単に二つのボールを取り出す。
この取り出し方は全部で何通りでしょう。
すべて列挙してみましょう。
これは先ほどの$${20}$$ではなく$${10}$$通りです。
前者を順列、後者を組み合わせと呼ぶことにします。
この違いは何でしょうか。
組み合わせの場合$${20}$$通りとしてしまうと数えすぎているのです。
より正確には$${2!}$$回同じものをダブってカウントしてしまっているのです。
この両者の違いをはっきりさせましょう。
順列の場合、$${(1,2)}$$と$${(2,1)}$$は別のものです。（12と21は違うもの）しかし組み合わせの場合、この区別はありません。（1と2のボールを取り出すことと2と1のボールを取り出すことはまったく同じこと）
この組み合わせが$${C}$$に対応しています。
つまり5つのものから2つ取り出す組み合わせの総数は
$${_5 C_2=10}$$通りです。
なぜこうして計算することができるのでしょうか。
PとC
組み合わせのほうでは今二つのものを取り出すことを考えていますから、順列に比べて$${2!}$$だけダブっているものを同一視していることになります。つまり
$$
_5C_2=\frac{_5 P_2}{2!}
$$
と推察することができます。
実際、一般には次が成立します。
$$
_nC_r=\frac{_n P_r}{r!}
$$
両辺に$${r!}$$をかけて
$$
_n P_r=_n C_r \times r!
$$
この形で「意味」を考えてみます。
標語的には
「順列」とは「取って」さらに「並べる」ということです。
取り出すことは$${C}$$に、並べることが階乗に対応しています。
（補足）
$${P}$$の定義
$$
_n P_r=\frac{n!}{(n-r)!}=n \cdot (n-1) \cdots (n-r+1)
$$
いくつかの公式
余事象
$${n}$$から$${r}$$個取り出すということは
取り出さない$${n-r}$$個を決めることに等しいので
$$
_n C_r =_n C_{n-r}
$$
が成立します。実際
$$
_n C_{n-r}=\frac{n!}{(n-r)!(n-(n-r))!} \\
=\frac{n!}{(n-r)!r!}=_n C_r
$$
です。
ここで最初に示した問題の答え合わせをしましょう。
$${_8 C_5 =_8 C_{8-5}=_8 C_3=\frac{8\cdot 7\cdot 6}{3\cdot 2\cdot 1}=56}$$
もちろんこれは最初に紹介した方法による結果と一致するはずです。
二項定理とパスカルの三角形
二項定理を紹介しましょう。
$$
(a+b)^n=\sum _{k=0}^n _n C_k a^k b^{n-k}
$$
$${a^kb^{n-k}}$$の係数を考えます。
$$
\underbrace{(a+b)\cdot (a+b)\cdots (a+b)}_{n個}
$$
n個の中から$${a}$$を$${k}$$個選べばよくこれは$${_n C_r}$$個です。
（n個のスロットにk個の$${a}$$を入ればよい）
この$${k}$$を0から$${n}$$まで考えれば二項定理を得ます。
視覚的に表したのがパスカルの三角形です。
ルールは単純で1,1から始めて基本的に上にある数字を加えることで決定していきます。（端はそのまま1を追加する）これが展開式の係数に対応しています。
$$
(a+b)^2=1\cdot a^2 +2\cdot ab +1\cdot b^2 \\
(a+b)^3=1\cdot a^3 +3\cdot a^2b+3\cdot ab^2 +1\cdot b^3 \\
\cdots
$$
つまり二項定理との対応を加味すれば次のようにも見ることができます。
ここから一般に次のように類推できます。
$$
_n C_{k-1} +_n C_{k}=_{n+1} C_{k}
$$
ただし$${k=1,2,\cdots n}$$
これは定義を用いてもきちんと証明できますがここでは省略します。
多項定理
二項定理と同じ原理で少し一般的な形で多項定理というものがあります。
$$
(x_1+x_2+\cdots x_m)^n
$$
の$${x_1^{k_1}x_2^{k_2}\cdots x_m^{k_m}}$$(ただし$${\sum_{i=1}^mk_1=n}$$)の係数を考えましょう。
$${n}$$個のスロットを想定し、まず$${x_1}$$が$${k_1}$$個入るのでその場所を決めることから$${_n C_{k_1}}$$通り
次に$${x_2}$$について、残りの$${n-k_1}$$から$${k_2}$$箇所決めることから$${_{n-_k_1} C_{k_2}}$$通り。
これを繰り返していくと結局求めるのは
$$
_n C_{k_1} \times _{n-k_{1}} C_{k_{2}} \times _{n-k_{1}-k_{2}} C_{k_{3}}\times \cdots \times _{n-k_{1}-k_{2}-\cdots -k_{m-1}} C_{k_m}
$$
とわかります。これを定義によって階乗で表し整理することで
$$
\frac{n!}{k_{1}!k_{2}!\cdots k_{m}!}
$$
となります。
これは次のように考えることもできます。
まずすべて区別し、すなわち「順列」だと思って$${n!}$$通りとします。
ここから区別をなくします。つまりダブって数えてしまっている分を考えます。これは$${k_{1}!k_{2}!\cdots k_{m}!}$$だけなので同じ結果を得ることができます。