【公式】組み合わせと順列の違い・見分け方【重複度を使う計算方法】

  • このエントリーをはてなブックマークに追加
  • Pocket

こんにちは。タクマ™ [@suwaru_blog] です。

前回、置換・順列を解説しました。こちらは「順序を考える」並べ方でした。

置換・順列は「並べ方・選び方はどうでもよくて、パターンだけ網羅したい」ときには使えません。

今回、順序は考えない並べ方「組み合わせ」について解説します!

組み合わせとは

5 枚のカード A, B, C, D, E を持っています。
いきなり本題ですが、この 5 枚のカードから順序を考えずに 3 枚を選び出してみます。

  • ABC
  • ABD
  • ABE
  • ACD
  • ACE
  • ADE
  • BCD
  • BCE
  • BDE
  • CDE

この「順序を考えずに」という言葉が意味することは、
たとえば ABE, BAE といった同じカードで構成されたものは同じと判断します。

このような順番を気にしない選び方を「組み合わせ」といいます。

「置換」「順列」は順序を考えますが、「組み合わせ」では順序を考えません。このことは重要なので覚えておいてください。

組み合わせの総数

数式で組み合わせを求める方法を説明します。以下のやり方に従えば OK です。

  • まず順列で考える (順序を考える)
  • 重複してしまった分 (重複度) で割り算する

では、こちらを詳しく説明していきます。

重複度とは

シンプルに 3 枚のカードの並び順を考えてみます。
A, B, C という 3 枚のカードの並べ方 (置換) は 6 パターンです。

  • ABC
  • ACB
  • BAC
  • BCA
  • CAB
  • CBA

順列では、この 6 パターンを「すべて別の並べ方」としてカウントしますが、
組み合わせでは、この 6 パターンを「 1 つのグループ」としてカウントします。

つまり、この場合の「順列の総数」は「組み合わせの総数」の 6 倍重複しています。
※ この 6 という数字を「重複度」といいます

よって「順列の総数」を 6 で割れば「組み合わせの総数」を求めることが可能です。

重複度の求め方

重複度は「置換の総数」から求めることができます。

ここでは 5 枚のカードから 3 枚のカードを選ぶので、
3 枚の置換の総数 3P3 (3 * 2 * 1) から 6 という重複度を得ることができます。

5 枚から 3 枚を選ぶ組み合わせの総数

5 枚から 3 枚を選ぶ組み合わせの総数は 5C3 と表記できます。

※ C は combination の略です

5C35 枚から 3 枚を選ぶ「順列」の総数 / 3 枚の「置換」の総数 のことです。
これは 5P3 / 3P3 で表せますね。

計算すると (5 * 4 * 3) / (3 * 2 * 1) で 10 になります。
よって 5 枚から 3 枚を選ぶ組み合わせの総数は 10 通りです。

組み合わせの総数の一般化

n 枚のカードから k 枚をまとめて選び出す組み合わせの総数を求めるとしましょう。

nCkn 枚から k 枚を選ぶ「順列」の総数 / k 枚の「置換」の総数 のことです。
これは nPk / kPk で表せますね。

組み合わせの総数の値

組み合わせの総数について、いくつか例を示します。

組み合わせの総数意味答え
5C5(5 * 4 * 3 * 2 * 1) / (5 * 4 * 3 * 2 * 1)1
5C4(5 * 4 * 3 * 2) / (4 * 3 * 2 * 1)5
5C3(5 * 4 * 3) / (3 * 2 * 1)10
5C2(5 * 4) / (2 * 1)10
5C15 / 15
5C01 / 11

階乗を使った組み合わせの総数の表現

組み合わせの総数 nPk / kPk は「階乗の表記方法」を使うと (n! / (n - k)!) / k! で、
これをまとめると n!/(n - k)!k! とすることができます。

置換・順列・組み合わせの関係性

ここで置換・順列・組み合わせの関係性を整理してみます。

表にまとめる

置換 – 3P3

  • 3 枚のカード A, B, C の置換
    • 3P3 = 6 通り
#1 #2 #3 #4 #5 #6
ABC ACB BAC BCA CAB CBA

組み合わせ – 5C3

  • 5 枚のカード A, B, C, D, E から 3 枚を選ぶ組み合わせ
    • 5C3 = 10 通り
#1
ABC
ABD
ABE
ACD
ACE
ADE
BCD
BCE
BDE
CDE

順列 – 5P3

  • 5 枚のカード A, B, C, D, E から 3 枚を選ぶ順列
    • 5P3 = 60 通り
#1 #2 #3 #4 #5 #6
ABC ACB BAC BCA CAB CBA
ABD ADB BAD BDA DAB DBA
ABE AEB BAE BEA EAB EBA
ACD ADC CAD CDA DAC DCA
ACE AEC CAE CEA EAC ECA
ADE AED DAE DEA EAD EDA
BCD BDC CBD CDB DBC DCB
BCE BEC CBE CEB EBC ECB
BDE BDE DBE DEB EBD EDB
CDE CED DCE DEC ECD EDC
3P3 * 5C3 = 5P3

表を見ると、以下の関係がハッキリします。

  • 3 枚の置換 * 5 枚から 3 枚を選ぶ組み合わせ = 5 枚から 3 枚を選ぶ順列
    • 3P3 * 5C3 = 5P3
      • この式を 5C3 = 5P3 / 3P3 に変形すると「組み合わせの総数の求め方」とも一致する
    • 6 * 10 = 60 通り

薬品の調合クイズ

