【知恵袋から】場合の数

§1. １列に並べる

§2. 選ぶ

§3. 円形に並べる

§4. 最短経路の数

§5. 倍数・約数

§6. 乱列

「YAHOO! 知恵袋」で筆者が回答したものの中から抜粋しました。

§1. １列に並べる

【問題1.1】 区別のつかない5個の玉を3つの箱ABCにわけます。
(1) どの箱にも少なくとも1個の玉が入るような玉の入れ方は何通りか？
(2) 空の箱があって良いとき、玉の入れ方は何通りか？

【解】 (1) 初めに1個ずつ、各箱に入れておきます。残りは2個。
　　　○｜○｜
のように並べればいいです。｜は仕切り板で、○が玉です。
　　　$\frac{4!}{2!2!} = 6 $通り ……(答)

(2) 今度は
　　　○○○｜○○｜
のように並べればいいです。
　　　$\frac{7!}{5!2!} = 21$ 通り ……(答)■

【問題1.2】 i n t e r n e t のすべての文字を使ってできる順列は5040通り。ではどの t も、どの e より左にあるものは何通りか？---

【解】 $8!/(2!2!2!1!1!) = 5040$
に対して、tとeを同じ文字として並べて
　　　$8!/(4!2!1!1!) = 840$
その後、左2個はｔ、右2個はeと解釈すればよい。
【答】 $840$通り

【問題1.3】 男子4人と女子4人が横一列に並ぶとき男女が交互に並ぶ順列の数はいくつになりますか？---

【解】
(ア)　●○●○●○●○のタイプ
黒丸に男を入れる方法が4!
その各々に対し、女が4!
だから、4!×4!
（イ）　○●○●○●○●のタイプ
上と同様に4!×4!
【答】 4×!4!×2 = 1152通り

【問題1.4】 5個の文字、a,a,b,b,cから３つ選んで1列に並べる方法は何通りあるか？---

【解】
(ア)○○×型
　　　aab, aac, bba, bbc
の4型のそれぞれに対し、3!/(2!1!) = 3 通りだから
　　　4 × 3 = 12
(イ)○×△型
　　　abc の並べ方
だから
　　　3!=6通り
(ア)+(イ)=18通り ……(答)
【蛇足】 樹形図を使っていては数え間違いが多いので、やめておきましょう。

【問題1.5】 男性M1、…、M4の4人と女性F1、…、F4の4人が、横1列に並んだ座席S1、…、S8に座る場合を考える。
(1) 同性どうしが隣り合わない座り方の中で、M1の両隣がF1とF2になる座り方は何通りあるか。
(2) 同性どうしが隣り合わない座り方の中で、Ｍ1とF1が隣り合わない座り方は何通りあるか---

【解】 大きく分けて
　　　ＭＦＭＦＭＦＭＦ
か
　　　ＦＭＦＭＦＭＦＭ
の2つの場合有り。……(*)
(1) Ｆ1Ｍ1Ｆ2の3人を一人の女とみなす。
女3人、男3人の互い違いだから
　　　$(3! 3!)×2 = 72$
この他、Ｆ2Ｍ1Ｆ1の3人を一人の女とみなす方法があるので、2倍する。
　　　$72 ×2= 144$ 通り ……(答)
(2)ア：Ｍ1が端に行った場合。
　　　Ｍ1×○×○×○×
Ｆ1は3ヵ所しか行き場がない。
　　　$3×(3! 3!) = 108$
Ｍ1は左端と右端があるから2倍する。
　　　$108 × 2 = 216$
イ：Ｍ1が端以外に行った場合。
　　　×Ｍ1×○×○×○
Ｆ1は2ヵ所しか行き場がない。
　　　$2×(3! 3!) = 72$
Ｍ1の行き場所は3ヵ所ある。
　　　$72 × 3 = 216$
でも、そもそも(*)に注意すれば、これの2倍だ。
　　　$216 × 2 = 432$
アとイを合わせて
　　　$216 + 432 = 648$ 通り ……(答)

