順列・組み合わせ【ITパスポート講座】
この記事で学ぶこと
- 順列
- 組み合わせ
- 重複ありとなし
今回はITパスポートの順列と組み合わせについて学習します。
順列・組み合わせ
順列と組み合わせは高校数学でも取り扱う分野で、パーミテーション(P)やコンビネーション(C)と表現します。
順列や組み合わせと、ITとの関係性については、身近な例を挙げるとパスワードのパターンがあります。
例えばアルファベット26文字（a～z）を用いて8桁のパスワードを構成する場合、そのパスワードのパターンはいくつあるかと言った問題では組み合わせの考え方を用います。
順列
順列は、互いに異なるn個の中からr個を取り出して1列に並べる時のパターンを考慮します。
例えば1～9のカードが1枚ずつあり、そこから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枚の中から選ぶため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\]
組み合わせ
次は組み合わせです。
組み合わせの場合は順番を気にしないので、カードを用いるより別の物を用いて考えるのが良いでしょう。
このような問題の場合、取り出す順番は気になりません。
例えば[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個となります。
順列・組み合わせの例題
実際に例題を解いて問題に慣れていきましょう。
問1
4文字のパスワードに関して，0～9の数字だけを使用した場合に比べ，0～9の数字の他にa～fの英小文字6文字も使用できるようにした場合は，組み合わせの数はおよそ何倍になるか。(H.24秋/問78)
ア：1.6
イ：6.6
ウ：8.7
エ：16.0
（ログイン後回答すると、ここに前回の正誤情報が表示されます）
問2
a，b，c，d，e，fの6文字を任意の順で1列に並べたとき，aとbが隣同士になる場合は，何通りか。(H.26春/問63)
ア：120
イ：240
ウ：720
エ：1,440
（ログイン後回答すると、ここに前回の正誤情報が表示されます）
問3
共通鍵暗号方式では通信の組み合わせごとに鍵が1個必要になる。例えばA～Dの4人が相互に通信を行う場合は，AB，AC，AD，BC，BD，CDの組み合わせの6個の鍵が必要である。10人が相互に通信を行うためには何個の鍵が必要か。(H.22春/問70)
ア：15
イ：20
ウ：45
エ：50
（ログイン後回答すると、ここに前回の正誤情報が表示されます）
共通鍵の本数を求める問題です。n人がn-1人とやり取りを行い、それぞれのカギ自体は共通しているため、以下の式で求められます。
\[\frac{n×(n-1)}{2×1}\]
公式に当てはめると\(\frac{10×9}{2×1}=45\)となり「ウ」が正解です。
因みに公開鍵の本数は2nです。両方頻出なので覚えてしまいましょう。
順列・組み合わせのまとめ
今回は順列・組み合わせについて学習しました。
パスワードの組み合わせや鍵の本数などで頻出事項なのでしっかりと覚えておきましょう。
次回はアルゴリズムとデータ構造について学習します。
福井県産。北海道に行ったり新潟に行ったりと、雪国を旅してます。
経理4年/インフラエンジニア7年(内4年は兼務)/ライター5年(副業)
簿記2級/FP2級/応用情報技術者/情報処理安全確保支援士/中小企業診断修得者 など
