[ITパスポート]情報数学(順列・組合せ)[無料講座]

2020年2月15日

今回はITパスポート順列と組合せについて学習します。

くろん
くろん
この〇通りの中から△個選ぶ選び方とかってなんだにゃ?
キュー
キュー
これは順列と組み合わせの問題やな。前回の論理演算同様に数学要素があるからしっかりと対策していこう

情報数学(順列・組合せ)

順列と組合せは高校数学でも取り扱う分野で、コンビネーション(C)やパーミテーション(P)と言った記号を目にしたこともあるかなと思います。

この考え方がITと何に関係あるのかなと思われると思いますが、身近な例を挙げるとパスワードのパターンがあります。

例えばアルファベット26文字(a~z)を用いて8桁のパスワードを構成する場合、そのパスワードのパターンはいくつあるかと言った問題では組み合わせの概念を用います。

順列

順列は互いに異なるnこの中からr個を取り出して1列に並べる時を考慮します。

例えば1~9のカードが1枚ずつあり、そこから3枚取り出して順に並べ3桁の数字にする。と言ったような考え方をするとき順列の考え方になります。

カズ
カズ
最初に3、次に5、最後に7を取り出した場合は357に、最初に7、次に5、最後に3を取り出した場合は753になるから順番が大事なんだね!

順列にはさらに重複を許す場合と許さない場合があるので、それぞれのパターンを例を通して見てみましょう。

重複を許さない場合

以下のような場合は重複を許しません。

1~9の数字が書かれたカードがある。このうち3枚のカードを取り出して並べることで3桁の数字を作るとき,全部で何通りの数字を作れるか。

1枚目を選ぶときは9枚の中から選ぶため9パターンあります。

[1] [2] [3] [4] [5] [6] [7] [8] [9] → [3]

2枚目は1枚目がなくなった状態の8パターンから選ぶことになります。

[1] [2] [4] [5] [6] [7] [8] [9] → [8]

3枚目は1枚目と2枚目がなくなった状態の7パターンから選ぶことになります。

[1] [2] [4] [5] [6] [7] [9] → [7]

これを計算すると9×8×7=504通りとなります。

一般式に落とし込むと

n個の物からr個取る順列の、重複を許さないときの個数は以下のような式になります。

\[n×(n-1)×(n-2)×・・・×(n-r+1)\]

ここで項の数はr個になります。

重複を許す場合

以下のような場合は重複を許します。

1~9の数字が書かれたカードがある。カードを1枚選び、そのカードの数字を記録してから元に戻す作業を3回繰り返す。この時何パターンの数字を作れるか。

この場合も流れを見ていきましょう。

1枚目を選ぶときは9枚の中から選ぶため9パターンあります。

[1] [2] [3] [4] [5] [6] [7] [8] [9] → [8]

2枚目を選ぶときも、1枚目のカードは戻っているため、9枚の中から選ぶことになります。よって9パターンあります。

[1] [2] [3] [4] [5] [6] [7] [8] [9] → [3]

3枚目を選ぶときも、1枚目と2枚目のカードは戻っているため、9枚の中から選ぶことになります。こちらも9パターンあります。

[1] [2] [3] [4] [5] [6] [7] [8] [9] → [8]

これを計算すると9×9×9=729通りとなります。

一般式に落とし込むと

n個の物からr個取る順列の、重複を許すときの個数は以下のような式になります。

\[n×n×n×・・・=n^r\]

となります。

組合せ

次は組み合わせです。組み合わせの場合は順番を気にしない考え方になるので、カードを用いるより別の物を用いて考えるのが良いでしょう。

9本のゲームがある。この中から3本選ぶ組合せは何通りあるか

このような問題の場合、取り出す順番は気になりませんよね。

例えば[DO1][DO2][DO3][DO4][DO5][DO6][DO7][DO8][DO9]と言ったゲームタイトルが9本あったとして、[DO4][DO7][DO8]の順で選んでも[DO7][DO8][DO4]の順で選んでも本質は同じです。

この時の選び方を見てみましょう。

まず単純に、9本の中から3本選ぶ順列の組み合わせは、順列で求めた通り

9×8×7で504通りとなります。

次に、3本選ぶときに何通りの重複があるかを見てみます。

例えば[DO4][DO7][DO8]と[DO7][DO8][DO4]は同じでした。

他の組み合わせとしても考えられるのはあり、全て列挙すると

(4,7,8)、(4,8,7)、(7,4,8)、(7,8,4)、(8,4,7)、(8,7,4)の6パターンとなります。

今回は全て書き出しましたが、ここでも実は順列の考え方を用いることが出来ます。

3種類の物から3通り選ぶことになるので、3×2×1となります。

504通りあるうち、重複している順列パターンが6通りあるので\(\frac{504}{6}=84\)が正解となります。

これを一般式に落とし込むと、

\[\frac{n×(n-1)×(n-2)×・・・×(n-r+1)}{r×(r-1)×(r-2)×・・・×1}\]

となります。分子分母の項数はそれぞれr個となります。

カズ
カズ
大学受験とかだと難しい制約が付くけど、ITパスポートではそんなことあまりないから気にしなくていいよ!
スポンサーリンク

情報数学(順列・組合せ)・例題

実際に例題を解いて問題に慣れていきましょう。

問題

問1

4文字のパスワードに関して,0~9の数字だけを使用した場合に比べ,0~9の数字の他にa~fの英小文字6文字も使用できるようにした場合は,組合せの数はおよそ何倍になるか。(H.24/秋)

ア 1.6
イ 6.6
ウ 8.7
エ 16.0

問2

a,b,c,d,e,fの6文字を任意の順で1列に並べたとき,aとbが隣同士になる場合は,何通りか。(H.26/春)

ア 120
イ 240
ウ 720
エ 1,440

問3

共通鍵暗号方式では通信の組合せごとに鍵が1個必要になる。例えばA~Dの4人が相互に通信を行う場合は,AB,AC,AD,BC,BD,CDの組合せの6個の鍵が必要である。10人が相互に通信を行うためには何個の鍵が必要か。(H.22/春)

ア 15
イ 20
ウ 45
エ 50

解説(クリックで展開)

コンテンツのディジタル化・まとめ

今回は情報数学の順列・組合せについて学習しました。

パスワードの組み合わせや鍵の本数などで頻出事項なのでしっかりと押さえて置いてください。

カズ
カズ
問題文をしっかり読んでどの条件かも判断できるようにしておこう!

次回からはハードウェアについて学習していきます。


スポンサーリンク