【問題1.6】 将棋名人戦において、７番勝負の星のパターンは何通りあるでしょうか。 どちらかが４勝したら、終わりになります。
単なる順列・組み合わせより難しい。 ４連勝 ◯◯◯◯ １通り。 ４勝１敗 ●◯◯◯◯ など。（●が◯の間に入る）４通り。 ４勝２敗、これが一番多い。 ４勝３敗自体は実際に何回かあったが、●●●◯◯◯◯ これは将棋で１回あっただけ。 ４勝２敗と４勝３敗の場合の数を求めてください。---

【解】 プロ野球の日本シリーズと同じですね。

(1)４連勝 ◯◯◯◯ １通り。
(2)４勝１敗 ●◯◯◯|◯ など。
　最後の○は無視、｜の左に○3個と●1個を並べる。4カ所のうち1カ所に●を置く方法は$_{4}Ｃ_{1} = 4$ 通り。
(3)４勝２敗 ●◯◯●◯|◯ など。
　最後の○は無視、｜の左に○3個と●2個を並べる。5カ所のうち2カ所に●を置く方法は$_{5}Ｃ_{2} = 10$ 通り。
(4)４勝３敗 ●●●◯◯◯｜◯ など。
　最後の○は無視、｜の左に○3個と●3個を並べる。6カ所のうち3カ所に●を置く方法は$_{6}Ｃ_{3} = 20$ 通り。

(1)〜(4)を合計すれば ７番勝負の星のパターンのうち、一方が勝つ場合が
　　　 $1 + 4 + 10 + 20 = 35$
通りあると分かります。 この35通りという数字は次のように簡単に出ます。
　　　◯◯●◯◯●●
のように、○4個と●3個を並べる。7カ所のうち3カ所に●を置く方法だから $_{7}Ｃ_{3} = 35$ 通り。
(上の例で言うと5戦目で4勝したからホントは終わりなのですが、無理矢理勝負を続行させ、 残り2戦はわざと負けてやります。消化試合ですね。このように解釈して計算すると全部で 35通りがすぐ出ます。)

§2. 選ぶ

【問題2.1】 平面上の10本の直線が、どの2本も平行でなく、どの3本も1点で交わらないとき、交点は何個あるか。また、三角形は何個できるか。---

【解】 「どの2本も…、どの3本も…」というのは、たとえば超極端の場合＝全部平行だったり、全部が1点で交わったり、というようなことがないということです。これでは一つも三角形ができませんよね。
そういう例外的なことはないよ、ということで、数学ではこういうのを「一般の位置にある」と言うことがあります。
では、解答。前半は
　　　${}_{10}C_{2} =45$個 ……(答)
後半は
　　　${}_{10}C_{3} =120$個 ……(答)

【問題2.2】 男子2人、女子5人、計7人の生徒がいる。この中から委員3人を選ぶ方法は、全部で□通りあり、このうち少なくとも1人は男子である選び方は、全部で□通りある。---

【解】 「少なくとも1人は男子」の余事象は「全員女子」だから
　　　$_{7}C_{3}- _{5}C_{3} = 35-10=25$ 通り■
【別解】 男をA君とB君とします。男子から1人A君を選んでおいて、残りの男子1人と女子5人から2人選べば、$_{6}C_{2}=15$
この中にはA君と、（B君＆＊子ちゃん）が選ばれることがあることに注意します。
一方、男子から1人B君を選んでおいて、残りの男子1人と女子5人から2人選べば、$_{6}C_{2}=15$
この中にはB君と、（A君＆＊子ちゃん）が選ばれることがあることに注意します。
この2回のカウントで、ダブルカウントが生じています。それは(A君＆B君＆＊子ちゃん)のの5通りです。
ダブルカウントを引けば正解にたどり着きます。すなわち
　　　$15 +15 - 5 = 25$ 通り■

