こんにちは、ウチダです。
いつもお読みいただきましてありがとうございます。
さて、突然ですが、「同じものを含む順列」の公式は以下のようになります。
$a$ が $p$ 個、$b$ が $q$ 個、$c$ が $r$ 個あり、$p+q+r=n$ である。このとき、それら全部を $1$ 列に並べる順列の総数は$$\frac{n!}{p!q!r!}$$
この公式を見て、パッと意味が分かりますか？
よく
[ふきだし set=”悩む男性”]同じものを含む順列の公式の意味がわからないなぁ。なぜ階乗で割る必要があるんだろう…？？？[/ふきだし]
[ふきだし set=”悩む女性”]同じものを含む順列の基本問題はある程度解けるんだけど、応用になると一気に難しく感じてしまうわ。[/ふきだし]
こういった声を耳にします。
よって本記事では、同じものを含む順列の基本的な考え方から、応用問題の解き方まで、
- 東北大学理学部数学科卒
- 教員採用試験に１発合格 → 高校教諭経験アリ
- （専門は確率論でした。）
の僕がわかりやすく解説します。
同じものを含む順列は組合せと同じ！？【違いはありますか？】
さて、いきなり重要な結論です。
実は、$${}_n{C}_{p}×{}_{n-p}{C}_{q}=\frac{n!}{p!q!r!}$$なので、組合せの考え方と全く同じである。
一つお聞きしますが、同じものどうしの並び替えって発生しますか？
発生しない、というか考えちゃダメですよね。
それであれば、並び替えを考えない「組合せ」と等しくなるはずですよね。
単純にこういうロジックで成り立っています。
これが同じものを含む順列の基本的な理解です。
また、上の図のように理解してもいいですし、
一度区別をつける $→$ 区別をなくすために階乗で割る
こういうふうに考えることもできます。
以上 $2$ パターンどちらで考えても、冒頭に紹介した公式が導けます。
[ふきだし set=”ウチダ”]「同じものを含む順列」と言いながら、結局は順列ではなく「組合せ」なんですよね。名前に惑わされないように、順列と組合せの違いを本質的に学んでおく必要があります。詳しくは「順列と組合せの違いとその公式とは【応用問題５選もあわせて解説】」の記事をご覧ください。[/ふきだし]
同じものを含む順列の基本問題１選
「公式が成り立つ論理構造」は掴めたでしょうか。
ここからは実際に、よく出題されやすい問題を解いて知識を定着させていきましょう。
(1) すべての並べ方は何通りあるか。
(2) 母音の e，i，i がこの順に並ぶ場合の数を求めよ。
英単語の「beginning」について、並び替えを考えましょう。
[ふきだし set=”ウチダ”]…これは「beginning」違いですね。(笑)ワンオク愛が出てしまいました、、、[/ふきだし]
【解答】
(1) n が $3$ 個、i が $2$ 個、g が $2$ 個含まれている順列なので、$$\frac{9!}{3!2!2!}=\frac{9・8・7・6・5・4}{2・2}=15120 (通り)$$
(2) 「 e、i、i がこの順に並ぶ」ということは、この $3$ 文字を統一して、たとえば X のように置いて考えられるということ。
したがって、n が $3$ 個、X が $3$ 個、g が $2$ 個含まれている順列なので、
$$\frac{9!}{3!3!2!}=\frac{9・8・7・6・5・4}{3・2・2}=5040 (通り)$$
(解答終了)
さて、(2)の解き方は理解できましたか？
- 一定の順序を含む $→$ 並び替えが発生しない。
- 並び替えがない $→$ 組合せで考えられる。
- 組合せの発想 $→$ 同じものを含む順列。
連想ゲームみたいに頭の中を整理していけば、同じ文字 X に統一して議論できる理由がわかりますね＾＾
同じものを含む順列の応用問題３選
では次に、同じものを含む順列の応用問題について考えていきましょう。
具体的には、
- 隣り合わない文字列の問題
- 最短経路問題
- 整数を作る問題【難しい】
以上 $3$ つを解説します。
隣り合わない文字列の問題
(1) 子音の s，c，h，l がこの順に並ぶ場合の数を求めよ。
(2) 母音の o，o が隣り合わない並べ方は何通りあるか。
またやってきましたね。文字列の問題です。
(1)は復習も兼ねていますので、問題なのは(2)です。
「隣り合わない」をどうとらえればよいか、ぜひじっくりと考えてみて下さい。
↓↓↓
【解答】
(1) 子音の s，c，h，l を文字 X で統一する。
よって、X が $4$ 個、o が $2$ 個含まれている順列なので、
$$\frac{6!}{4!2!}=\frac{6・5}{2・1}=15 (通り)$$
(2) 全体の場合の数から、隣り合う場合の数を引いて求める。
ⅰ）全体の場合の数は、o が $2$ 個含まれている順列なので、
$\displaystyle \frac{6!}{2!}=360$ 通り。
ⅱ）隣り合う場合の数は、oo を一まとめにして考える。
つまり、新たな文字 Y を使って、oo $=$ Y と置く。
よって、異なる $5$ 文字の順列の総数となるので、$5!=120$ 通り。
したがってⅰ）ⅱ）より、$360-120=240$ 通り。
(解答終了)
問題によっては、隣り合わない場合の数を直接求めることもありますが、基本は
「全体の場合の数から隣り合う場合の数を引く」
これでほぼほぼ解けます。
【重要】最短経路問題
最短経路の問題は、重要な応用問題として非常によく出題されます。
まずはためしに、一番簡単な最短経路の問題に挑戦です！
↓↓↓
【解答】
$A$ から $B$ まで遠回りをしないで行くのに、「右に $6$ 回、上に $4$ 回」進む必要がある。
ちなみに、上の図の場合は$$→→↑→↑↑→→↑→$$という順列になっている。
したがって、同じものを含む順列の総数の公式より、$$\frac{10!}{6!4!}=\frac{10・9・8・7}{4・3・2・1}=210 (通り)$$
(解答終了)
[ふきだし set=”ウチダ”]最短経路問題は、「この道を通るように」や「この道を通らないように」など、非常に応用が利きやすい問題でもあります。「最短経路問題の応用（池がある場合）の解き方とは【わかりやすく解説】」の記事を参考に、ぜひ色んな問題パターンに触れてみてください。[/ふきだし]
整数を作る問題【難しい】
それでは最後に、本記事において一番難しいであろう問題を取り扱っていきます。
たとえば「 $0$，$1$，$2$ を無制限に使ってよい」という条件であれば、結構簡単に求めることができるのですが…
- $0$ は $1$ 個
- $1$ は $3$ 個
- $2$ は $2$ 個
と個数にばらつきがあります。
こういう問題は、大体場合分けが必要になってきます。
【解答】
注意点を $2$ つまとめる。
- 最上位は $0$ ではない。
- 偶数なので、一の位が $0$ または $2$
したがって、一の位で場合分けが必要である。
ⅰ）一の位が $0$ の場合
残り $1$，$1$，$1$，$2$，$2$ の順列の総数になるので、$\displaystyle \frac{5!}{3!2!}=10$ 通り。
ⅱ）一の位が $2$ の場合
残りが $0$，$1$，$1$，$1$，$2$ となるので、最上位の数にまた注意が必要となる。
- 最上位の数が $1$ の場合
残り $0$，$1$，$1$，$2$ の順列の総数になるので、$\displaystyle \frac{4!}{2!}=12$ 通り。 - 最上位の数が $2$ の場合
残り $0$，$1$，$1$，$1$ の順列の総数になるので、$\displaystyle \frac{4!}{3!}=4$ 通り。
①、②を合わせて、$12+4=16$ 通り。
したがってⅰ）ⅱ）より、$10+16=26$ 通りである。
(解答終了)
[ふきだし set=”ウチダ”]もっともっと複雑な問題もいくらでも作れますが、ここでは「場合分け」の必要性を感じていただきたく思います。使う数字の個数に制限がない問題については「重複順列の問題６選とは【公式よりも応用問題の解き方が大切です】」の記事をご覧ください。[/ふきだし]
同じものを含む順列に関するまとめ
本記事の結論を改めて記そうと思います。
- 組合せと”同じ”（”同じ”ものを含む順列だけに…すいません。。。）
- 整数を作る問題は場合分けが必要になってくる。
本記事で応用問題の解き方のコツを掴んでいきましょうね！
「場合の数」全 12 記事をまとめました。こちらから次の記事をCHECK!!
以上、ウチダでした～。
コメントを残す
コメント一覧 （2件）
隣り合わないの２は、
3+3+2なので、分子は8だと思います。
よって、1680だと思うのですが。
何度検算してもあわなかったので。
勉強中さん、コメントありがとうございます！
ごめんなさい、3+3+2の意味がよくわかりません。
あと、全体の場合の数が360なので、それを超えることはありえません。
ご確認ください。