順列と組み合わせ―順列pと組み合わせcの違い、問題など

トップ 情報処理の知識体系 テクノロジ系 基礎理論 応用数学 確率と統計 確率 順列と組み合わせ

ある事象が何通りの起こり方があるか、場合の数の数え方には順列と組み合わせがあります。順列pと組み合わせcの違いや計算などをまとめています。

▲記事トップへ

目次

この記事の目次です。

1. 順列―計算方法
2. 組み合わせ
3. 組み合わせと順列との違いと計算方法
4. 順列と組み合わせに関連する問題・例題

もっと知識を広げるための参考
更新履歴

1. 順列―計算方法

順列はnPrと書いて、nPr＝n!/(n-r)!という式で計算します。

n個の異なるものからr個（r≦n）選んで並べる並べ方を表します。

たとえば、1,2,3を並べてできる順列は、123,132,213,231,312,321の6通りです。

3つのものを並べるとき、はじめの数の並び方は3通り、2番目は残りの2通り、3番目は残りの1通りです。

なので、3つのものの順列の個数は3×2×1＝6となります。

例では3個のものから3個選んで並べる並べ方なので3P3と書き、3!/(3-3)!という式で表します。

2. 組み合わせ

組み合わせとは、英語でcombinationといい、たとえば、a,b,cの3人から2人を選び出す方法は{a,b}、{b,c}、{c,a}の3通りが考えられます。 このような個々の取り出し方のことを組み合わせといいます。

組み合わせの個数はnCrで表されます。 上述の例の場合、3C2＝3となります。

またn!＝1・2・3・・・・n（nの階乗）とするとき、nCrは以下の式で表せます。

nCr　＝　n!／r!(n-r)!　＝　（n(n-1)(n-2)・・・(n-r+1)）／r!

3. 組合せ―順列との違いと計算方法

組合せは順列と違って、順番は関係なく、あるかたまりからいくつか取り出す取り出し方になります。

汎用的に書いた式は「nCr＝nPr/r!」です。

最短経路は何通りかの問題の解き方

このような最短経路の数が何通りあるかを求める問題は組み合わせの問題の解き方を使って解きます。

ある地点を通る問題の解き方（積の法則を使用する）

例えば、家を出て駅に行って学校にいくみたいに、駅というある地点を通る経路数が何通りあるかを求めるとします。 その場合、家から駅に行く経路の数×駅から学校に行く経路の数となります。家から駅が3通り、駅から学校が2通りだとしたら、3×2の6通りとなります。

このように途中で分岐点を通過する経路の数は分岐前の数と分岐後の数の掛け合わせで求められます。 これを積の法則といいます。

4. 順列と組み合わせに関連する問題・例題

以下では順列と組み合わせに関連したIPA情報処理試験の過去問とその解説をまとめています。

• 平成27年春 問2 確率と統計―情報処理試験（高度共通）

  平成27年春 問2 確率と統計―情報処理試験（高度共通）の過去問と解説を掲載しています。

• 平成21年春 問4 部分文字列は全部で幾つあるかを表す式―応用情報技術者 午前

  平成21年春期応用情報技術者の問題(問4 場合の数)とその解説を掲載しています。

• 平成20年秋 問5 最短経路は何通りあるか（組み合わせの数の問題）―ソフトウェア開発技術者 午前

  平成21年春期応用情報技術者の問題(問4 場合の数)とその解説を掲載しています。

もっと知識を広げるための参考

• 応用数学

  応用数学とは何かをテーマにオリジナル教科書＆情報処理試験の問題解説をまとめています。

• テクノロジ系

  情報処理試験対策用のサイトオリジナル教科書をテーマにテクノロジ系の知識をまとめています。

更新履歴

• 2017年07月30日 最短経路は何通りかの問題の解き方について追記しました。
• 2017年07月05日 組み合わせとはの説明を追記しました。
• 2017年03月28日 組み合わせ関連の問題を追加しました。
• 2016年05月07日 ページをUPしました。

戻る