場合の数 | きょうさい対策ブログ

◯順列

(1) いくつかのものを順序をつけて並べたものを順列という．
(2) 異なる \( \displaystyle n \) 個のものを並べる順列の総数は，
\( \displaystyle n! = n \cdot (n – 1) \cdot (n – 2) \cdot \cdots \cdot 2 \cdot 1 \) 通り
(3) 異なる \( \displaystyle n \) 個のものから \( \displaystyle r \) 個を選んで並べる順列の総数は，
\( \displaystyle {}_{n}\mathrm{P}_{r} = n \cdot (n – 1) \cdot (n – 2) \cdot \cdots \cdot (n – r + 1) = \frac{n!}{(n – r)!} \) 通り
(4) \( \displaystyle 0! = 1 \), \( \displaystyle {}_{n}\mathrm{P}_{0} = 1 \) と定める．

補足(クリックして下さい)

※(補足)「 \( \displaystyle 0! \) 」など，新しい数・記号が出たときは，出来上がっている公式(規則)が拡張できるように定義することが多い．
式 \( \displaystyle n \cdot (n – 1)! = n! \) で \( \displaystyle n = 1 \) とすると，\( \displaystyle 0! = 1 \) である(ので，\( \displaystyle 0! = 1 \) と定義する)．また，\( \displaystyle {}_{n}\mathrm{P}_{r} = \frac{n!}{(n – r)!} \) で \( \displaystyle r = 0 \) とすると，\( \displaystyle {}_{n}\mathrm{P}_{0} = \frac{n!}{n!} = 1 \) となる(ので，\( \displaystyle {}_{n}\mathrm{P}_{0} = 1 \) と定義する．)

(例)男子\( \displaystyle 4 \)人，女子\( \displaystyle 3 \)人を\( \displaystyle 1 \)列に並べるとき，次の並べ方が何通りあるか求める．
(1) 女子\( \displaystyle 3 \)人が隣り合う並べ方
(2) 女子がどの\( \displaystyle 2 \)人も隣り合わない並べ方

説明例(クリックして下さい)

(1) 女子3人を並べる方法は \( \displaystyle 3! \) 通り，女子3人をまとめた1組と男子4人を並べる方法は \( \displaystyle 5! \) 通りであるから，求める場合の数は，
\( \displaystyle 3! \times 5! = 6 \times 120 = 720 \) 通り (答)
(2)男子4人を並べる方法は \( \displaystyle 4! \) 通り，男子の両端または間の5か所から3か所を選んで女子3人を並べる方法は \( \displaystyle {}_{5}\mathrm{P}_{3} \) 通りであるから，
\( \displaystyle 4! \times {}_{5}\mathrm{P}_{3} = 24 \times 5 \cdot 4 \cdot 3 = 1440 \) 通り (答)

※上の例のように，「隣り合う」処理はひとまとまりにする，「どの２要素も隣り合わない」は隙間に並べる，が典型的な処理．

◯組合せ

(1)いくつかのものを，順序を考えずに選んだ組を組合せという.
(2)異なる \( \displaystyle n \) 個のものから \( \displaystyle r \) 個を選ぶ組合せの総数は，
\( \displaystyle {}_{n}\mathrm{C}_{r} = \frac{{}_{n}\mathrm{P}_{r}}{r!} = \frac{n(n – 1) \cdots (n – r + 1)}{r!} = \frac{n!}{r!(n – r)!} \) 通り
(3) \( \displaystyle {}_{n}\mathrm{C}_{0} = 1 \) と定める.

補足(クリックして下さい)

※\( \displaystyle {}_{n}\mathrm{C}_{r}=\frac{n!}{r!(n-r)!} \) で \( \displaystyle r=0 \) とすると，\( \displaystyle {}_{n}\mathrm{C}_{0}=\frac{n!}{0!n!}=1 \) となる(ので，\( \displaystyle {}_{n}\mathrm{C}_{0}=1 \)と定義する)．
※定義から \( \displaystyle {}_{n}\mathrm{C}_{r}={}_{n}\mathrm{C}_{n-r} \) であることが分かる．\( \displaystyle r \) が大きいときは，この公式を用いて計算することが多い．
※「異なる\( \displaystyle n \)個のものから\( \displaystyle r \)個を選ぶ(\( \displaystyle {}_{n}\mathrm{C}_{r} \)通り)」は，「異なる\( \displaystyle n \)個のものから\( \displaystyle r \)個を選んで並べる(\( \displaystyle {}_{n}\mathrm{P}_{r} \)通り)」のあとに，順番の区別をなくす(\( \displaystyle r! \)で割る)ことで得られる．

(例\( \displaystyle 1 \))「男子\( \displaystyle 6 \)人，女子\( \displaystyle 4 \)人の中から\( \displaystyle 4 \)人の代表を選ぶ．少なくとも\( \displaystyle 1 \)人の女子を含むように選ぶ方法は何通りあるか．」という問いに対して，次の回答は誤りである．誤りを指摘し，正しい回答を示せ．

