← 定理辞典📖 定理辞典

順列・組合せ

順列と組合せ

異なる nn 個から rr 個を取って並べる順列は nPr=n!(n−r)!{}_n\mathrm{P}_r=\dfrac{n!}{(n-r)!}、順番を区別せず選ぶ組合せは nCr=nPrr!=n!r! (n−r)!{}_n\mathrm{C}_r=\dfrac{{}_n\mathrm{P}_r}{r!}=\dfrac{n!}{r!\,(n-r)!}。

主張

異なる nn 個から rr 個を取り出すとき、「並べる」か「選ぶだけ」かで数え方が変わるよ。並べる(順番を区別する)のが順列で、11 個目は nn 通り、22 個目は残りの n−1n-1 通り、… とかけ算して nPr=n(n−1)⋯(n−r+1)=n!(n−r)!{}_n\mathrm{P}_r=n(n-1)\cdots(n-r+1)=\dfrac{n!}{(n-r)!}。順番を気にせず選ぶだけ(組を作る)のが組合せ。同じ組は、その中での並べ替え r!r! 通りぶん、順列では何回も重複して数えている。だからその重複でわって nCr=nPrr!=n!r! (n−r)!{}_n\mathrm{C}_r=\dfrac{{}_n\mathrm{P}_r}{r!}=\dfrac{n!}{r!\,(n-r)!}。「並べる=かけ算」「選ぶ=順列を並べ替えでわる」。この 22 つの見方の関係が、数え上げの土台になるんだ。

nPr=n!(n−r)!nCr=nPrr!=n!r! (n−r)!{}_n\mathrm{P}_r=\dfrac{n!}{(n-r)!}\qquad {}_n\mathrm{C}_r=\dfrac{{}_n\mathrm{P}_r}{r!}=\dfrac{n!}{r!\,(n-r)!}
A①②③B①②③C①②③D①②③A①A②A③B①B②B③C①C②C③D①D②D③
11 人目 44 通り ×\times 22 人目 33 通り =12=12 の枝先が並べ方(順列)。順番を区別しない組合せは、並べ替えのぶんでわった数になるよ。

成り立つ条件

取り出すもとの nn 個がたがいに異なり、同じものを 22 度は取らない(取って並べる/選ぶ)こと。0≤r≤n0\le r\le n。順番を区別するなら順列、しないなら組合せを使う。ここの読み分けがいちばん大事だよ。同じものを含む並べ方や、同じものを何度でも取れる重複順列・重複組合せは、これとは別の数え方になる。約束として 0!=10!=1、nC0=nCn=1{}_n\mathrm{C}_0={}_n\mathrm{C}_n=1 とする。

証明(なぜ成り立つ?)

並べる数 nPr{}_n\mathrm{P}_r をかけ算の原理で出し、同じ組が並べ替え r!r! 通りぶん重複して数えられていることから、nCr{}_n\mathrm{C}_r を割り算で導く。

  1. 1

    まず並べる数(順列)。11 個目は nn 通り、22 個目は残りで n−1n-1 通り、… と rr 個目まで選ぶと、かけ算の原理で次のようになる。

    nPr=n(n−1)(n−2)⋯(n−r+1)=n!(n−r)!{}_n\mathrm{P}_r=n(n-1)(n-2)\cdots(n-r+1)=\dfrac{n!}{(n-r)!}
  2. 2

    次に組合せを考える。rr 個を「選ぶだけ」なら、選んだ rr 個の組が 11 つに対し、その中の並べ方は rPr=r!{}_r\mathrm{P}_r=r! 通り。順列ではこの r!r! 通りを別々に数えていた。

  3. 3

    つまり順列 nPr{}_n\mathrm{P}_r は、組合せ 11 つを r!r! 回ずつ重複して数えた結果。だから「順列 == 組合せ ×r!\times r!」が成り立つ。

    nPr=nCr×r!{}_n\mathrm{P}_r={}_n\mathrm{C}_r\times r!
  4. 4

    両辺を r!r! でわれば、下の式が出る。「並べてから、順番違いの重複を割り落とす」。これが選ぶ数え方の正体だよ。

    nCr=nPrr!=n!r! (n−r)!{}_n\mathrm{C}_r=\dfrac{{}_n\mathrm{P}_r}{r!}=\dfrac{n!}{r!\,(n-r)!}

補足・つまずきポイント

便利な性質に nCr=nCn−r{}_n\mathrm{C}_r={}_n\mathrm{C}_{n-r} がある(「rr 個選ぶ」=「残す n−rn-r 個を選ぶ」だから)。rr が大きいときは小さい方で計算すると速い。パスカルの三角形 nCr=n−1Cr−1+n−1Cr{}_n\mathrm{C}_r={}_{n-1}\mathrm{C}_{r-1}+{}_{n-1}\mathrm{C}_r や、二項定理 (a+b)n=∑nCr an−rbr(a+b)^n=\sum {}_n\mathrm{C}_r\,a^{n-r}b^r の係数も、すべてこの nCr{}_n\mathrm{C}_r だよ。円形に並べる円順列は、回転して同じ並びを 11 つと数えるので (n−1)!(n-1)! になる(順列を回転ぶん nn でわる、同じ「重複でわる」考え方)。

関連する定理

見て確かめる

言葉で読んだら、動くアニメと自分の手で確かめてみよう。

使いどころ

この定理が、実際の問題でどう効くのかを見てみよう。