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

この連載は、基本情報技術者試験の受験者を対象としたものです。
多くの受験者が苦手としている「情報の基礎理論」の分野から毎回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通りなので、これが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 関連タグ免除試験を受けた 74.9% の方が、 科目A免除資格を得ています。
※独習ゼミは、受験ナビ運営のSEプラスによる試験対策eラーニングです。

『プログラムはなぜ動くのか』(日経BP)が大ベストセラー
IT技術を楽しく・分かりやすく教える“自称ソフトウェア芸人”
大手電気メーカーでPCの製造、ソフトハウスでプログラマを経験。独立後、現在はアプリケーションの開発と販売に従事。その傍ら、書籍・雑誌の執筆、またセミナー講師として活躍。軽快な口調で、知識0ベースのITエンジニアや一般書店フェアなどの一般的なPCユーザの講習ではダントツの評価。
お客様の満足を何よりも大切にし、わかりやすい、のせるのが上手い自称ソフトウェア芸人。
主な著作物
- 「プログラムはなぜ動くのか」(日経BP)
- 「コンピュータはなぜ動くのか」(日経BP)
- 「出るとこだけ! 基本情報技術者」 (翔泳社)
- 「ベテランが丁寧に教えてくれる ハードウェアの知識と実務」(翔泳社)
- 「ifとelseの思考術」(ソフトバンククリエイティブ) など多数