【回答(誤り)】
女子を1人選び，残りの9人から3人を選ぶ方法を考えて，
\( \displaystyle {}_{4}\mathrm{C}_{1}\times {}_{9}\mathrm{C}_{3}=4\times \frac{9\cdot 8\cdot 7}{3\cdot 2\cdot 1}=336 \)通り

説明例(クリックして下さい)

(解)数え方に重複が発生しているため，誤りである．
男1，…男6，女1，…，女4と名前をつけたとき，上の回答では，例えば
\( \displaystyle \begin{cases} \text{①女1を選んで，残り9人から男1，男2，女2を選ぶ} \\ \text{②女2を選んで，残り9人から男1，男2，女1を選ぶ} \end{cases} \)
は，別々のものとして数え上げられていることになるが，実際には同じ選び方である．

【正しい回答例①】(直接求める方法)
「少なくとも1人の女子を含むように選ぶ」場合の数は，
「女子１人と男子３人を選ぶ」
「女子２人と男子２人を選ぶ」
「女子３人と男子１人を選ぶ」
「女子４人を選ぶ」
のそれぞれの場合の数の和であるから，
\( \displaystyle {}_{4}\mathrm{C}_{1}\cdot {}_{6}\mathrm{C}_{3}+{}_{4}\mathrm{C}_{2}\cdot {}_{6}\mathrm{C}_{2}+{}_{4}\mathrm{C}_{3}\cdot {}_{6}\mathrm{C}_{1} \)
\( \displaystyle \ \ \ \ \ =4\cdot 20+6\cdot 15+24+1=195 \) 通り (答)

【正しい回答例②】(総数から不適なものを除外する方法)
「少なくとも1人の女子を含むように選ぶ」場合の数は，すべての選び方の場合の数から，「全員男子を選ぶ」場合の数を引けば良い．
10人から4人を選ぶ方法は，
\( \displaystyle {}_{10}\mathrm{C}_{4}=\frac{10\cdot 9\cdot 8\cdot 7}{4\cdot 3\cdot 2\cdot 1}=210 \) 通り
このうち，選ばれた4人が全員男子であるのは，
\( \displaystyle {}_{6}\mathrm{C}_{4}={}_{6}\mathrm{C}_{2}=\frac{6\cdot 5}{2\cdot 1}=15 \)通り
よって，求める場合の数は，
\( \displaystyle 210-15=195 \) 通り (答)

※ 上の問題文で紹介されている誤答のように，順序を考慮しない「組」を数え上げる問題において，「まず1人を選び，次に残りのメンバーを選ぶ」というような段階的に選ぶ考えは，重複（ダブルカウント）が発生しやすいため，特に注意が必要．なお，この問題が「1名の女子を班長，3名を班員とする」というように，選ぶ段階（第1ステップ，第2ステップ）に明確な役割の違い（区別）がある場合は，上の問題文で誤答としているものが，正しい回答となる．

(例2)8人の生徒を次のように分ける方法が何通りあるか求める．
(1) ４人，2人，2人に分ける
(2) 3組に分ける

説明例(クリックして下さい)

(1)4人組，2人組A，2人組Bに分ける方法は，
\( \displaystyle\ \ {}_{8}\mathrm{C}_{4}\times {}_{4}\mathrm{C}_{2}=\frac{8\cdot 7\cdot 6\cdot 5}{4\cdot 3\cdot 2\cdot 1}\times \frac{4\cdot 3}{2\cdot 1}=70\cdot 6 \) (通り)
求める場合の数は，2人組A，Bの区別をなくして，
\( \displaystyle \frac{70\cdot 6}{2!}=210 \) (通り) (答)
(2)8人をX，Y，Zの3組に分ける方法を考える．0人の組がいてもよいとすると，組の分け方は\( \displaystyle 3^{8} \)通りある．
このうち，0人の組が2つできるのは3通りある．また，0人の組が1つできるのは，
・0人の組の決め方はX，Y，Zの3通り
・2組への分け方は，0人の組がある場合を除いて\( \displaystyle 2^{8}-2 \)通り
であるから，\( \displaystyle 3\cdot (2^{8}-2) \)通りある．
よって，X，Y，Zの3組に分ける方法は，
\( \displaystyle \ \ 3^{8}-3-3\cdot (2^{8}-2)=3^{8}-3\cdot 2^{8}+3 \)通り
求める場合の数は，X，Y，Zの区別をなくして，
\( \displaystyle \ \ \frac{3^{8}-3\cdot 2^{8}+3}{3!}=\frac{3^{7}-2^{8}+1}{2} \)
\( \displaystyle \ \ \ \ \ =\frac{1932}{2}=966 \) (通り)（答）

