組み合わせ論

組み合わせ論(combinatorics)とは、数学の一分野である。

概要

簡単に言えば、あるパターンに対して何通りあるかを計算する方法。高校数学まででは「場合の数」という単元名になっていることが多い。

15人を並べるパターンは全部で何通りあるか、30人の中から5人を選ぶパターンは何通りあるか、3連単10頭ボックス買いの買い目は何通りか…など。

もちろん、すべてのパターンを数え上げれば求まるが、パターンを抜かしたり重複して数えるミスが怖いし、何より対象の数が多いと計算量が膨大になってしまう。そこで、計算を簡単にする方法を考えるのである。

具体例

直積

m個のものとn個のものを組み合わせるパターンの数を数え上げた場合の数。

例えば、グループAに4人、グループBに3人いる場合、グループA、Bから1人ずつ取ってペアを作る場合の数がこれに当たる。

各グループに重複がなければ、場合の数は単に掛け算となるため、決まった記号はない。上記の例なら単純に4×3である。

公営競技では「フォーメーション」という投票券の買い方に相当する(重複がない場合)。

順列

→順列

m個の中からn個を並べる場合の数。順番違いは別とみなす。

高校数学では、m個からn個並べる順列を_mP_nと表すことが多い。
他に、P(m,n)や[m n](実際は縦に並べる)などの記述方法もある。
EXCELではPERMUT(m,n)と表記する。

例えば₁₀P₃であれば、1番目に並べる場合が10通り、2番目は1番目に選んだものを除くので9通り、3番目は1番目と2番目に選んだものを除くので8通り、すなわち10×9×8通りとなる。

同様に、

_ｍP_n
=ｍ×(m-1)×(m-2)×…(m-n+1)
=m!/(m-n)!

である。

公営競技では、n連単ボックス買いに相当する。
例えば、3連単の7頭ボックス買いならば₇P₃で求められる。

重複順列

m個の中からn個を重複を許して並べる場合の数。

重複を許すならば、m個のn回直積となるので、場合の数はmⁿである。
べき乗で表せるため、決まった記号はない。

例えば、m面サイコロをn個振った場合の数がこれに相当する。

公営競技では、枠n連単ボックス買いがこれに該当する(すべての枠番にゾロ目があると仮定した場合)。

円順列

m個の中からn個を円形に並べる場合の数。回転して重なるものは同じと見なす。

同様に、回転だけでなく左右反転させて重なるものを同じと見なす場合を数珠順列と呼ぶ。

組み合わせ

→組み合わせ(組み合わせ論)
→二項定理

m個の中からn個選ぶ場合の数。順番違いは同じとみなす。
狭義にはこれを「組み合わせ」というが、他の「組み合わせ」と紛らわしいので「二項係数」という場合もある。

高校数学では、m個からn個選ぶ組み合わせは_mC_nと表現する。
他に、C(m,n)や(m,n) (実際は縦に並べる)という表記もある。
EXCELではCOMBIN(m,n)と表記する。

例えば₁₀C₃であれば、₁₀P₃が上述の理由で10×9×8通り、順番違いを除くので、3つの順番違いのパターンを計算すると₃P₃=3!=3×2×1通りとなる。前者を後者で割れば求められる。

同様に、

_mC_n
=(_mP_n)/(_nP_n)
=(m!)/(m-n)!n!

である。

公営競技では、n連複ボックス買いに相当する(ワイドなど、拡大n連複も同じ)。
例えば、3連複の7頭ボックス買いならば₇C₃で求められる。

重複組み合わせ

m個の中からn個を、順番違いを考慮せずに重複を許して選ぶ場合の数。

高校数学では_mH_nと表記する場合が多い(ただし発展教材)。

例えば、₃H₈の場合、以下のように考える。

1. 8つの◯を並べる。これを3色に塗り分けることを考える。

◯◯◯◯◯◯◯◯

2. 各◯間のどこかに、2つの「仕切り」を入れることを考える。仕切りの間のボールを、左から順に1色目、2色目、3色目で塗り分けることにする(仕切りの間に◯がない場合も数える)。
これは₃H₈と一対一対応する。

◯◯◯|◯◯|◯◯◯

3. すなわち、₃H₈は8つの◯と2つの|を並べる場合の数に他ならない。ただし、◯同士、|同士は区別しないものとする。

4. 8つの◯と2つの仕切りをすべて区別すれば、場合の数は(8+2)!となる。重複分を除くには◯同士、|同士の順番違いを除けばいいので、8!2!で割ればよい。

同様に、

_mH_n
=(m+n-1)!/m!(n-1)!

となる。

公営競技では、枠n連複ボックス買いに相当する(すべての枠番にゾロ目があると仮定した場合)。

関連動画

関連静画

関連リンク

関連項目

• 数学
  • 確率論
  • 階乗
  • 二項定理
  • 組み合わせ爆発
• 投票券(公営競技) (馬券/車券/舟券)
  
  • 馬連(馬複/二連複) / 馬単
  • 枠連 / 枠単
  • 三連複 / 三連単
  • フォーメーション(公営競技) / ボックス(公営競技) / ながし(公営競技)