組み合わせの総数【場合の数】

組み合わせの総数について説明します。順列と同じく「場合の数」の分野に属する個数の数え方です。これは確率でも使用しますし、２項定理を始めとして種々の計算にも使われる事が特徴です。
（英：組み合わせ【数学の用語として】 selection, combination）

考え方・・順番を区別せずに選ぶ

順列が並び方を区別するのに対して、
組み合わせは本当に「何を選んだか」だけを問題にして順番は無視するというものです。

例えば、４つのものを並べる順列の総数は４！通りですが、
４つのものから４つを選ぶ組み合わせは１通りだけです。

順列：｛Ａ，Ｂ，Ｃ，Ｄ｝｛Ａ，Ｂ，Ｄ，Ｃ｝｛Ａ，Ｃ，Ｄ，Ｂ｝｛Ａ，Ｄ，Ｃ，Ｂ｝,・・他　２４通り
組み合わせ：｛Ａ，Ｂ，Ｃ，Ｄ｝の１通り

４つのものから３つを並べる順列の総数は４・３・２＝２４通りですが、組み合わせの場合はどうなるでしょう。具体的に書きだしてみると、｛Ａ，Ｂ，Ｃ｝｛Ａ，Ｂ，Ｄ｝｛Ａ，Ｃ，Ｄ｝｛Ｂ，Ｃ，Ｄ｝の４通りだけという事になります。これを記号では_４Ｃ_３＝４のように書きます。

尚、４つのものから３つを選ぶという事は実際のところ「残る余りの『１つ』」の選び方と同じなので、ただちに「４通り」と言う事もできます。これは次に触れるように、公式のような形で定式化する事もできます。

結論の式と公式

公式にすると、結論は次のようになります。

この組み合わせの記号_ｎＣ_ｍを２項係数と呼ぶ事もあります。（名称が違うだけで中身は全く同じです。）
その名称の由来は冒頭で触れましたように、２項定理で係数として表される事によります。

考え方としては次のようにします。

まず、ｎ個からｍ個を選び「並び替える」場合は_ｎＰ_ｍ通りです。この時、「ｎ個からｍ個を選ぶ」という操作はじつはすでにやってしまっているんですね。

ただし順列の場合は、その「選んだｍ個の並び替え」も実行して、総数にカウントしているわけです。言い換えると、順番を区別していない「組み合わせ」のそれぞれを「ｍ個を並び替変えの総数：ｍ！通り」倍しているわけです。

例えば、５つから３つを選んで｛Ａ，Ｃ，Ｄ｝であったとしましょう。これは、順番を区別していないものです。つまり、｛Ｃ，Ａ，Ｄ｝と書いても同じものとします。

ここで、順列の場合は、｛Ａ，Ｃ，Ｄ｝の並び替えもカウントするので、この組み合わせに対して３！＝６通りあるわけです。

これは他の組み合わせ｛Ｂ，Ｃ，Ｅ｝などに対しても並び替えれば３！＝６通り発生するわけで、他の組み合わせも個体の数が同じですから同様に並び替えで３！＝６通りずつ発生します。

結局、次のようになります：
「組み合わせの総数【_ｎＣ_ｍ】」×「選ぶ個数【ｍ】に対する順列の総数【ｍ！】」
＝「ｎ個からｍ個選んで並び替える順列の総数【_ｎＰ_ｍ】」
という事になります。これを式で書くと次のようになります。

$$(_nC_m)\cdot (m!)=_nP_m\hspace{5pt}\Leftrightarrow \hspace{5pt}_nC_m=\frac{_nP_m}{m!}$$

これが、組み合わせの総数を表す公式の意味です。

この式の続きは、単なる分母と分子の約分の計算になります。順列を階乗だけで表す形にすれば組み合わせの式もｎとｍを使った階乗で表される形になります。

この式を使えば、例えば７個から３つ選ぶ場合の組み合わせの総数は、次のようになります。

$$_7C_3=\frac{7\cdot 6\cdot 5}{3!}=\frac{7\cdot 6\cdot 5}{3\cdot2\cdot1}=35$$

このように「３５通り」という結果が比較的簡単に分かるわけです。尚、これが順列であれば６倍の２１０通りですから、並び替えずに組み合わせにすると大きな数に比較的なりにくい傾向がある事も分かります。

ここで、同じ組み合わせを階乗だけの形で書くと、

$$_7C_3=\frac{7!}{(7-3)!3!}
=\frac{7!}{4!3!}$$