※(2)は，(6,1,1),(5,2,1),(4,3,1),(4,2,2),(3,3,2)と分ける場合の数の和としても計算できる．
(6,1,1)…\( \displaystyle \frac{{}_{8}\mathrm{C}_{6}\times {}_{2}\mathrm{C}_{1}}{2!}=28 \)
(5,2,1)…\( \displaystyle {}_{8}\mathrm{C}_{5}\times {}_{3}\mathrm{C}_{2}=168 \)
(4,3,1)…\( \displaystyle {}_{8}\mathrm{C}_{4}\times {}_{4}\mathrm{C}_{3}=280 \)
(4,2,2)…\( \displaystyle \frac{{}_{8}\mathrm{C}_{4}\times {}_{4}\mathrm{C}_{2}}{2!}=210 \)
(3,3,2)…\( \displaystyle \frac{{}_{8}\mathrm{C}_{3}\times {}_{5}\mathrm{C}_{3}}{2!}=280 \)
※「\( \displaystyle n \)個の異なるものを\( \displaystyle k \)つの組(1組1個以上)」に分ける場合の数は，第２種スターリング数\( \displaystyle S(n,k) \)とよばれている．上の例により，\( \displaystyle S(8,3)=966 \)である．

○同じものを含む順列

\( \displaystyle p \) 個の A，\( \displaystyle q \) 個の B，\( \displaystyle r \) 個の C，\( \displaystyle \cdots \)を一列に並べる方法は，\( \displaystyle \frac{(p+q+r+\cdots)!}{p!q!r!\cdots} \) 通り
※場合の数を数えるとき，通常，人は区別して考える．同じ文字や，区別のつかないものについて上の式で計算する．

(例1)下図のような道路を通って，点Pから点Qまで移動する最短経路のうち，Rを通らない経路は何通りか．

説明例(クリックして下さい)

５個の「→」と３個の「↑」を並べて，その順に移動すると考えると，最短経路はこの順列に対応するから，PからQまでの最短経路は，
\( \displaystyle \frac{8!}{5!3!}=8\cdot 7=56 \) 通り
このうち，点Rを通るものを除いて，
\( \displaystyle 56-\frac{5!}{3!2!}\times 1\times \frac{2!}{1!1!}=36 \) 通り (答)

※特定の交差点Xに注目したとき，交差点Xの左側，下側に位置する交差点までの最短経路の総数がそれぞれ\( \displaystyle m,n \) 通りのとき，交差点Xまでの最短経路は\( \displaystyle m+n \)になる．これを利用して，最短経路の総数を直接調べることもできる．

(例2)次の組数を求める．
(1)\( \displaystyle x+y+z=8 \)を満たす0以上の整数の組\( \displaystyle (x,y,z) \)
(2)\( \displaystyle x+y+z=8 \)を満たす1以上の整数(自然数)の組\( \displaystyle (x,y,z) \)
(3)\( \displaystyle x+y+z\le 8 \)を満たす0以上の整数の組\( \displaystyle (x,y,z) \)

説明例(クリックして下さい)

※((2)の別解) \( \displaystyle (x-1)+(y-1)+(z-1)=5 \)であるから，\( \displaystyle X+Y+Z=5 \)を満たす0以上の整数の組を考えればよく，5個の「〇」と2個の「｜」の順列の総数を考えて，\( \displaystyle \frac{7!}{5!2!}=21 \)組

○円順列・数珠順列

(1) 回転して一致する並べ方は同じと考えて，いくつかのものを円形に並べたものを円順列という．
(2)異なる\( \displaystyle n \)個のものを並べる円順列の総数は，\( \displaystyle (n-1)! \)通り．
(3) 回転または裏返して一致する並べ方は同じと考えて，いくつかのものを円形に並べたものを数珠順列という．
(4) \( \displaystyle n \) を 3以上の自然数とする．異なる\( \displaystyle n \)個のものからできる数珠順列の総数は \( \displaystyle \frac{(n-1)!}{2} \) 通り．

(例，宮城県)立方体の6つの面にそれぞれ1，2，3，4，5，6の数字を1つずつ書き入れるとき，何通りの書き入れ方があるか求める．ただし，数字を書く向きは区別しない．

説明例(クリックして下さい)

数字の「1」を書き入れる面を1つ固定し，その面が常に上面にくるように立方体の向きを定める．数字を書く向きは区別しないため，この固定の仕方は1通りである．
次に，この「1」の面と向かい合う面（底面）に書き入れる数字を，残りの5つの数字（2，3，4，5，6）から選ぶ．この選び方は5通りである．

最後に，残った4つの数字を，側面の4つの面に書き入れる．側面を真上から見ると円状に並んでいるため，回転して一致するものを区別しない円順列となる．異なる4つの数字を円形に並べる方法は，
\( \displaystyle (4-1)!=3!=3\cdot 2\cdot 1=6 \) 通り
以上により，求める書き入れ方の総数は，
\( \displaystyle 5\cdot 6=30 \)通り (答)

この記事は役に立ちましたか？

間違い/不具合かな？
と思ったらこちらへ