場合の数(順列と組み合わせ)|やさしい基礎理論


2024-10-22 更新

この連載は、基本情報技術者試験の受験者を対象としたものです。
多くの受験者が苦手としている「情報の基礎理論」の分野から毎回1つずつテーマをあげて、やさしくポイント解説と問題解説を行います。
苦手分野を克服して、試験の得点をアップしましょう。

今回のテーマは、 「場合の数(順列と組み合わせ)」 です。

順列の求め方

基本情報技術者試験には、数学の問題が出ることがあります。
主なテーマは、「場合の数」「確率」「統計」などです。

今回は、場合の数を取り上げます。
中学で習ったはずなので、忘れてしまったという人も、ちょっと復習すれば、すぐに思い出せるでしょう。
問題のレベルも中学ぐらいなので、決して難しくありません。

場合の数とは、ある事柄について、考えられるすべての場合を数え上げた総数です。
場合の数には、「順列」と「組み合わせ」があります。

順列は、内容が同じでも、順序が異なれば違うものとします。
組み合わせは、内容が同じなら、順序が異なっても同じものとします。

たとえば、A、B、C、D、E、Fの5つのデータの中から3つを選ぶ場合に、順列では、「A、B、C」と「B、A、C」を違うものとしますが、組み合わせでは、それらを同じものとします。

はじめに、順列の求め方を説明しましょう。

A、B、C、D、E、Fという5つのデータの中ら3つを選ぶ順列は、1つ目の選び方が5通りで、2つ目の選び方が4通りで(既に5つの中から1つ目を選んでいるので、残りの4つの中から選ぶことになる)、3つ目の選び方が3通りなので(既に5つの中から1つ目と2つ目を選んでいるので、残り3つの中から選ぶことになる)、5×4×3=60通りです。

5×4×3=60通りという掛け算は、すべてのパターンを書き出した「樹形図」の枝の総数を求めているといえます。

60通りの樹形図を示すのは、困難なので、例を変えましょう。
図1に、A、B、Cという3つのデータの中ら2つを選ぶ順列(3×2=6通り)の樹形図を示します。

【図1】 3つのデータの中から2つを選ぶ順列の樹形図

1つ目の選び方は3通りなので、これが3つの枝分かれになります。
2つ目の選び方は2通りなので、これが2つの枝分かれになります。
3つに枝分かれしたそれぞれが、さらに2つに枝分かれするので、枝の総数は3×2=6本であり、順列は3×2=6通りです。

組み合わせの求め方

次に、組み合わせの求め方を説明しましょう。

A、B、C、D、E、Fという5つのデータの中ら3つを選ぶ順列は、先ほど説明したように、5×4×3=60通りです。
この60通りの中から1つのパターンを選んで、同じ内容で順序が異なるパターンがいくつできるかを求めてみましょう。

たとえば、「A、B、C」というパターンは、同じ内容で順序が異なるパターンが「A、B、C」「A、C、B」「B、A、C」「B、C、A」「C、A、B」「C、B、A」の60通りあります。
これは、A、B、Cという3つのデータの中ら3つを選ぶ順列であり、3×2×1=6通りです。
したがって、5つのデータの中ら3つを選ぶ順列の60通りの中には、同じ内容のものが6つずつあるので、それらを同じものとして1通りと数えれば、60÷6=10通りとなり、これが組み合わせです。

順列と組み合わせの求め方は、公式として示すこともできますが、公式を丸暗記するより感覚的に理解した方がよいでしょう。
暗記は、面白くないし、応用が利かないからです。

これまでの説明をまとめて感覚的に示すと、5つのデータの中ら3つを選ぶ順列は、1つ目が5通り、2つ目が4通り、3つ目が3通りなので、5×4×3=60通りです。
5つのデータの中ら3つを選ぶ組合せは、順列が5×4×3=60通りで、同じ内容で順序が異なるパターンが3×2×1=60通りあるので、60÷6=10通りです。

