2019.11.14 1-4 数学 B 第７章 場合の数と数列 §1 場合の数 章末問題 【授業目標】 これまでの復習をしながら、なるべく多くの問題を解いてみる。 理解があいまいだったところを洗いだし、その部分の理解を深める。 【本日の宿題】 章末問題 1A, 1B、問題集 464～470、472～474 ※ 問題の題意から、どのような順列や組合せ、または、円順列、重複順列、同じものをつかった順列など、 どのように式を立てるのかを思いつくまでに時間を取られてしまう場合がある。 とはいえ無限にパターンがあるわけではないから、いくつか問題を解く中でパターンを知っておくとよい。 練習問題 1A 1 まず、問題文の情報を図示して整理すること。（→ 右図） 便宜的に右図のように経路（道）に番号を振る。 A → B → C → B → A という順に通る 4 段階で、順列と同様にそれぞれ選べる経路数を数える。 A → B ： ①から⑤の 5 通り B → C ： ⑥から⑨の 4 通り C → B ： すでに通った経路を除く 3 通り B → A ： すでに通った経路を除く 4 通り この選べる経路の数は、どの経路を通るかに依らない。 すなわち、独立事象として扱い、積の法則が成り立つ。 従って、5×4×3×4 = 240 通りの経路があり得る。 2 大小 2 個のサイコロの目の和が 5 の倍数（5, 10）となるのは、2 つの目の「組合せ」が 1 と 4, 2 と 3, 4 と 6、（4 と 1 は数え済み）、5 と 5 の 4 通りである。 ・ 大小の順に 2 個のサイコロの目がつくる「順列」の総数は、6^2 = 36 通りある。 このうち、 ・ 組合せが１と 4 になる順列の数は、具体的には 1,4 と 4,1 の2P2 = 2 通り。 「同じものを用いた順列」と同じ考え方で計算し2C1×1C1 = 2 通りとしてもよい。 ・ 組合せが 2 と 3 になる順列の数は、同様に 2 通り。 ・ 組合せが 4 と 6 になる順列の数は、同様に 2 通り。 ・ 組合せが 5 と 5 になる順列の数は、5, 5 の 1 通りのみ。 ← このように順列の数で数える必要あり 従って、求めるのは目の出方の順列の数として 7 通り。 （確率は、7/36 となる） 3 「4 桁の整数」には、1000 の位が 0 であるものを含まないという前提で解く。 (1) まず 1000 の桁が他の桁とは異なる制約をもつので、一番はじめに考える。 1000 の桁で使える数字は、7 通り。 100 の桁で使える数字は、残り 6 通りと、0 の 7 つ。7 通り。 10 の桁で使える数字は、残りの 6 通り。 1 の桁で使える数字は、5 通り。 以上の場合の数は、共通で場合分けしなくて良い。つまり独立事象として扱え、積の法則を適用する。 従って、7×7P3 = 7×7×6×5 = 1470 通り。 (2) 1000 の桁で使える数字は、7 通り。 100 の桁から 1 の桁で使える数字は、8 通り（重複を許される）。 従って、7×83 = 3584 通り。 A B C ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨
4 (n+1)! = (n+1)×n! などの関係式を用いる。 (1) n! / (n+1)! = n! / {(n+1)×n!} = 1/(n+1) (2) (n+1)! / (n-1)! = (n+1)×n×(n-1)! / (n-1)! = (n+1)×n (3) (n-r+1)! / (n-r-1)! = (n-r+1)×(n-r)×(n-r-1)! / (n-r-1)! = (n-r+1)×(n-r) 5 「色の異なる 8 個のボール」→ ボールはすべてそれぞれ区別せよ 「大きさの異なる 3 つの箱」→ 箱も区別せよ つまり、① ～ ⑧のボールを、箱 A, B, C に振り分ける方法を数える。 最後まで空のままの箱があっても良いので、①から⑧の順に 3 つの箱を割り振っていくと、 AAAAAAAA, AAAAAAAB, など 8 桁の順列ができる。 この総数は、重複順列として数えることができ、38 = 6561 通り。 → 箱の中のボールの数で場合分けをして数えておく。 この場合は、個々の場合について、「同じものを含む順列」として考える必要がある。 ・ 2 つの箱が空の場合 まず、空の箱 2 つ、入っている箱 1 つを選ぶので箱の組合せとして 3C2×1C1 = 3 通り。 具体的には、AAAAAAAA, BBBBBBBB, CCCCCCCC の入り方の 3 通り。 ・ 1 つの箱が空の場合 空の箱 1 つ、入っている箱 2 つを選ぶので、箱の組合せとして 3C1×2C2 = 3 通りある。 具体的には、玉の入っている箱が A,B の場合、A,C の場合、および B,C の場合。 とりあえず、この 2 つの箱を x, y とするならば、この 3 通りの組合せそれぞれについて xxxxyyyy など、重複順列を考える。ただし、xxxxxxxx と yyyyyyyy は除外する。 従って、3×(28 - 2) = 762 通り。 ・ 空の箱が無い場合、箱の中の個数の組合せは、116, 125, 134, 224, 233 の 5 通り。 116 である場合、箱の組合せとしては 1 個入る箱が 2 つなので3C2×1C1 = 3 通り。 それぞれについて、 8C1×7C1×6C6 通りの玉の入れ方があるので、3×8C1×7C1×6C6 = 168 通り 125 である場合、箱の組合せとしては、3C1×2C1×1C1 = 3P3 = 6 通り。 それぞれについて、 8C1×7C2×5C5 通りの玉の入れ方があるので、6×8C1×7C2×5C5 = 1008 通り 134 である場合、箱の組合せとしては、3C1×2C1×1C1 = 3P3 = 6 通り。 それぞれについて、 8C1×7C3×4C4 通りの玉の入れ方があるので、6×8C1×7C3×4C4 = 1680 通り 224 である場合、箱の組合せとしては、3C2×1C1 = 3 通り。 それぞれについて、 8C2×6C2×4C4 通りの玉の入れ方があるので、3×8C2×6C2×4C4 = 1260 通り 233 である場合、箱の組合せとしては、3C1×2C2 = 3 通り。 それぞれについて、 8C2×6C3×3C3 通りの玉の入れ方があるので、3×8C2×6C3×3C3 = 1680 通り ・ 検算として、6561 = 3 + 762 + 168 + 1008 + 1680 + 1260 + 1680 を確認することができる。 6 平行四辺形は、縦および横のそれぞれについて 2 本の平行線 1 組ずつを指定する。 縦の 2 本の平行線の組合せは、6C2 通りあり、 横の 2 本の平行線の組合せは、7C2 通りある。 この組合せがともに同じでなければ別の平行四辺形ができるので、できる平行四辺形の数は、 6C2×7C2 = 15×21 = 315 通り。 別解。線ではなくエリアについて注目して数えてもよい。 列（縦のならび）の選び方として、6 本の線により区切られているので、5 エリアある。 ここから連続した（飛び地のない）エリアの選び方としては、 1 エリアのみを用いる 5 通り 2 エリアを用いる 4 通り（つまり、12, 23, 34, 45） 3 エリアを用いる 3 通り ： 5 エリアとも用いる 1 通り の合計で、5 + 4 + … + 2 + 1 = 15 通り。（これは実は、6C2 に等しい△） 同様に、行（横の並び）の選び方として、7 本の線により区切られているので、6 エリアあり、 ここから連続した（飛び地のない）エリアの選び方としては、6 + 5 + … + 2 + 1 = 21 通り。 従って、15×21 = 315 通り。
→ 比較して気づいた方も多いと思うが、1 + 2 + … + (n-1) + n = (n+1)×n/2 = n+1C2 である△。 説明 Sn = 1 + 2 + … + (n-1) + n （Sn は、1 から n までの和）と置く。 2Sn = {n + (n-1) + … + 2 + 1} + {1 + 2 + … + (n-1) + n} = (n + 1) + (n-1 + 2) + … + (2 + n-1) + (1 + n) = (n+1)×n └─ (n+1) となる項が、n 個並んだ和 ─┘ ∴ Sn = 1 + 2 + … + (n-1) + n = (n+1)×n / 2 △ この公式の帰納法による証明 ・ n = 1 のとき、S1 = 1, n+1C2 = 2C2 = 1 なので、Sn = n+1C2 が成立する。 ・ Sk = k+1C2 を仮定すると、Sk+1 = k+2C2 が成り立つことを示せばよい。 一般に、k+2C2 = (k+2)×(k+1)/2 また、k+1C2 = (k+1)×(k)/2 であるから、 k+2C2 - k+1C2 = (k2 + 3k + 2)/2 - (k2 + k)/2 = (2k + 2)/2 = k + 1 である。 一方、S の定義より Sk+1 = Sk + (k + 1) なので、 Sk+1 = Sk + (k+2C2 - k+1C2) である。 ここで Sk = k+1C2 の仮定を用いると、Sk+1 = k+1C2 + (k+2C2 - k+1C2) = k+2C2 が成立する。 7 同じものを用いる順列として、以下のように場合わけして考える。 1 が 3 回用いられるので、残りの 3 つの桁には、2 と 3 が入る。 それぞれの数字が、6 つの位置のどこに入るのかの組合せとして数えるので 1 が 3 回、2 が 3 回、3 が 0 回の場合は、6C3×3C3×0C0 = 20×1×1 = 20 通り 1 が 3 回、2 が 2 回、3 が 1 回の場合は、6C3×3C2×1C1 = 20×3×1 = 60 通り 1 が 3 回、2 が 1 回、3 が 2 回の場合は、6C3×3C1×2C2 = 20×3×1 = 60 通り 1 が 3 回、2 が 0 回、3 が 3 回の場合は、6C3×3C0×3C3 = 20×1×1 = 20 通り 従って、20 + 60 + 60 + 20 = 160 通り 8 同じものを用いる順列として数える。 (1) 3 が 3 回、4 が 2 回、5 が 1 回なので、6C3×3C2×1C1 = 20×3×1 = 60 通り (2) 偶数になるためには、末尾の数字は、4 しか選択肢がない。 残りの 5 桁を、3 が 3 回、4 が 1 回、5 が 1 回で埋めるので、5C3×2C1×1C1 = 10×2×1 = 20 通り 9 与式を展開したときの一般項のうち (1) x4 の次数をもつものは、 6C5×1C1･(2x)5･(-1/x)1 なので、その係数は、6×1×25×(-1)1 = -192 (2) 1/x2 の次数をもつものは、 6C2×4C4･(2x)2･(-1/x)4 なので、その係数は、15×1×22×(-1)4 = 60 (3) x0 の次数をもつものは、 6C3×3C3･(2x)3･(-1/x)3 なので、定数項は、20×1×23×(-1)3 = -160 練習問題 1B 1 個人ごとに区別するものとして問題を解く。 (1) 8 人が円形に並ぶので、円順列として計算し、8!/8 = 7! = 5040 通り。 (2) 「女子 3 人が隣り合う」は、女子 3 人の間に男子が入り込まないという意味に解釈する。 女子代表 1 名と男子 5 名で円順列を作ると、6!/6 = 5! = 120 通りがあり、 そのそれぞれについて、女子代表を女子 3 人の並びに置き換えるのは 3P3 = 6 通りある。 6!/6 × 3P3 = 120×6 = 720 通り。 (3) まず、男子 5 人で円順列を作る。5!/5 = 4! = 24 通りとなる。 女子は、それぞれ別の男子を指名して、その右隣に入ることにする。その選び方は、5P3 = 60 通り。 5!/5 × 5P3 = 24×60 = 1440 通り。 2 【新しい考え方】 最短のルートとは、右と下以外へは進まない（上や左へは戻らない）ものである。 交差点ごとに、右へいったら→、下へ行ったら↓と、移動経路のログを付けるものと考えるとよい。 なお、全に東西南北に走っていて、すべての区画は長方形であると近似できるものとし、 また、道巾は無視できるため、どの経路を通っても上や左に戻らない限り、経路長が一定と考える。 ※ 細かいことを言いだすと、球面上にあるため、右へいく（同じ経度分を移動するために必要な）経路 は高緯度ほど（わずかに）短くなるが、そういう類のクイズではないので、無視する。
(1) A から B まで移動するとき、右へ 4 回、下へ 3 回移動するという条件は、どの経路を通っても同じ。 そのため右(→)を 4 回、下(↓)を 3 回使ってできる「同じものを含む順列」の総数を求めればよい。 →→→→↓↓↓, →→→↓→↓↓, →→→↓↓→↓, →→→↓↓↓→, … の順列の数を数えていく。 7 つの桁の位置に、4 つの R を選び、残りに 3 つの D を選ぶので、7C4×3C3 = 35 通り。 ※ 7C4 = 7!/(4!･3!) である。 ※ 二項定理に関連して、パスカルの三角形（左は数字、右はnCr で書いたもの）を再掲しておく。 1 0C0 1 1 1C0 1C1 1 2 1 2C0 2C1 2C2 1 3 3 1 3C0 3C1 3C2 3C3 1 4 6 4 1 4C0 4C1 4C2 4C3 4C4 1 5 10 10 5 1 5C0 5C1 5C2 5C3 5C4 5C5 1 6 15 20 15 6 1 6C0 6C1 6C2 6C3 6C4 6C5 6C6 1 7 21 35 35 21 7 1 7C0 7C1 7C2 7C3 7C4 7C5 7C6 7C7 → 頂点の位置から最短でそれぞれの点にいたるまでの経路数になっていることがわかる。 → それぞれの頂点から進むことのできる経路は、右(→)と左(↓)の 2 択になっているので、 経路の数は、(→)と(↓)の 2 種類による「同じものを含む順列」二項係数として解くことができる。 → パスカルの三角形を書き上げていく操作との対応を考える。 ある地点に到達するための経路は、上の段の 2 つの地点に到達する経路数の和になる。 ある地点に到達するための前の地点が 1 つしかない場合は、前の地点の経路数をそのまま引き継ぐ。 (2) C を通る経路を考え、この余事象として全体から引き去る。 C を通る経路は、A → C で4C2×2C2 = 6 通りあり、C → B で3C2×1C1 = 3 通りなので、 これを同時に満たすのは、積の法則により 18 通り。 よって、35 - 18 = 17 通り。 ※ 類例に、特定の通路を通る経路数（その余事象として特定の通路を通らない経路数）の問題がある。 「C-D 間の特定の通路を通る」という条件では、 A → C の経路数と、C-D 間の特定の通路を通る経路数と、D → B の経路数の積で求めることができる。 3 正八角形の頂点 または、円周上に（等間隔でなくとも、適当な間隔でもよい）に並んだ 8 個の点 または、どの 3 点以上を選んでも一直線上にはないことが分かっている 8 個の点 から任意の 3 点を選んで結ぶと、必ず三角形ができる。 なお、合同であっても、別の点の組から作られた三角形は別の三角形と見做す。 (1) 8 個の頂点から任意の 3 つを選ぶときの組合せの総数である。8C3 = 56 個。 (2) 正八角形と 2 辺を共有する三角形において、正八角形と共有する 2 辺は連続している。 → 離れた 2 辺を共有する図形は、四角形以上になってしまうので。 → いくつか数え方の説明ができるが、一番シンプルなのは、正八角形と共有する連続した 2 辺に挟まれる 頂点で数えていく。この頂点の候補は、正八角形の頂点の数と一致するので、8 個。 → その他の説明として、たとえば、2 辺を共有する三角形は、正八角形の頂点に順に番号をつけたとき、 123, 234 など連続した番号を選んだものになる（ただし、8 と 1 は連続しているものとみなす。つま り、781 や 812 も連続した番号とみなす）。このような選び方は、3 つの連続した数字の一番小さいも のが 1 の場合から 8 の場合の 8 通りとなる。 (3) 正八角形と 1 辺のみを共有する三角形の構成要素を、その辺と、辺とは離れた位置の頂点として考える。 → 1 つの辺あたり、残りの頂点 6 つのうち隣接していない 4 つが候補となる。 辺 12 に対し、3 と 8 を除外した 4 から 7 の 4 通りとなる。すなわち、8×4 = 32 個 (4) 正八角形と辺を共有しないという条件から錯誤なく正しく数えるのは、案外面倒である。 正八角形と 3 辺を共有することはないので、「1 辺または 2 辺を共有する」の余事象として数える。 → 56 - 8 - 32 = 16 個 → 頂点に番号を付けたとき、135 のような二等辺三角形 8 個、136 のような二等辺三角形 8 個である。
4 「同じものを使った順列」である。ただし、7 桁の数として、一番左が 0 となるものは除外する。 (1) 一番左の桁の選択肢は、1, 2，3 である。ただし、そのどれを選ぶのかにより、それ以外の桁で使える 「同じもの」の個数が変わるため、場合わけして数える必要がある。 → 全体、つまり、左端が 0 から 3 のどれでもよいとすると、 1 個の 0, 3 個の 1, 2 個の 2, 1 個の 3 を並べる 7 桁の数字の並びは、 7C1×6C3×3C2×1C1 = 7!/(1!･3!･2!･1!) = 420 通り → このうち、0 で始まるのは、残り 6 桁に 3 個の 1, 2 個の 2, 1 個の 3 を並べるので、 6C3×3C2×1C1 = 6!(3!･2!･1!) = 60 通り → 一番左が 1 である場合、残り 6 桁に 1 個の 0, 2 個の 1, 2 個の 2, 1 個の 3 を並べるので、 6C1×5C2×3C2×1C1 = 6!/(1!･2!･2!･1!) = 180 通り。 → 一番左が 2 である場合、残り 6 桁に 1 個の 0, 3 個の 1, 1 個の 2, 1 個の 3 を並べるので、 6C1×5C3×2C1×1C1 = 6!/(1!･3!･1!･1!) = 120 通り。 → 一番左が 3 である場合、残り 6 桁に 1 個の 0, 3 個の 1, 2 個の 2 を並べるので、 6C1×5C3×2C2 = 6!/(1!･3!･2!) = 60 通り。 → 全体から左端が 0 の場合を引いて 420 - 60 = 360 通り。 または、左端が 1 から 3 の場合を合計して 180 + 120 + 60 = 360 通り。 (2) 偶数であるためには、右端が 0 または 2 でなければならない。 → 全体、つまり、左端が 0 から 3 のどれでもよいとすると、 右端が 0 のものは、6 桁に 3 個の 1, 2 個の 2, 1 個の 3 を並べるので、 6C3×3C2×1C1 = 6!(3!･2!･1!) = 60 通り 右端が 2 のものは、残り 6 桁に 1 個の 0, 3 個の 1, 1 個の 2, 1 個の 3 を並べるので、 6C1×5C3×2C1×1C1 = 6!/(1!･3!･1!･1!) = 120 通り。 → 左端が 0 で、右端が 2 のものは、残り 5 桁に 3 個の 1, 1 個の 2, 1 個の 3 を並べるので、 5C3×2C1×1C1 = 5!/(3!･1!･1!) = 20 通り。 → 左端が 1 で、 右端が 0 のものは、残り 5 桁に 2 個の 1, 2 個の 2, 1 個の 3 を並べるので、 5C2×3C2×1C1 = 5!/(2!･2!･1!) = 30 通り。 右端が 2 のものは、残り 5 桁に 1 個の 0, 2 個の 1, 1 個の 2, 1 個の 3 を並べるので、 5C1×4C2×2C1×1C1 = 5!/(1!･2!･1!･1!) = 60 通り。 → 左端が 2 で、 右端が 0 のものは、残り 5 桁に 3 個の 1, 1 個の 2, 1 個の 3 を並べるので、 5C3×2C1×1C1 = 5!/(3!･1!･1!) = 20 通り。 右端が 2 のものは、残り 5 桁に 1 個の 0, 3 個の 1, 1 個の 3 を並べるので、 5C1×4C3×1C1 = 5!/(1!･3!･1!) = 20 通り。 → 左端が 3 で、 右端が 0 のものは、残り 5 桁に 3 個の 1, 2 個の 2 を並べるので、 5C3×2C2 = 5!/(3!･2!) = 10 通り。 右端が 2 のものは、残り 5 桁に 1 個の 0, 3 個の 1, 1 個の 2 を並べるので、 5C1×4C3×1C1 = 5!/(1!･3!･1!) = 20 通り。 → 全体から左端が 0 の場合を引いて(60 + 120) - 20 = 160 通り。 または、左端が 1 から 3 の場合を合計して 30 + 60 + 20 + 20 + 10 + 20 = 160 通り。 ※ (1)、(2) ともに全体から左端が 0 の場合を引いて計算するのが最も計算量が少なくて済む。 5 (1+x)n に二項定理を適用すると、次式のように展開される。 (1+x)n = nC0･10･xn + nC1･11･xn-1 + nC2･12･xn-2 + … + nCn-2･1n-2･x2 + nCn-1･1n-1･x1 + nCn･1n･x0 この式に x = 1 を代入すると、1m = 1, xn = 1n = 1 なので式右辺は簡単になり、 左辺 = (1+x)n = 2n 右辺 = nC0 + nC1 + nC2 + … + nCn-2 + nCn-1 + nCn
6 (x2 + x + 1)5 を展開したときにでてくる次の次数の項の係数を求めよ。 >> 授業で配布したハンドアウト資料では、 >> 別の問題（(x+2)3 を展開したときに出てくる次の次数の…）の解説になってました。m(_ _)m >> このページは修正版です。 方針：多項定理の問題として解く。 与式を展開して出てくる項は、(x2)p･xq･1r = x2p+q である。ただし、p + q + r = 5 r が 0 を含む任意の数をとれるので、p + q ≦ 5 の範囲であればよい。 この条件を満たし、x の次数が同じになって係数に寄与する項が複数あることに注意する。 (x2)p の部分に着目し、p を 1 だけ下げると q が 2 上がる関係になっていることに注目して整理する。 すなわち p = 4 のとき、3 のとき、2 のとき、1 のとき、0 のときにそれぞれ残りの部分を書いてみる。 (1) x9 = (x2)4･x1 （9 次の項とするため(x2)3･x3 では p+q=6 となってしまい該当しない） (2) x7 = (x2)3･x1 + (x2)2･x3 （7 次の項とするため(x2)1･x5 では p+q=6 となってしまい該当しない） (3) x5 = (x2)2･x1 + (x2)1･x3 + x5 つまり、(a + b + c)5 ただし、a = x2, b = x, c = 1 において、 (1) a4b (2) a3bc + a2b3 (3) a2bc2 + ab3c + b5 の係数を求めればよい。 (1) 5C4 = 5 (2) 5C3･2C1 + 5C2 = 20 + 10 = 30 （20 a3bc + 10 a2b3） (3) 5C2･3C1 + 5C3･2C1 + 5C5 = 30 + 20 + 1 = 51 （30 a2bc2 + 20 ab3c + b5) （別解）教科書の解答にあるヒント 「x2 + x = x(x + 1) = X とおく」 (x2 + x + 1)5 = (X + 1)5 を実際に展開してみる。 二項定理から（パスカルの三角形を利用しても可） (x2 + x + 1)5 = (X + 1)5 = X5 + 5X4 + 10X3 + 10X2 + 5X + 1 = x5(x + 1)5 + 5･x4(x + 1)4 + 10･x3(x + 1)3 + 10･x2(x + 1)2 + 5･x(x + 1) + 1 ただし、 x5(x + 1)5 = x5･(x5 + 5x4 + 10x3 + 10x2 + 5x + 1) 5･x4(x + 1)4 = 5･x4･(x4 + 4x3 + 6x2 + 4x + 1) 10･x3(x + 1)3 = 10･x3･(x3 + 3x2 + 3x + 1) 10･x2(x + 1)2 = 10･x2･(x2 + 2x + 1) 5･x(x + 1) + 1 これらの中から、x9, x7, x5 の次数になる項を探し、係数の和を取る。
問題集 464 等式の証明には、以下のような方法をとることができる。 ・ 意味から考えて、同じになるはずの場合の数を表す式が 2 通りあり得ることを示す（p202 例題 5）。 ・ 公式を適用し、与式右辺、または左辺、またはその双方を式変形して、互いに等しいことを示す。 ・ 組合せの場合など、パスカルの三角形との関係から説明する。 (1) ・ nPr は、互いに重複のない n 個の要素から r 個を取り出して並べるときの順列の総数である。 もし、順列の先頭や末尾など、特定の位置を始めに指定する場合は、その位置に指定することができる 要素の数は n 個あり、そのそれぞれについて、残り n-1 個の要素から r-1 個を取り出して並べる。つ まり、この時の順列の総数は、n×n-1Pr-1 通りとなる。 始めに 1 か所を指定しようが指定しまいが出来上がる順列の総数は等しいので、nPr = n×n-1Pr-1 である。 ・ n-1Pr-1 = (n-1)×(n-2)× … ×(n-r+2)×(n-r+1) … r-1 項の積 nPr = n×(n-1)×(n-2)× … ×(n-r+2)×(n-r+1) … r 項の積 なので、両式を比較すると、nPr = n×n-1Pr-1 である。 ・ n-1Pr-1 = (n-1)!/ ((n-1)-(r-1))! = (n-1)!/(n-r)! （※ ここでnPr と分母が共通になることに注意） nPr = n!/(n-r)! 一方、n×(n-1)! = n! なので、nPr = n×n-1Pr-1 である。 (2) ・nPr は、互いに重複のない n 個の要素から r 個を取り出して並べるときの順列の総数である。 いま、n 個の要素のうち 1 つに注目して、この特別な要素が含まれないような順列と含まれるような順 列に区別することを考える。 この特別な要素が含まれない順列の総数は、互いに重複のない n-1 個の要素から r 個を並べてできる 順列の総数であるから、n-1Pr となる。 次に、この特別な要素が必ず含まれる順列を考える。要素を置く位置（先頭から何番目にあるのか）に は、r 個の選択肢がある。ここに特別な要素を置き、残りの位置すなわち r-1 個に対し、残された n-1 個の要素を置いて順列を作ればよい。従って、r×n-1Pr-1 となる。 この特別な要素が含まれる、含まれないは、互いに排他的であり、その和が全体を形成する。従って、 特別な要素に着目せずに作った順列の総数は、この特別な要素が含まれない順列の総数と、含まれる順 列の総数の和に等しい。よって、nPr = n-1Pr + r×n-1Pr-1 である。 ・ 与式右辺 = n-1Pr + r×n-1Pr-1 = (n-1)!/(n-r-1)! + r×(n-1)!/(n-r)! = (n-r)×(n-1)!/{(n-r)(n-r-1)!} + r×(n-1)!/(n-r)! = (n-r)×(n-1)!/(n-r)! + r×(n-1)!/(n-r)! = {(n-r) + r}×(n-1)!/(n-r)! = n×(n-1) ! /(n-r)! = n!/(n-r)! = nPr = 与式左辺 ・ すでに p202 例題 5 で調べたように、nCr = n-1Cr + n-1Cr-1 が成り立つことが知られている。 nCr = nPr/r! の関係があることに注意して、この公式を式変形する。 nCr = n-1Cr + n-1Cr-1 の両辺を r! で割る。 nCr/r! = n-1Cr/r! + n-1Cr-1/r! = n-1Cr/r! + n-1Cr-1/{r(r-1)!} = n-1Cr/r! + r×n-1Cr-1/(r-1)! よって、nPr = n-1Pr + r×n-1Pr-1 である。 (3) ・ 与式右辺 = (n/(n-r))×n-1Cr = (n/(n-r))×(n-1)!/((n-r-1)!･r!) = n･(n-1)!/((n-r)･(n-r-1)!×r!) = n!/((n-r)!×r!) = nCr = 与式左辺 ・ n-1Cr = (n-1)!/((n-r-1)!･r!) なので r/(n-r)×n-1Cr = (n-1)!/((n-r)･(n-r-1)!×r!/r) = (n-1)!/((n-r)!･(r-1)!) = n-1Cr-1 である。 すでに p202 例題 5 で調べたように、nCr = n-1Cr + n-1Cr-1 が成り立つことが知られている。 nCr = n-1Cr + n-1Cr-1
= n-1Cr + r/(n-r)×n-1Cr = (1 + r/(n-r))×n-1Cr = (n/(n-r))×n-1Cr ※ パスカルの三角形において、(3) の関係は ↙ r=0 n=0 1 ↙ r=1 n=1 1 1 ↙ r=2 n=2 1 2 1 ↙ r=3 n=3 1 3 3 1 ↙ r=4 n=4 1 4 6 4 1 ↙ r=5 n=5 1 5 10 10 5 1 ↙ r=6 n=6 1 6 15 20 15 6 1 ↙ r=7 n=7 1 7 21 35 35 [21] 7 1 ↙ r=8 n=8 1 8 28 56 70 [56] 28 8 1 8C5 = 56 7C5 = 21 のような、右上の肩の数字との関係。56 = 21×8/(8-5) となっている。 (4) ・ 与式右辺 = (n-r+1)/r ×nCr-1 = (n-r+1)/r × n!/((n-r+1)!･(r-1)!) = n!/{((n-r+1)!/(n-r+1))×(r･(r-1)!)} = n!/{(n-r)!×r!} = nCr = 与式左辺 ・ nCr をたとえば n = 7 の場合について、立式を並べると、左から r = 0 から大きくなる順に、 1, 7 1, 7×6 1×2, 7×6×5 1×2×3, 7×6×5×4 1×2×3×4, 7×6×5×4×3 1×2×3×4×5, 7×6×5×4×3×2 1×2×3×4×5×6, 7×6×5×4×3×2×1 1×2×3×4×5×6×7, となっている。 つまり、左の数字に対して、×7/1, ×6/2, ×5/3, ×4/4, ×3/5, ×2/6, ×1/7 倍になる。 これは、n が 7 以外の任意の数になっても同様で、 左の数字に対して ×n/1, ×(n-1)/2, ×(n-2)/3, … , ×3/(n-2), ×2/(n-1), ×1/n 倍になる。 これを一般的に書きなおすと、nCr = nCr-1×(n+1-r)/r の関係が成り立つことが分かる。 ※ n の代わりに n-1 で書くと n-1Cr = n-1Cr-1×(n-r)/r であり、この関係は(3)の証明でも使用した。 465 2 人で引き分けの無いゲームを a, b の 2 人で行ったときの、各回の勝者を a, b で表す。 7 回目以前に、ではなく、7 回目に決着がつく必要があるので、 (1) 6 回目と 7 回目のゲームの勝者が同じであり、1 回目から 6 回目までは連勝がないことが条件。 abababb, または、bababaa となる 2 通りのみが条件に合致する。 (2) 5 回目から 7 回目までの勝者が同じであり、4 回目はこれとは異なる勝者である必要がある。
つまり、***abbb または、***baaa のパターン。*** には、a, b の 3 連勝が生じないようにする。 ***abbb の *** に入るかどうかを、a,b の重複順列 2^3 = 8 通りについて検討する。 aaa × aab ○ aba ○ abb ○ baa × bab ○ bba ○ bbb × 具体的には、aaa, bbb と *** 内だけで 3 連勝が生じてしまうものと、 baa のように、4 回目の a と併せて 3 連勝になってしまうものが条件に合わず、残りの 5 通りが OK. ***abbb に対し 5 通りが条件に合致し、a と b をすべて入れ換えた ***baaa に対しても 5 通りが条件に 合致するので、併せて 10 通りがある。
466 正九角形の頂点 9 つから、任意の 3 つを選ぶと三角形ができる。 選んだ 3 点の順番は関係ないので、組合せの問題として解けば良い。 ただし、回転して重なる三角形でも、異なる頂点の組合せのものは、別の三角形として数える。 (1) 9C3 = 9×8×7/(3×2×1) = 84 通り。 (2) 1 辺のみを共有するということは、2 つの頂点が指定され、残りの頂点が離れた位置にあるどれかを選ぶ。 つまり、9 つの頂点のうち、1 辺の両端およびその隣接位を除く 5 つの中から選ぶことになる。 辺は 9 つあるので、9×5 = 45 通り。 (3) 2 辺を共有する三角形を数えると、9 通りあり得る（二辺に挟まれた頂点の選び方として 9 通りなので）。 3 辺を共有する三角形は無い。 従って、全ての組合せから、1 辺を共有する 45 通り、2 辺を共有する 9 通りを引き去ると、 84 - 45 - 9 = 30 通りである。 (3)別解（数え間違いしやすいので非推奨） 辺を共有しない三角形の選び方は、3 つの頂点がいずれも隣接していない選び方である。 これを達成できる最も小さい正多角形は正六角形であり、その頂点の番号を 1 から 6 と置いたとき、1, 3, 5 または 2, 4, 6 のように 1 個置きに選ぶ形になる。すなわち、辺を共有しない三角形の頂点の間 にある選ばれなかった頂点の数は、(1, 1, 1) でしかない。 今、正九角形を対象に考えているので、余分に頂点が 3 つある。なわち、辺を共有しない三角形の頂点 の間にある選ばれなかった頂点の数は、(4, 1, 1)、(3, 1, 2), (3, 2, 1), (2, 2, 2) の 4 通りであ る。（2, 1, 3) などは、環状に並んだときすでに挙げたもの（この場合は (3, 2, 1)）と同じになり 重複するので数える必要はない。 (4, 1, 1)、(3, 1, 2), (3, 2, 1) となるものは、それぞれ 9 通りある（最も長い空き位置で考える。 頂点に番号を振る。初めの例では 4 連続する、1234, 2345, 3456、… 8912、9123 の 9 通りのみが空き 位置の候補として考えられる。それ以外のパターンについても同様に 9 通りずつ）。 (2, 2, 2) となるものは、対称性の関係から、空き位置が 12, 23, 34 の 3 通り。45 が空き位置になる パターンは、12 と重複、56 は 23 と重複、etc 従って、9×3 + 3 = 30 通り。 467 どの 6 個を使うのかによって場合分けする必要があることに注意。 1, 2, 2, 2, 3, 3 からなる「同じものを含む順列」の総数 = 6C1×5C3×2C2 = 6×10×1 = 60 通り。 1, 1, 2, 2, 3, 3 からなる「同じものを含む順列」の総数 = 6C2×4C2×2C2 = 15×6×1 = 90 通り。 1, 1, 2, 2, 2, 3 からなる「同じものを含む順列」の総数 = 6C2×4C3×1C1 = 15×4×1 = 60 通り。 以上を合計すると、210 通り。 なお、同じものを含む順列の総数の求め方は、以下のように計算しても良い（同じ計算である）。 上の 3 つの場合について、それぞれ、 公式により、6C1×5C3×2C2 = 6!/(1!･3!･2!) = 60 通り、 6C2×4C2×2C2 = 6!/(2!･2!･2!) = 90 通り。 6C2×4C3×1C1 = 6!/(2!･3!･1!) = 90 通り。 以上を合計して、210 通り。 468 「円形に並べる」ので、円順列のように回転させて重なるものは同一と見做すものとして解く。 ※ 問題文の指示として必ずしも明白なわけではないが、回転させて重なるものは同一と見做すのでなければ、 一列に並べる場合と円形に並べる場合とで差異がないので、出題者の意図を読むことにする。 【要注意】ここで、円順列を考えたときには全ての要素が異なっていたので、一列に並べるための異なる順列 を作り、環状に並べたときに重複となるものを考慮するため、特定の要素の位置に注目して、たとえば 7 つの要素からなる円順列の場合、7!/7 = 6! のように計算できた。これは、7 人を円状に並べるとき 特定のリーダー1 人を任意の場所において、そこから残り 6 人を順に置いていく作業に相当する。 しかし、一方ですべての要素に重複がある場合、例えば赤 2 つ、白 3 つ、青 2 つの玉を円周上に並べる ことにすると、任意の位置に赤を置くことにしても、残りの赤 1 つ、白 3 つ、青 2 つを置くときのよう な 6!/(1!･3!･2!) で計算することができない。この計算式は、2 つの赤が区別されているときの計算方 法になってしまうからである。以下(1)の別解部分を参照のこと。
(1) 赤玉が 1 個しかないので、赤玉を任意の位置に置き、その位置を基準にして残り 6 個を並べると、 6C2×4C4 = 6!/(2!･4!) = 15 通り。 （別解）青 1 個を任意の位置においた場合、その位置を基準にして残り 6 個を並べると、 6C1×5C1×4C4 = 6!/(1!･1!･4!) と立式できる。 しかしはじめに 1 個置く青の球の選び方の組合せは 2C1だったから、その分重複しているので、 6C1×5C1×4C4 / 2C2 = 6!/(1!･1!･4!) ÷ 2 = 15 通り。 （別解）白 1 個を任意の位置においた場合、その位置を基準にして残り 6 個を並べると、 6C1×5C2×3C3 = 6!/(1!･2!･3!) と立式できる。 しかしはじめに 1 個置く白の球の選び方の組合せは 4C1だったから、その分重複しているので、 6C1×5C2×3C3 / 2C2 = 6!/(1!･2!･3!) ÷ 4 = 15 通り。 (2) 青玉 2 個が隣接するパターンの総数を全体から差し引く。 赤 1 個、青 1 個、白 4 個でできる並べ方の総数に等しい（もう一つの青は、今ある青の横に置く）。 (1) と同様に、5C1×4C4 = 5!/(1!･4!) = 5 通り。 (1 別解) と同様に、5C1×4C1×3C3 / 4C1 = 5!/(1!･1!･3!) ÷ 4 = 5 通りでもよい。 従って、15 - 5 = 10 通り。 469 問題文の指示に合致する 4 桁の数の総数は、順列の問題として考えればよく、6P4 = 360 通りある。 実際に、問題文の指示のように 4 桁の数字を並べてみる。 大きい桁（左の桁）に選べるなるべく小さい数字を選ぶものが 4 桁の数として小さいのであるから、 1234 → 1235 → 1236 → (3 個) 123* の 4 桁の数は、 3 個（3P1 = 3） 124* → (3 個) 125* → (3 個) 126* → (3 個) 12** の 4 桁の数は、3×4 = 12 個（4P2 = 12） 13** → (12 個) 14** → (12 個) 15** → (12 個) 16** → (12 個) 1*** の 4 桁の数は、12×5 = 60 個（5P3 = 60) 2*** → (60 個) 3*** → (60 個) 4*** → (60 個) 5*** → (60 個) 6*** → (60 個) **** の 4 桁の数は、60×6 = 360 個（6P4 = 360） (1) 4125 より前にある数字の数を数える。 1*** となるもの 5P3 = 60 個 2*** となるもの 5P3 = 60 個 3*** となるもの 5P3 = 60 個 4*** となる中では、4123 → 4125 と並ぶので、4000 番台で 4125 は 2 番目。 従って、4125 は 先頭から数えて、60×3 + 2 = 182 個目である。 (2) 100 個目に達するまで、順に先頭から調べていく。 1*** となるもの 5P3 = 60 個 2*** となるもの 5P3 = 60 個 61 個目から 120 個目までが、2000 番台 この時点で 120 個まで達するので、100 番目は、2000 番台のいずれかである。 21** となるもの 4P2 = 12 個 23** となるもの 4P2 = 12 個 24** となるもの 4P2 = 12 個 ここまでの和で、96 個 25** となるもの 4P2 = 12 個 ここまでの和で、108 個。つまり 97 個目から 2500 番台。 この時点で、100 番目は、2500 番台のいずれかであるころが分かる。 251* となるもの 3P1 = 3 個 ここまでの和で、99 個 253* となるもの 3P1 = 3 個 100 個目から 102 個目までが、2531 → 2534 → 2536。 従って、100 個目は、2531 である。
470 (a+b)n を展開したときのの一般項が、r の範囲を 0 から n として、 nCr･an-r･br であることを利用する。 (1) (1+1)n を展開したときの一般項は、 nCr･1n-r･1r = nCr である。 つまり、(1+1)n = nC0 + nC1 + nC2 + … + nCn-1 + nCn 左辺は、2n である。従って、与式 = 2n ※ n が偶数でも奇数でも無関係に成り立つ。 (2) (1-1)n を展開したときの一般項は、 nCr･1n-r･(-1)r = (-1)r･nCr である。 つまり、(1-1)n = nC0 - nC1 + nC2 - … + (-1)n-1･nCn-1 + (-1)n･nCn 左辺は、0n である。従って、与式 = 0 ※ n が偶数でも奇数でも無関係に成り立つ。 (3) (1)式では、全ての項が正なのに対し、(2) では交互に正と負の項が並ぶ。 この 2 つの式を足し合わせると、(2) 式では正の項のみが残り、負の項は(1) 式と打ち消される。 それぞれ、項の数は（0 番目から n 番目までの）n+1 個あり、(2) 式では最後の r = n で正となる。 (1+1)n + (1-1)n = 2{ nC0 + nC2 + nC4 + … + nCn-2 + nCn } 左辺は 2n - 0 = 2n である。従って、与式 = 2n/2 = 2n-1 472 【新しい考え方】 例題と同様に考えよ。なお、鉛筆に区別はなく、本数の問題のみで考える。 (1) 10 本の鉛筆と、3 個の仕切りの合計 13 個を「同じものを含む順列」として並べる。 従って13C10×3C3 = 13!/(10!･3!) = 286 通り (2) 4 本の鉛筆をまず 4 人に分配してしまい、残りを同様に分ける。 従って9C6×3C3 = 9!/(6!･3!) = 84 通り 473 球がそれぞれ区別される。A, B, C の区別される 3 つの箱に制約なく振り分ける場合の総数は、重複順列 として計算し、38 = 6561 通りある。 (1) C には 1 個も入れないので、8 個の球は A, B の 2 通りの選択肢しかなく、28 = 256 通りの入れ方があ る。しかし、全てが A に入ったもの、全てが B に入ったものの 2 通りは条件に合致しない。254 通り。 (2) 1 つの箱に全てが入るのは、A, B, C の 3 通りある。(1)では、2 つの箱の中に入るものを計算した。C が空 のもののほか、A が空、B が空の場合があり得るので、これらを全ての場合から差し引くと 6561 - 3 - 254×3 = 5796 通り。 474 1+9 と 9+1 のように出現順の異なるものは別の順列として数える。 例題の(2)、および 472(2) と同じ考え方を適用すると簡単になる。 (1) A, B, C の 3 人が 1 人最低 1 個の球を持ち、それぞれの持ち数の合計が 10 個になるよう分配する。 0 は許さないので、初めに 1 つずつ分配しておき、残り 7 つの玉と 2 つの仕切りを並べる。 9C7×2C2 = 36 通り 別解 3 個の数字の和が 10 になるためには、たとえば 1+1+8, 1+2+7, … , 1+7+2, 1+8+1 などのように「1 と残り 2 つで 10 になる」ものが、8 通り、「2 と残り 2 つで 10 になる」ものが 7 通り、「3 と残り 2 つ で 10 になる」ものが 6 通り、… となるので、8 + 7 + 6 + … + 2 + 1 = 36 通り。 (2) 10 個の数字を用いる場合、すべてが 1 である 1 通り、 9 個の数字を用いる場合、8 個の 1 と 1 つの 2 で、2 の出現位置違いの 9 通り 8 個の数字を用いる場合、7 個の 1 と 1 つの 3 の場合は、3 の出現位置違いの 8 通り 6 個の 1 と 2 つの 2 の場合は、2 の出現位置違いの 8C2 = 28 通り。 以上の合計で、1 + 9 + (8 + 28) = 46 通り。 (3) 10 個の球の間の 9 つの仕切りを置く可能性のある位置がある。それぞれに仕切りを置くか置かないかの 2 択で考える。仕切りを + 記号に置き換え、連続した球の数とで式を作る。 29 = 512 通り。