他方、７つから４つ選ぶ組み合わせの総数は、

$$_7C_4=\frac{7!}{(7-4)!4!}
=\frac{7!}{3!4!}$$

であり、これらは同じ数ですね。７個から３つ選ぶ場合も４つ選ぶ場合も、同じく３５通りです。これは、３つ選んだら残り４つも必然的に決まるのだから同じ総数になって当然であると考えてもよいですし、一般のｎとｍに対する式変形で示す事も可能です。

式で示す場合、ｎ個から（ｎ－ｍ）個を選ぶ組み合わせの式を作ってみればよいのです。

$$_nC_{n-m}=\frac{n!}{\{n-(n-m)\}!(n-m)!}=\frac{n!}{m!(n-m)!}= _nC_m$$

分母のところの掛け算が順番を入れ替えても同じになる事から、この関係が成り立ちます。つまり、７個から２個選ぶ組み合わせの総数が分かったら、７個から５個選ぶ組み合わせの総数も同じであるので計算不要という事です。（順列の場合は、そのようにする事はできません。）

必ず自然数になる？

さてここで、言われると確かにそのように納得できるかもしれないが、順列の総数を「ｍ！」で割る時に「自然数になる」保証はあるのか？と思うかもしれません。

これは「理解」する方法としては、「組み合わせの総数が１.５通りとか２／３通りになる事はあり得ないので、必ず自然数であるに決まっている」・・と、捉えても支障はありません。
実際、どうやっても自然数にしかならないからです。

他方で、順列とか組み合わせとかを離れて、単に自然数ｎとｍを持ってきて次式が自然数になるか否かという問題が提示された時に「組み合わせだから自然数」と言うのは数学的な証明には、もちろんなりません。

結論は、この式は必ず自然数になります。分子は分母で必ず割り切れて余りはでないという事です。

そのようになる事に対する一番簡単な証明は、「順番にｎ個並んだ自然数の中には、ｎの倍数が少なくとも１つ必ず含まれている」という事を根拠にするものです。

例えば、順番ずつ３つ並んだ自然数の中には、３の倍数が少なくとも必ず含まれています。これは、どんなでたらめな自然数を持ってきても、それに＋１、＋２する形（あるいは－１、－２）する形で並べてあげると３の倍数が必ず含まれるという事です。

２１４というてきとうな自然数をもってきて、｛２１４、２１５、２１６｝と並べれば、この場合は真ん中の数が３の倍数ですね。この理屈の意味自体は簡単で、１,２,３,４,５,６,７,８,９,・・・と、並べたとき、どこでもいいから数が３つ含まれるように区切ると、どうやっても３の倍数は１個以上含まれるという事です。

３でなくても、５でも６でも７でも、任意の自然数でそのようになります。
もう少し一般的に言うと、例えば３の倍数なら、任意の自然数は３ｎ, ３ｎ＋１, ３ｎ＋２ のいずれかで表されるので１を加えていくか引いていく形で３個並べれば、その必ず３ｎの形のものが存在するという事です。

$$_nC_m=\frac{n(n-1)(n-2)\cdots (n-m+1)}{m!}$$

の形で見るのが一番分かりやすいかと思いますが、式の分子の（積の）項数はｍ個です。他方、分母はｍ！＝ｍ(ｍ－１)(ｍ－２)・・・３・２・１ですから、ｍ以下の自然数しか含まれません。そのため、分子に含まれる任意の自然数の倍数は、必ず分母に存在するという事です。これが基本的な考え方です。

話が少しややこしくなるのは、組み合わせの式の場合では分子に複数の自然数があるためです。仮に自然数ｐとｑの倍数が共通する数として分母に含まれていたら、必ず割り切って全体として自然数になるかが怪しくなる可能性もあるとも言えるわけです。

しかし実際はそのような事は起きないので大丈夫であるというのが結論です。

まずｎは固定したうえで、ｍまでは確かに割り切れて全体が自然数になるとしましょう。

次のｍ＋１が素数であったら、ｍまでの数のいずれでもないし倍数でもないので、分子のｍ＋１個の中にｍ＋１の倍数が存在し、割り切れる事になります。

