組合(くみあわ)せ

異(こと)なる$n$個(こ)から$r$個(こ)を、順番(じゅんばん)を考(かんが)えずに選(えら)ぶ方法(ほうほう)の数(かず)を${}_{n}\mathrm{C}_{r}$と書(か)き、組合(くみあわ)せという。${}_{n}\mathrm{P}_{r}$では区別(くべつ)していた並(なら)び方(かた)を$r!$通(とお)りずつまとめる。だから${}_{n}\mathrm{C}_{r}=\dfrac{{}_{n}\mathrm{P}_{r}}{r!}$になる。

$r$個(こ)を選(えら)ぶことと、残(のこ)りの$n-r$個(こ)を選(えら)ばずに残(のこ)すことは同(おな)じことだ。だから${}_{n}\mathrm{C}_{r}={}_{n}\mathrm{C}_{n-r}$が成(な)り立(た)つ。

同(おな)じものがいくつか混(ま)ざった$n$個(こ)を1列(れつ)に並(なら)べる方法(ほうほう)を同(おな)じものを含(ふく)む順列(じゅんれつ)という。同(おな)じものが$p$個(こ)、$q$個(こ)、$r$個(こ)……とあるとき、並(なら)び方(かた)の重(かさ)なりを割(わ)る。すると$\dfrac{n!}{p!\,q!\,r!\cdots}$通(とお)りになる。

（押すと拡大して表示します）

例題(れいだい)：8人(にん)から3人(にん)の委員(いいん)会(かい)を選(えら)ぶ方法(ほうほう)は何通(なんとお)りか。

選(えら)ぶ3人(にん)の並(なら)び方(かた)は考(かんが)えない。${}_{8}\mathrm{P}_{3}=8\times7\times6=336$を考(かんが)える。これを3人(にん)の並(なら)べ方(かた)$3!=6$通(とお)りずつでまとめる。答(こた)えは${}_{8}\mathrm{C}_{3}=336\div6=\mathbf{56}$通(とお)りだ。

この56通(とお)りは、選(えら)ばれなかった残(のこ)り5人(にん)を選(えら)ぶ方法(ほうほう)の数(かず)${}_{8}\mathrm{C}_{5}$とも一致(いっち)する。

次(つぎ)に、A、A、A、B、B、Cの6文字(もじ)を1列(れつ)に並(なら)べる方法(ほうほう)は何通(なんとお)りか。Aが3個(こ)、Bが2個(こ)、Cが1個(こ)ある。同(おな)じものを含(ふく)む順列(じゅんれつ)の公式(こうしき)にあてはめる。$\dfrac{6!}{3!\,2!\,1!}=\dfrac{720}{12}=\mathbf{60}$通(とお)りだ。

なぜ${}_{n}\mathrm{C}_{r}={}_{n}\mathrm{P}_{r}\div r!$になるのか。選(えら)んだ$r$個(こ)を並(なら)べる方法(ほうほう)は$r!$通(とお)りあるが、組合(くみあわ)せでは並(なら)べ方(かた)の違(ちが)いを区別(くべつ)しない。同(おな)じ$r$個(こ)の組(くみ)は、${}_{n}\mathrm{P}_{r}$の中(なか)に$r!$個(こ)ずつ重(かさ)なって数(かぞ)えられている。その重(かさ)なった数(かず)で割(わ)る。

${}_{n}\mathrm{C}_{r}={}_{n}\mathrm{C}_{n-r}$になるのは、$n$個(こ)を2グループに分(わ)けられるからだ。「選(えら)ぶ$r$個(こ)」と「残(のこ)す$n-r$個(こ)」の2つに分(わ)ける。どちらから見(み)ても、同(おな)じ1つの分(わ)け方(かた)だ。

格子(こうし)の上(うえ)を右(みぎ)にだけ・上(うえ)にだけ進(すす)む最短(さいたん)経路(けいろ)の数(かず)も組合(くみあわ)せで数(かぞ)えられる。全部(ぜんぶ)の移動(いどう)のうち、どの回(かい)を「右(みぎ)」にするかを選(えら)ぶ方法(ほうほう)の数(かず)が、そのまま経路(けいろ)の総数(そうすう)になる。

（押すと拡大して表示します）