粒状になった A, B, C の 3 種類の薬品があり、以下のルールに従って新薬調合を行います。

  • A, B, C の 3 種類の中から、合わせて 100 粒を調合する
  • 必ず A, B, C それぞれ 1 粒以上を調合しなければならない (重複してもよい)
  • 調合の順序は考えず、同じ薬品の粒には区別がない (組み合わせ)

重複組み合わせ

5 粒で考える

100 粒じゃなく、まず 5 粒という小さいスケールで考えてみます。
また「順序が問われない」なら、A, B, C と順序を固定して考える方がシンプルです。

これは「仕切りの置き場所の組み合わせ」の問題

そして 5 粒を並べたとき、2 本の「仕切り」で区切るイメージを持ってみましょう。
| を仕切りに見立てると、AA | BB | C のようなイメージです。

1 本目の区切りまでには A を並べて、
2 本目の区切りまでには B を並べて、
残りのスペースには C を並べるルールを適用するとします。

このルールを適用すると A, B, C の存在を特に意識せずに、
「仕切りの置き場所の組み合わせ」の問題として捉えることができます。

仕切りは何箇所に置けるか

5 粒の薬を「○」、仕切りが置ける場所を「▼」で表すと ○▼○▼○▼○▼○ になります。
仕切りを置ける場所は 4 箇所です。

この 4 箇所から 2 箇所の仕切りを置く場所を決める組み合わせは 4C2 です。
これが 5 粒の場合の答えになります。

n 粒 k 種類の薬品で考える

仕切りの結果を一般化してみましょう。

  • 薬は n 粒
  • 仕切りを置ける場所は n -1 箇所
  • 仕切りの数は k -1 枚

この数字を使うと、調合法の総数は n-1Ck-1 となります。

100 粒で考える

したがって 100 粒を 3 種類の薬品から選ぶ方法の総数は 100-1C3-1 なので 99C2 です。
計算すると (99 * 98) / (2 * 1) で、答えは 4841 通りです。

少なくとも一端がジョーカークイズ

トランプが 5 枚あります。内訳は J, Q, K, ジョーカー, ジョーカーです。
この 2 枚のジョーカーは区別がないものとします。

このトランプを横一列に並べるとき、
左端・右端の少なくとも一端がジョーカーになる並べ方は何通りでしょうか。

順列から組み合わせを求める

ジョーカーを区別して数えて「順列」を求めた上で、
ジョーカーの重複度で割れば「組み合わせ」を求めることができます。

左端がジョーカーの場合

ジョーカーそれぞれを X1, X2 で区別するとします。
その場合、左端にくるジョーカーは X1, X2 どちらか 2 通りです。

どちらか選んだら、残り 4 枚は自由に並べることができます。
なので 左端のジョーカーの選び方 * 残り 4 枚の置換 です。

これを数式にすると 2 * 4P4 で、これは 2 * 4! で計算できます。
左端がジョーカーの場合の順列は 48 通りです。

右端がジョーカーの場合

左右入れ替わるだけなので、こちらも同じ計算方法です。
右端がジョーカーの場合の順列は 48 通りです。

両端がジョーカーの場合

「少なくとも一端がジョーカー」という条件には、両端がジョーカーの場合も含まれます。
両端のジョーカーの並べ方は 2P2 通りですね。

両端のジョーカーが決まったら、残り 3 枚は自由に並べることができます。
なので 両端のジョーカーの選び方 * 残り 3 枚の置換 です。

これを数式にすると 2P2 * 3P3 で、これは 2! * 3! で計算できます。
両端がジョーカーの場合の順列は 12 通りです。

左端・右端のときの並べ方を合わせると 48 + 48 で 96 通りになりますが、
それぞれの並べ方には「両端がジョーカーの場合」が含まれています。

単純に足し算すると、「両端がジョーカーの場合」が重複するので引き算してあげる必要があります。
よって 96 - 12 で 84 通りです。

「包含と排除の原理」については、こちらの記事参照

最後にジョーカー 2 枚の重複度 2P2 で割ればいいので、答えは 84 / 2 で 42 通りです。

論理を使う

「少なくとも一端がジョーカーになる」の否定は「両端ともジョーカーではない」です。

なので「すべての並べ方の数」から「両端ともジョーカーではない」を引き算すると「少なくとも一端がジョーカーになる」を求めることができます。

「否定の論理」については、こちらの記事参照

すべての並べ方

5 枚を区別して置換を求め、ジョーカーの重複度 2 で割ることで組み合わせがわかります。
よって 5P5/2 を計算して、5! / 2 から 60 通り、と求めることができます。

両端ともジョーカーではない並べ方

ジョーカーではないカードは J, Q, K の 3 枚です。
このうちの 2 枚が両端に選ばれるのは 3P2 通りです。

残りは 3 枚なので、それは 3P3 通りあります。

この 2 つを掛けて、ジョーカーの重複度 2 で割ることで組み合わせがわかります。
よって (3P2 * 3P3) / 2 を計算して 18 通り、と求めることができます。

「少なくとも一端がジョーカーになる」は「すべての並べ方の数」から「両端ともジョーカーではない」を引けばよかったので、答えは 60 - 18 で 42 通りです。

CS シリーズ

次回

前回

お仕事ください!

僕が代表を務める 株式会社 EeeeG では Web 制作・システム開発・マーケティング相談を行っています。
なにかお困りごとがあれば、Twitter DM や Web サイトからお気軽にご相談ください。

コメント

コメントを残す

*