場合の数に関する問題の例(その1)

場合の数に関する問題を2つ紹介しましょう。
以下は、文字列のパターン数を求める問題です。文字列のパターンというものが、順列なのか組み合わせなのかを考えてください。

問2(出典:H20春問7)

2個の文字AとBを使って、長さ1以上7以下の文字列は何通りできるか。

    ア  128    イ  254    ウ  255    エ  256

文字列のパターンは、順列です。
なぜなら、長さ2文字の場合、「AB」と「BA」は異なる文字列だからです。

この問題では、長さ1文字以上7文字以下のパターンの総数を求めますが、一気に計算しようと考えずに、1文字なら何パターン、2文字なら何パターン、・・・、7文字なら何パターンと、文字数ごとにパターン数を求めて集計するとよいでしょう。

1文字のパターン数は、「A」と「B」の2通りです。
2文字のパターンは、1文字目が「A」と「B」の2通りで、2文字目も「A」と「B」の2通りなので、2×2=4通りです。
3文字のパターンは、1文字目が「A」と「B」の2通りで、2文字目も「A」と「B」の2通りで、3文字目も「A」と「B」の2通りなので、2×2×2=8通りです。

以下同様に、1文字から7文字におけるパターン数を求めると、図xxのようになります。

【図xx 1文字から7文字におけるパターン数】
1文字 2通り
2文字 2×2=4通り
3文字 2×2×2=8通り
4文字 2×2×2×2=16通り
5文字 2×2×2×2×2=32通り
6文字 2×2×2×2×2×2=64通り
7文字 2×2×2×2×2×2×2=128通り

すべてのパターン数を集計すると、2+4+8+16+32+128=254通りです。
したがって、選択肢イが正解です。

場合の数に関する問題の例(その2)

以下は、男女8人の中から3人を選ぶという問題です。
3人を選ぶということが、順列なのか組み合わせなのかを考えてください。
この問題には、男子が少なくとも1人含まれるという条件があることにも注意してください。

問2(出典:H18秋問7)

男子3人、女子5人の中から3人を選ぶとき、男子が少なくとも1人含まれる選び方は何通りあるか。

    ア  21    イ  30    ウ  46    エ  56

3人を選ぶというのは、選ぶだけであり順序を考慮しないので、組み合わせです。
ただし、単純に組み合わせを求めるのではなく、男子が少なくとも1人含まれるという条件を満たさなければなりません。

どうしたらよいでしょうか?

これは、言われてみれば「ああ、そうか!」と気付くと思いますが、すべての組み合わせを求めて、そこから女子だけの組み合わせを引けばよいのです。

男女8人の中から3人を選ぶ組合せは、(8×7×6)/(3×2×1)=56通りです。
女子5人の中から3人を選ぶ組合せは、(5×4×3)/(3×2×1)=10通りです。

したがって、男女8人の中から3人を選んだ組み合わせの中で、男子が少なくとも1人含まれているのは、56-10=46通りであり、選択肢ウが正解です。

基本情報技術者試験の公開問題を見ると、過去問題(過去の試験に出題された問題)の再利用が多いことがわかります。
したがって、試験に合格するために最も効率的で効果的な学習方法は、できなかった問題があれば、できるようになるまで練習することです。
もしも、今回取り上げた問題がすぐにできなかったら、できるようになるまで練習してください。

それでは、またお会いしましょう!

label 関連タグ
科目A試験は、
免除できます。
独習ゼミで科目A試験を1年間免除して、科目B試験だけに集中しましょう。
免除試験を受けた 74.9% の方が、
科目A免除資格を得ています。
※独習ゼミは、受験ナビ運営のSEプラスによる試験対策eラーニングです。
科目A免除試験 最大 2 回の
受験チャンス !
info_outline
科目A免除試験 最大 2 回の
受験チャンス !
詳しく見てみるplay_circle_filled
label これまでの『やさしい基礎理論』の連載一覧 label 著者