ｍ＋１が素数でない場合で、ｍ以下の自然数ｐの倍数になっている時であっても、例えばｐｑ個の中には、ｐの倍数が少なくとも「ｑ個」含まれています。これは、ｐ個の塊で区切れるところがｑ個あるためです。
そのうえで、ｐｑの倍数も１個以上あるので、分母の１つのｐの倍数を既に割って使ってしまったあとでも別のｐの倍数が必ず残っています。それで、ｍ＋１＝ｐｑの倍数も分母に必ずあるので、再び全体として割り切って自然数になるというわけです。

具体例では、_８Ｃ_３＝８・７・６／(３・２・１) は確かに自然数になりますが、続いて_８Ｃ_４を考えた時に、_８Ｃ_４＝８・７・６・５／(４・３・２・１)の分母に新たに入った４＝２^２について、すでに分母にある２については、分母の項数が４つなので、２の倍数は２個以上あります。（この場合、見れば分かる通り６と８です。）分母の４項の中で、４の倍数は必ず１個以上ある事は確定しています。

Ａ，Ｂ，Ｃ，Ｄと並べたところの１つが４の倍数だと考えると分かりやすいかと思いますが、例えばＢの位置にあったとき、Ｃ、Ｄは使用しませんが、２の倍数は２個ずつ区切ったＡ，ＢとＣ，Ｄのどちらにも１個ずつ含まれます。このようにして、分母にすでに２がある事で４で割り切れなくなってしまう心配はないという事です。

少しややこしい理屈である事は間違いありませんが、基本的な考え方は一般のｎとｍに対しても同じ事です。

このようにして、組み合わせの総数を表す式はきちんと「割り切れて」自然数になる事が式の形からも保証されます。

別の方法はある？

「組み合わせを順列を使って表せるのは分かったが、別の方法はないのか」

あります。場合の数を考える時には考え方は１つとは限らず、複数の考え方で同じ結論になる事はよくあります。ただし、組み合わせに関して言えば順列を階乗で割る表し方が一番簡単ではないかと思います。

別のやり方としては、１つの例として次のように組み合わせを考える事もできます。

Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇの７つから４つ選ぶ場合、まず「Ａを含む場合」、残り３つを６つから選びます。次に、Ａを含まずＢを含む場合、Ａ，Ｂを含まない５つから３つを選びます。
こういう具合に考えても組み合わせの総数を表す事ができて、次の関係が成立します。

$$_nC_m=_{n-1}C_{m-1}+_{n-2}C_{m-1}+_{n-3}C_{m-1}+\cdots +_{m}C_{m-1}+_{m-1}C_{m-1}$$

６つから３つを選ぶ組み合わせは、さらに５つから２つを選ぶ場合・４つから２つを選ぶ場合・・に分割できます。数が少なくなれば「明らかに」分かる組み合わせの場合にたどり着きます。
７つから４つ選ぶ時に実際にこれが正しいのかを見てみると、

$$_7C_4=_{6}C_{3}+_{5}C_{3}+_{4}C_{3}+_{3}C_{3}=20+10+4+1=35$$

通常の組み合わせの公式で計算すると、

$$_7C_4=\frac{7\cdot 6\cdot 5\cdot 4}{4\cdot 3 \cdot 2 \cdot 1}=35$$

この通り一致するわけですが、これは次の理由になります。
まず分母の７を（４＋３）の形に書きます。

$$_7C_4=\frac{(4+3)\cdot 6\cdot 5\cdot 4}{4!}=\frac{4\cdot 6\cdot 5\cdot 4+3\cdot 6\cdot 5\cdot 4}{4!}=\frac{6\cdot 5\cdot 4}{3!}+\frac{3\cdot 6\cdot 5\cdot 4}{4!}$$

$$=_6C_3+\frac{3\cdot (4+2)\cdot 5\cdot 4}{4!}=_6C_3+\frac{4\cdot 5\cdot 4\cdot 3+2\cdot 5\cdot 4\cdot 3}{4!}=_6C_3+_5C_3+\frac{2\cdot 5\cdot 4\cdot 3}{4!}$$

$$=_6C_3+_5C_3+\frac{2\cdot (4+1)\cdot 4\cdot 3}{4!}=_6C_3+_5C_3+_4C_3+\frac{ 3\cdot 2\cdot 1}{3!}=_6C_3+_5C_3+_4C_3+_3C_3$$

一般のｎとｍの場合も同じで、分母の一番大きい項を(ｍ＋ｐ)の形にして分離していくとこの形になります。

しかし言い換えると、この考え方でやったとしても結果は同じで_nC_m＝(_nＰ_m)／(ｍ！) と同じ式になるのです。