【問題2.3】 （1）正七角形の異なる2本の対角線の組で、頂点以外の点を共有するものは何組あるか。
（2）正七角形の異なる2本の対角線の組で、共有点をもたないものは何組か。---

【解】 (1)頂点以外の点を共有するものは、$_{7}C_{4} = 35$組 ……(答)
　　　
なぜなら図から分かるように、4点(黒丸)を決めれば、対角線は自動的に決まるから。
(2) 共有点をもたないものは、
Aタイプ(対角線が平行)が7組、
Bタイプ(対角線が平行でない)が7組、
あって合わせて、$7 + 7 = 14$組……(答)
　　　
【蛇足】 頂点を共有する対角線の組がいくつあるか、考えてみよう。
　　　
交点の決め方が7通りあって、それぞれに対し2本の対角線のとり方が $_{4}C_{2}$通りあるから、
　　　$7 \times _{4}C_{2} = 42$組
これと(1), (2)の答を合算すると
　　　$35+14+42=91$
で、合計91組。対角線は$_{7}C_{2}-7=14$本あるから、$_{14}C_{2} = 91$ でつじつまが合う。

§3. 円形に並べる

【問題3.1】 白玉1個、赤玉4個、青玉6個で環状の首飾りを作るとき、どの2個の赤玉も隣り合わないことにすると作り方は何通りあるか。---

【解】 白玉1個と青玉6個で首飾りを作っておきます。
　　　
玉と玉の隙間が7ヵ所あり、そのうちの4ヵ所に赤玉を挿入します。その方法は
　　　${}_{7}C_{4}=35$通り
あります。ここで、左右対称だと裏返して同じなので、2つに場合分けします。
(ア)左右対称の場合
　　　${}_{3}C_{2}=3$通り
(イ)左右対称でない場合
　　　$35-3=32$通り
というのは、首飾りでなく円卓の場合。首飾りでは(ダブルカウントしてしまっているので) 2で割って
　　　$32 \div 2= 16$通り
(ア)+(イ)より
　　　$3+16=19$通り ……(答)

【問題3.2】 立方体の各面に、隣り合った面の色は異なるように、色を塗りたい。ただし、立方体を回転させて一致する塗り方は同じとみなす。---
(1) 異なる6色をすべて使って塗る方法は何通りあるか。
(2) 異なる4色をすべて使って塗る方法は何通りあるか。

