順列・組合せ
アプリで開く →
進み具合を記録できるアプリ版です（ノード単位の直リンクはありません）
要点
P と C の違いは『並べるか、選ぶか』という言葉の違いではなく、順序の違いを別のものと数えるかどうかにある。C(n,r) = P(n,r)/r! という関係が示しているのは、組合せとは順列を r! 個ずつまとめて1つと見たものだ、ということである。この『まとめて割る』という見方を持っておくと、円順列でもじゅず順列でも、何個ずつまとめているのかを考えるだけで処理できる。公式を覚える対象ではなく、導ける対象にしておくこと。
こんなときに使う
- 並び順に意味がある（座席、桁、順位、役職）→ P
- 選ぶだけで順序に意味がない（メンバー、部分集合）→ C
- 迷ったら P で数えてから、何個ずつ重複しているかを考えて割る
- 『少なくとも1人』→ 余事象
- C(n, r) = C(n, n−r) を使うと計算が軽くなることが多い
手順
- 1. 順序に意味があるかを判定する
- 2. あるなら P(n,r) = n!/(n−r)!、ないなら C(n,r) = n!/{r!(n−r)!}
- 3. 判断に迷ったら、まず順序つきで数える
- 4. そのあと、同じものが何個ずつ重複しているかを考えて割る
- 5. n を小さくして書き出し、検算する
例題
8人の中から (1) 3人の委員を選ぶ方法 (2) 委員長・副委員長・書記を1人ずつ選ぶ方法 は、それぞれ何通りか。
解答
- (1) 誰が選ばれるかだけが問題で、順序に意味はない。
- C(8,3) = 8·7·6 / (3·2·1) = 56 通り
- (2) 同じ3人でも、誰が委員長かで別のものと数える。順序に意味がある。
- P(8,3) = 8·7·6 = 336 通り
- 【2つの関係】
- 336 = 56 × 6 = 56 × 3!
- 同じ3人組に対して、役職の割り当て方が 3! = 6 通りある。
- つまり順列は、組合せを 3! 倍に細分したもの。逆に C = P / r! と書けるのはこのため。
- この対応を理解していれば、公式を忘れても復元できる。
別解・ほかの見方
- P で数えてから r! で割って C を得る（公式を忘れたときの復元法）
- 余事象を使う（『少なくとも1人は女子』は『全員男子』を引く）
- パスカルの関係 C(n,r) = C(n−1,r−1) + C(n−1,r) を使う（着目した1人を含むか含まないかで分ける）
- 二項定理と結びつける（C(n,r) は (a+b)ⁿ の展開係数）
落とし穴
- 区別の有無が曖昧なまま公式を選ぶ
- 『少なくとも』を直接数えようとして場合分けが爆発する
- C(n,r) の計算で約分を先にせず、大きな階乗を計算してミスする
- 選んだあとに並べる問題で、選ぶ段階と並べる段階を混ぜてしまう
- 区別する/しないの前提が曖昧
なぜ大事か
道具。使い所を誤らないことが本体
東大での出方
道具として使う単元で、単独の出題はない。ただし東大の確率では『分母をどう数えるか』の選択が本体なので、P と C のどちらで数えるかを分母・分子で揃える判断が毎回必要になる。
確認問題
- 男子5人、女子4人から4人を選ぶとき、女子が少なくとも1人含まれる選び方は何通りか
- 8人を A, B の2つの部屋に分ける（どちらも空でない）方法は何通りか
- C(10,3) と C(10,7) が等しいことを、意味から説明せよ
発展
二項係数の恒等式（C(n,0)+C(n,1)+…+C(n,n) = 2ⁿ など）を、数え方を変えて同じものを数えるという方法で証明する。組合せ論的証明の考え方は、東大の論証問題でも効く。
前提になるノード
このノードを前提にするノード
「場合の数」のノード
解説は自作です。誤りに気づいたら お問い合わせ（/contact/）から教えてください。