場合の数(順列)

  1. 場合の数


     コインを投げて、裏がでるか表がでるかはランダムですが、裏ばかり表ばかりが10回以上続くことは希です。このような現象は、まず、すべての場合を数え上げることから解析が始まります。
     ここでは、典型的な数え上げの手法を紹介します。

  2. 階乗


    1. 階乗(factorial)の計算

      nから1づつ減らしながら1までかけた数
            n・(n-1)・(n-2)・3・2・1
      を n ! と表しnの階乗(factorial)とよびます。

       n ! = n・(n-1)・(n-2)・3・2・1
         ただし、 0 ! は1とします。

    2. 計算

       5! を計算して下さい。

  3. 順列(Permutation)


    1. 順列

      異なる n 個のものから r 個とって1列に並べた数字の列を順列といいます。例えば、1,2,3 の数から 2個を取り出し並べると以下の6通りの場合があります。ここで、同じ数を重複して取り出すことはできないモノとします。
       1,2 1,3
       2,1 2,3
       3,1 3,2
      また、A B C D の4枚から2枚を取り出す方法は、次の12通りです。
       A B  ,  A C  , A D
       B A  ,  B C  , B D
       C A  ,  C B  , C D
       D A  ,  D B  , D C

    2. 順列の数

      異なる n 個から、最初の数の取り出し方は n 通りあります。次の数は、残りの n-1 個から選びますから n-1 通りになります。したがって、n個のものから2個とって1列に並べるとき、可能な数字の数は n・(n-1) になります。
       これを続けると、異なるn個のものからr個とって1列に並べるとき、異なる数字の数は
            n・(n-1)・(n-2)・・(n-r +1)
      となります。この数を nPr と表します。P はpermutation(入れ替え)の略です。これは ! を用いると、次のように計算できます。

        nPr = n・(n - 1)・(n - 2)・・(n - r + 1) = n ! / (n-r) !

    3. 計算

       4P24P3、を計算してください。

    4. 別の定義

       一つの箱に1個の球をおく場合を考えます。n 個の箱に r 個の球を置く場合の数は nPr となります。

  4. 順列の例


    1. 例題1

      0 から 6 までの7個の数字を取り出して並べるとき,すべての数字が異なる4けたの整数の個数を求めなさい。

      ■ 
      4桁の数字なので,千の位には0を使うことができません.そこで千の位は1から6までの6個の中から1個選ぶことになるので,6通りです。.
       百の位から一の位までは0から6までのどの数字も使うことができます.しかし,同じ数字は2度使えないことに注意して下さい。百の位には千の位で用いられた数字以外どれでも使えるので,6通りあります。十の位は千の位と百の位で用いられた数字以外どれでも使えるので5通り、最後に一の位はすでに用いられたもの以外すべて使えるので4通り。よって全部で
            6・6・5・4 = 720
      個の4桁の数字を作ることができます.
       
      別解:
       百の位,十の位,一の位は千の位で用いられた数字以外どれでも1回づつ使うことができることに注意すると,6個の中から3個を取り出し順序をつけて並べる順列の数になるので 6P3 と表わせます。
      よって6・ 6P3 = 6・6・5・4 = 720

    2. 問題
       すべての異なる数字からなる4桁の10進数の数を求めなさい。4桁の数ですから、先頭の桁は0ではいけません。

      ■ 答え:4536

    3. 例題2

      0 から 6 までの7個の数字を取り出して並べるとき,5で割り切れる4けたの整数の個数を求めなさい。
      ヒント:5の倍数は一の位が必ず,0か5になることに注意します。


      一の位が0の場合と5の場合を別々に考えます.
      ●一の位が0の場合.
      千の位,百の位,十の位は1から6までの数字を1回づつ使うことができるので,6個の中から3個を取り出し並べる順列の数になるので 6P3 と表わせます.よって 120通り

      ●一の位が5の場合.
      千の位に0が使えないので,千の位は0,5以外の5通り,百と十の位は一と千の位で用いた数字以外どれでも1回づつ使えるので 5P2 通り。よって 5・5P2 =100 通りとなります。

      ここで,一の位が0の場合と5の場合は同時にはおきないので,全部で
        120+100   通り

    4. 例題3

       異なる4個のアルファベット(a..z)に続けて異なる3個の数字を1列に並べる並べ方の数を求めなさい。

      答え: 25,776,000

  5. 重複順列


    1. 重複順列(制限がない場合)

       n 枚から r 枚を取り出すとき、重複が許される場合、つまり、同じ数が何回でも利用できる場合、重複順列と呼びます。n枚からr枚を取り出す重複順列の数は nr となります。

    2. 例題

       4個の数字から構成される数がある。4個の数字の中に同じ数が含まれる数の集合を求めなさい。

      ■4個の数字から構成される数字の数は 104 ある。このうち、4個すべて異なる数は、10P4 となります。したがって、少なくても一つ同じ数が含まれる場合の数は
       
       104 - 10P4 = 4960

    3. 重複順列(重複に制限がある場合)

      r個の球のうち、q1 個は第一の色、q2 は第二の色、qt は第三 の色とします。n個の箱に r 個の球を入れるとき異なる並べ方の数は、(同じ色の球は区別ができませんから)、

       nPr / (q1! q2! .. qr!)
       ただし、 r = q1 + q2 + ..  + qt

      となります。q1! は同じ色の数の並びになり区別がつきません。どうように、q2!、..、qt! は同じ色のならびになります。

    4. 例題

      3個のスペースと2個のマークから構成される符号の数の総数を求めなさい。

       5! /(3! ・ 2!) = 10

  6. 組み合わせ


    1. 組み合わせとは

       n 個から r 個取り出すとき、取り出した順序には無関係に、集合として異なる場合のみを数えるとき、組み合わせ(combination)といいます。

       例えば、1,2,3 枚から2枚を取り出す場合、順列としては、1,2 と 2,1 は別と考えますが、組み合わせとしては同じと考えます。したがって以下の3通りになります。
       1,2 1,3
          2,3
      また、A B C D の4枚から2枚を取り出す組み合わせの数は、次の6通りです。
           A B  ,  A C  , A D
          ,  B C  , B D
          ,     , C D

    2. 組み合わせの数

      異なる n 個のものから r 個とる順列の数は

        Pr = n!/ (n-r) !

      でした。r 個の組み合わせの数は 並び順のみが異なる「場合」は同じ「場合」として扱います。r 個の並びの数は r ! ですから、組み合わせの数は Pr を r ! で割った数になります。 n 個のものから r 個とる組み合わせの数を Cr と書きます。これは、以下のように計算できます。

       Cr = Pr /r ! = n!/ ((n-r) ! ・ r !)

    3. 例題1

      1から10までの番号のついたカードから6枚を取り出すときの場合の数を求めます
      1から10までの番号のついたカードから6枚を取り出すとき,何通りの取り出し方があるかを考えます.このとき,一枚づつ順に取り出し並べるわけではないので,取り出す順序を考える必要はありません。よって,何通りの組み合わせがあるかを考えればよいでしょう.10個の中から6個を取り出す組み合わせなので,
       10C6 = 210 となります。

    4. 例題2

      1から10までの番号のついたカードから6枚を取り出すときの場合、1と2を含む場合の数を求める。

      1 と 2 のカードを含むとは取り出した6枚の中に必ず 1 と 2 のカードが入っていなければならないということです.これは1と2を先に引いておいて残りの4枚を3から10までの8枚から選ぶ選び方と考えることができます。よって 8C = 70通り。

    5. 例題3

      1から10までの番号のついたカードから6枚を取り出すときの場合、1または2を含む場合の数を求める。

      1のカードを含む場合をc1,2のカードを含む場合をc2とします。するとc1は 9C5 通り,c2も 9C5 通りとなるので,1または2を含む場合は 、共に含む場合を差し引く必要があるので、

       9C5 + 9C5 -70 = 182

       となります。

    6. 例題4

      1枚の硬貨を5回投げるとき,表の出る回数が0回,1回,2回,3回,4回,5回の場合は何通りあるか求めよう.


       n個から順番を考えずにr枚を取り出す組み合わせの数になりますから、表の回数がrである場合の数は、5Cr になります。

      5C0 = 5C5 = 1、5C1 = 5C4 = 5、5C2 = 5C3 = 10 となります。

  7. 応用ポーカー(トランプ)の役


    1. 引用

      この項は http://www.kjps.net/user/kakuritsu/poker.html から引用させて頂きました。

    2. ポーカーの役

      トランプのポーカーでいろいろな役のできる場合の数を計算しましょう。トランプカード(正確には playing card)にはクラブ、ハート、スペード、ダイヤの4種のスートがあります。ポーカーの役には次のようなものがあります。
      • ワンペア
         同じ数のカードが2枚そろったとき。
      • ツーペア
         ワンペアが2組できたとき。
      • スリーカード
         同じ数のカードが3枚そろったとき。
      • フラッシュ
         5枚全て同じ種類のスートがそろったとき。
      • ストレート
         5枚の番号が続いたとき。
      • フルハウス
         ワンペアとスリーカードができたとき。
      • フォーカード
         4枚、同じ数のカードがそろったとき。
      • ストレート・フラッシュ
         同じスートで5枚の番号が続いたとき。K,A,2,3,4 など、Aからの折り返しはなしとします。
      • ロイヤル・ストレート・フラッシュ
         同じスートのA,K,Q,J,10がそろったとき。

    3. 役の計算


      ●すべての場合
       52枚から5枚を取り出す方法は 525=2,598,960 です。ジョーカーは利用しないモノとします。

      ●ロイヤル・ストレート・フラッシュ:ROYAL STRAIGHT FLUSH
      4種類のスーツのそれぞれで(1,10,11,12,13)であるから、4通り。
      したがって 確率 1/649740

      ●ストレート・フラッシュ:STRAIGHT FLUSH
      同一種類の札ばかりで、数字が順番に並ぶ役札。 例えばハートでは

      1,2,3,4,5
      2,3,4,5,6
      3,4,5,6,7
      4,5,6,7,8
      5,6,7,8,9
      6,7,8,9,10
      7,8,9,10,11
      8,9,10,11,12
      9,10,11,12,13

      ですから 9 通りです。
      これが4種類で、9×4=36 通り。
       確率は 1/72193

      ●フォーカード:4 OF A KIND
      同一数の札4枚と、他の1枚とでできてる役札です。

      1a ,☆2a,☆3a,☆4a,★
      (1≦a≦13)☆、★はハート、ダイヤ、クラブ、スペードのどれか。

      同一の数は、1〜Kの13通り。
      残りのカードの1枚は 52−4=48 通り。

      13×48=624 ですから 確率は 1/4165

      ●フルハウス:FULL HOUSE
      同一数の札2枚と、それ以外の同一数の札3枚からできている役札。

      1a ,☆ 2a ,★ 1b ,★ 2b ,★ 3b (1≦a≦13),(1≦b≦13),(a≠b)
      ☆、★はハート、ダイヤ、クラブ、スペードのどれか。

      4枚の違った種類の札から、同じ数字の札を2枚選ぶ場合を考えると、42 で6通り。 それが1〜Kまで13通りあるから 6×13=78
       後の3枚の計算になりますが、上の計算で2枚使った数以外の数は12通り。 それぞれの数に4種類のスーツがありますから、 12×43=48
      全体を計算すると
       (42×13)×(43×12)=78×48=3744

      したがって 確率 1/694 

      ●フラッシュ:FLUSH
      同一種類の札だけでできており、ROYAL STRAIGHT FLUSH、STRAIGHT FLUSH以外の役札

      a ,☆ b ,☆ c ,☆ d ,☆ e
      (1≦a≦9),(a<b<c<d<e),(e≦13)
      ☆はハート、ダイヤ、クラブ、スペードのどれか。

      一種類の札で考えると、13枚から5枚取り出す場合は 135=1287
      4種類のスーツがあるから、1287×4=5148
      そこから ROYAL STRAIGHT FLUSH と STRAIGHT FLUSH を引くと、
       5148−(4+36)=5108
      したがって 確率 1/509

      ●ストレート:STRAIGHT
      ROYAL STRAIGHT FLUSHやSTRAIGHT FLUSHと同様な数字の並びで、同一種類でない札が1枚以上ある役

      ☆1 ,☆10 ,☆11 ,☆12 ,☆13
      ☆a+0,☆a+1,☆a+2,☆a+3,☆a+4
      (1≦a≦9) ☆はハート、ダイヤ、クラブ、スペードのどれかで、少なくとも1枚は同種類でない。

      一つの種類の札で考えると数字の並びは {13-(5-1)}+1=10 通りあります。
      それぞれ札は4通りのスーツがあるから、45=1024 通りで 計 10×1024=10240になります。
      この中からROYAL STRAIGHT FLUSHやSTRAIGHT FLUSHの40通り分を引かなければならない。
      10240−40=10200
      したがって確率は 1/255

      ●スリーカード:3 OF A KIND
      同一数字が3枚ある役。
      例 ハートの2、ダイヤの2、クラブの2、他は自由
      1a ,☆ 2a ,☆ 3a ,★ x ,★ y
      (1≦a≦13),(x≠a,y≠a)
      ☆、★はハート、ダイヤ、クラブ、スペードのどれか。

      3枚となる数字の選び方は13通り、残りの2枚の数字の選び方は122=66通り。
      スートの選び方はそれぞれ4通りずつあるので、求める確率は、
       13*66*4*4*4/2598960=88/4165 およそ47回に一度の割合です。

      ●ツーペア:2 PAIRS
      同数のペアが二組となる役です。
      例 ハートの2、ダイヤの2、ハートの5とダイアの5、他は任意
      1a ,☆ 2a ,☆ 1b ,☆ 2b ,★
      (1≦a≦13),(1≦b≦13),(a≠b)
      ☆、★はハート、ダイヤ、クラブ、スペードのどれか。

      2枚同じとなる数字の選び方は 132=78通り、残り1枚の数字の選び方は11通り。
      スートの選び方は2枚組の方が42=6通りずつ、残り1枚も4通りあるので、求める確率は、
       (78*6*6)*(11*4)/2598960=198/4165 およそ21回に一度の割合です。

      ●ワンペア:1 PAIR
      同数のペアが一組。
      例 ハートの2、ダイヤの2 他は任意
      1a ,☆ 2a ,★ ,★ ,★
      (1≦a≦13) ☆、★はハート、ダイヤ、クラブ、スペードのどれか。

      5枚中同じ数が2枚1組あって、他の3枚はそれぞれ別の数のもの。
      2枚となる数字の選び方は13通り、1枚ずつとなる数字の選び方は123=220通り。
      スートの選び方は2枚組の方が42=6通り、1枚のもの4通りずつあるので、求める確率は、
      13*220*6*4*4*4/2598960=352/833 およそ2.4回に一度の割合です

      ●役なし:NO PAIR
      ALLから全ての役を引いた数で 1302540 となります。
      この確率は 1302540/259860 = 0.51で 約1/2 となります。