【解】(1) 立方体の天板に塗る色を(例えば赤色と)固定します。対面の床面に塗る色(下図では青色)を決める方法が $5$ 通りある。
　　　
その方法のそれぞれについて、残りの側面( $4$ 色)を決める方法が円順列で $(4-1)!$ 通り。よって
　　　$5 \times (4-1)! =30$ 通り ……(答)
(2) 側面4面を初めに決めます。このとき
(ア) 4色を使うと、全部で5〜6色使う羽目になる。
(イ) 側面で3色を使うと、天板と床板は同じ色の第4色で塗ることになる。4側面を3色で塗る方法は $ABAC$(1組の対面が同色で、他の1組の対面が異色)であるから、下図のようになる。　
　　　
(ウ) 側面で2色を使う方法は$ABAB$ (2組の対面が同色）だから、天板と床板は異なる色の第3色、第4色を使って塗ることになる。
結局、(イ) と (ウ) は同じ方法である。(イ)＝(ウ)の方法は何通りあるかと言うと、2組の対面に同色を塗る方法が ${}_{4}C_{2}=6$ 通りで、残りの2色を塗る方法は2通りあるような気がするが、塗った立方体を逆さにしても同じ(円順列と考えてもよい)だから、実は $!$ 通りしかない。よって
　　　${}_{4}C_{2} \times (2-1)!=6$ 通り ……(答)

§4. 最短経路の数

【問題4.1】 下の図の点PからQまで最短距離で行く道順は何通りあるか。---
　　　

【解】和の法則を使います。
　　　
ある交差点(例えば6)にたどり着く方法は、その一つ下の(2)と左の(4)を足して
　　　2+4=6
でいいのです。なぜなら、下の交差点まで2通りの方法、左の交差点まで4通りの方法で、6の交差点には6通りの方法があると分かります。
【答】 43通り。

【問題4.2】 下図のような街路がある。 AからBまで行く経路のうち、右(東)および上(北)移動以外に左(西)の移動が１区画分含まれている。ただし同じ点を二度通ってはいけない。この場合の道数は何通りか。---
　　　

【解】 赤線で示された例を書き下すと
　　　東北東東北西北北東北東
となる。これを見て気づくのは「同じ点を二度通ってはいけない」といことから
　　　北西北
のように、西はその両隣を北でブロックしなければならない、といことだ。
あとは、
　　　「北西北」「東」「東」「東」「東」「東」「北」「北」「北」
の同じものを含む 9枚のカードの順列かと思いきや、少し違う。問題の図のように A より西、B より東には路がないから
　　　「北西北」
のカードは、先頭(左端)と終末(右端)に持ってこれないのみならず、より正確に言えば、「北西北」のカードの左にも右にも「東」のカードを少なくとも 1枚置かねばならない。
したがって
（ア） (1)「北」(2)「北」(3)「北」(4)「北西北」(5)
において、(1)(2)(3)(4)(5)の5箇所に「東」を重複を許して5個入れるのだが「北西北」の左右に「東」を必ず置くから、重複組合せ $_{n}H_{r}$ を使って
　　　$_{5}H_{5}-_{4}H_{5}-_{1}H_{5}=_{9}C_{5}-_{8}C_{5}-_{5}C_{5}=126-56-1=69(通り)$
（イ） (1)「北」(2)「北」(3)「北西北」(4)「北」(5)
において、(1)(2)(3)(4)(5)の5箇所に「東」を重複を許して5個入れるのだが「北西北」の左右に「東」を必ず置くから、
　　　$_{5}H_{5}-_{3}H_{5}-_{2}H_{5}=_{9}C_{5}-_{7}C_{5}-_{6}C_{5}=126-21-6=99(通り)$
（ア）と（イ）の場合を合わせれば
　　　$69+99=168(通り)$
だが、これ以外にこれらを左右反転させた順列があるから、2倍して
　　　$168 \times 2 =336(通り)$ ……(答)

§5. 倍数・約数

【問題5.1】 200?500までの整数のうち、9で割り切れる数は何個あるか。---

【解】 九去法というのがあります。各位の数を足して9で割り切れれば、元の数も9で割り切れるのです。
200?500までの整数のうち、9で割り切れる数の最小は
　　　2+0+7 =9 で 207 = 9×23
最大は
　　　4+9+5 = 18で 495 = 9×55
それで、
　　　55-23+1=33 個 ……(答)
です。植木算で '+1' です。

§6. 乱列

【問題6.1】 5人の客がホテルのフロントにそれぞれコートを預け、帰りに、2人だけがそれぞれ自分のコートを受け取り3人がそれぞれ自分と異なるコートを渡される場合の数は何通りか？また、すべての5人がそれぞれ自分のコートと異なるコートを渡される場合の数は何通りか？---

【解】 $n$人すべてがそれぞれ自分のコートと異なるコートを渡される場合の数を$D(n)$通りとする。
　　　$D(1) = 0$
　　　$D(2) = 1$
　　　$D(3) = 2$
　　　$D(4) = 9$
ここまでは、地道に考えてできる。このあとは漸化式を作らないと無理だろう。
　　　
上の図から、次の漸化式が出てくる。
　　　$D(n) = (n-1) \{ D(n-1) + D(n-2)\}$
したがって、$D(5) = 44$通りが後半の答。
前半の答は
　　　 $_{5}C_{3} \times D(3) = 20$通り。
詳しくは「モンモール数」で検索してください。本HPでは『乱列またはモンモールの問題』で解説してます。歴史上有名な問題です。