異なる$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!\,通りの並び方があるから,\,積の法則}を適用する.$
