組合せの基本と順列との関係、二項係数nCrの等式の証明

スポンサーリンク
異なる$n}$個のものの中から異なる$r}$個を取る組合せの総数は 順列\,P nr\,と同様,\ 公式の丸暗記では全く応用が利かないので,\ 意味合いの理解が必須}である. なお,\ CはC}ombination}\ (組合せ)に由来する. まず,\ C nr=P nr}{r!}\ の意味合いを,\ 4個の数字1,\ 2,\ 3,\ 4から3個とる組合せの総数を例に考える. 組合せを考える前に,\ まず4個から3個取って並べること(順列)を考える. これは\,P43=4・3・2=24通りあるはずで,\ すべて書き出すと以下となる.  [123],\ [132],\ [213],\ [231],\ [312],\ [321]  組合せは\ \ (1,\ 2,\ 3)  [124],\ [142],\ [214],\ [241],\ [412],\ [421]  組合せは\ \ (1,\ 2,\ 4)  [134],\ [143],\ [314],\ [341],\ [413],\ [431]  組合せは\ \ (1,\ 3,\ 4)  [234],\ [243],\ [324],\ [342],\ [423],\ [432]  組合せは\ \ (2,\ 3,\ 4) このように,\ 順列は24通りあるが,\ 組合せは4通りしかない. 一般に,\ 「選んでかつ並べる(順列)」と「選ぶだけ(組合せ)」では,\ 組合せの方が総数が少なくなる. しかし,\ 計算で求めやすいのは順列\,P nr\,の方である.\ 所詮は積の法則の適用にすぎないからである. そこで,\ 順列を利用して組合せを求める}ことになる. つまり,\ 一旦選んで並べた後,\ その並び順を無視すると何通りになるかを求める}のである. ここで重要になるのは,\ 順列と組合せの対応}である. 上の例では,\ 1つの組合せに対して,\ 6つの順列が対応している. これは,\ 異なる3個のものを並べるときの順列の総数が\,3!=6通りあることに起因する. 結局,\ 順列の総数\,P43\,を3!\,で割るとP 43}{3!},\ 組合せの総数\,C43\,が得られる}わけである. r!\,で割ることがr個分の並び順を無視することを意味する}点が応用上重要である. nからr個の連続する整数の積)}{(rから1までの整数の積)} この階乗表現の意味合いは「同じものを含む順列」の項目で確認する. 以下の$二項係数\,C nr\,の等式$が成り立つことを示せ. {$n$個から$r$個取り出すことは,\ $n$個から残すもの$n-r$個を選ぶことに等しい.} 証明の方針には,\ 「組合せの意味を考える」「公式\,C nr=n!}{r!(n-r)!}\,を用いて計算で示す」}がある. (1)の等式は,\ 意味合いを考えるとほとんど当たり前に成り立つことがわかる. 例えば,\ 異なる9個のものから7個取る組合せの総数は,\ 残すもの2個を選ぶ組合せの総数に等しい. 等式\,C nr=C{n}{n-r}\,は常識であり,\ 利用機会が非常に多い.\ 主に以下のように利用する. の○の部分の数を小さくして計算しやすくする) n○\,の○の部分に文字が含まれないようにする)  (2)\ \ 異なる$n$個のものから$r$個を選ぶ組合せの総数は $C nr}$ 一方,\ 特定の1個(A)に着目して異なる$n$個のものから$r$個を選ぶ}ことを考える. Aを選ぶ場合とAを選ばない場合があり,\ この2つの場合は互いに排反である. [1]\ \ Aを選ぶ}とき A以外の$n-1$個から$r-1$個を選ぶ}組合せの総数は $C{n-1}{r-1$ [2]\ \ Aを選ばない}とき A以外の$n-1$個から$r$個を選ぶ}組合せの総数は $C{n-1}{r$ 具体例を示しておく.\ \ Aを含む異なる8個のものから3個を選ぶときの組合せの総数を考える. (A,\ A以外,\ A以外)の組合せの総数は   \ \,A}以外の7個から2個選べばよいから C72\,通り (A以外,\ A以外,\ A以外)の組合せの総数は A}以外の7個から3個選べばよいから C73\,通り 別解は一見複雑だが,\ 5!=5・4!\ などが成り立つことを理解できていれば容易である. 複雑な\,C{n-1}{r-1}+C{n-1}{r}\,を変形していき,\ C nr\,となることを示す. 公式適用後,\ 共通因数をくくり出す.\ 分子は(n-1)!\,をくくり出せるが,\ 問題は分母である. r!=r・(r-1)!,\ (n-r)!=(n-r)・(n-r+1)!\ より,\ (r-1)!\,と(n-r-1)!\,をくくり出せる. 括弧内を通分した後にうまく因数を組み合わせると,\ 階乗のみで表すことができる. n=8,\ r=3のときの具体例を示しておく.  (3)\ \ $n$人から$r$人の委員を選び,\ さらにその$r$人の委員の中から1人の委員長を選ぶ.} 以下の2通りの方法が考えられる. 先に$n$人から$r$人の委員を選び,\ その後$r$人の委員の中から1人の委員長を選ぶ.} 先に$n$人から1人の委員長を選び,\ その後残りの$n-1$人から$r-1$人の委員を選ぶ.} いくつかのパターン問題や状況で利用することになる等式である. 誘導がつかないこともあるので,\ 上級者は暗記しておきたい. 本解の意味合いを理解できていれば覚えやすいだろう. 別解では,\ 両辺の複雑さが同程度なので,\ それぞれ変形して同じ式になることを示している. 男子7人,\ 女子5人から5人を選ぶとき,\ 次の場合の数を求めよ.$ $ (1)\ \ 12人から5人を選ぶ.$ $ (2)\ \ 男子3人,\ 女子2人を選ぶ.$ $ (3)\ \ 5人の中に女子が少なくとも1人含まれる.$ $ (4)\ \ 特定の男子A,\ Bと女子C}が含まれる.$ $ (5)\ \ 特定の男子Aを含み,\ 特定の女子Cを含まない.}$ $ (6)\ \ 男子2人,\ 女子3人を選んで1列に並べる.$ \\ A,\ B以外の男子5人とC以外の女子4人から残りの2人を選ぶ.} \ \ $そのときの組合せの総数は   (5)\ \ A以外の男子6人とC以外の女子4人から残りの4人を選ぶ.} (2)\ \ 男子7人から3人を選ぶ組合せの総数が\ C73=35\ 通りある. \ \ その35通りのいずれに対しても,\ 女子5人から2人を選ぶ組合せの総数が\ C52\ 通りある. \ \ よって,\ 積の法則を適用する. (3)\ \ 「少なくとも1人」なので,\ 補集合を利用}する. \ \ 「女子が1人も含まれない」,\ つまり「\,5人全員が男子」を除けばよい. \ \ C nr=C{n}{n-r}\,を利用すると計算が楽になる. (4)\ \ A,\ B,\ C}の3人は選ばれることが決定している. \ \ よって,\ A,\ B,\ C}以外の9人から残りの2人を選ぶだけである.  (A,\ B,\ C,\ \maru{?},\ \maru{?) (5)\ \ (A},\ \maru{?},\ \maru{?},\ \maru{?},\ \maru{?})\ の未定の4人をAとCを}除く10人から選べばよい. (6)\ \ 本問は,\ 12人から5人を選んで並べる順列}である. \ \ しかし,\ 単純に\,P{12}{5}\,とすると,\ 男子3人,\ 女子2人の場合などもすべて含まれてしまう. \ \ かといって\,P72×P53\,とすると,\ 男子と女子を別々に並べたことになってしまう. \ \ 並べるのだが選び方に条件がある場合,\ 選ぶことと並べることを別々に考える.} \ \ つまり,\ まず条件を満たすように選び,\ その後で並びを考慮する}のである. \ \ 本問の場合,\ まず男子2人と女子3人の計5人を選ぶ. \ \ $この選び方\,C72×C52\,通りのいずれに対しても5!\,通りの並び方があるから,\,積の法則}を適用する.$