§B4.3順列・組合せ

最終更新

数える前に、順序を区別するか、同じものを区別するか、同じ種類を繰り返し選んでよいかを確認します。

1 順列と組合せ

定義 1.1 (順列と組合せ). 異なるnn個からrr個を選んで一列に並べる方法の個数をnPr{}_nP_rと書きます。異なるnn個から順序を区別せずにrr個を選ぶ方法の個数をnCr{}_nC_rと書きます。ただし、n,rn,rは0≤r≤n0\le r\le nを満たす整数とします。

積の法則から順列の公式を導きます。

公式 1.2 (順列の公式).

nPr=n(n−1)⋯(n−r+1)=n!(n−r)!.{}_nP_r=n(n-1)\cdots(n-r+1)=\frac{n!}{(n-r)!}.

証明. 第1番目はnn通り、第2番目は残りのn−1n-1通りであり、同様に第rr番目はn−r+1n-r+1通りです。積の法則を用いると公式を得ます。▨

選んだrr個の並べ替えをまとめて数えると、組合せの公式を得ます。

公式 1.3 (組合せの公式).

nCr=nPrr!=n!r!(n−r)!.{}_nC_r=\frac{{}_nP_r}{r!}=\frac{n!}{r!(n-r)!}.

証明. 一つのrr個の組からはr!r!通りの順列が得られます。したがってnPr=r! nCr{}_nP_r=r!\,{}_nC_rです。両辺をr!r!で割ると公式を得ます。▨

公式 1.4 (二項係数の対称性).

nCr=nCn−r.{}_nC_r={}_nC_{n-r}.

選ぶrr個を決めることと、選ばないn−rn-r個を決めることが一対一に対応するためです。

2 同じものを含む順列

公式 2.1 (同じものを含む順列).nn個のうち同じ種類のものがそれぞれn1,…,nkn_1,\ldots,n_k個あり、n1+⋯+nk=nn_1+\cdots+n_k=nであるとき、異なる並べ方は

n!n1!⋯nk!\frac{n!}{n_1!\cdots n_k!}

通りあります。

証明. 一時的にすべてを区別するとn!n!通りです。同じ種類のnin_i個につけた印を入れ替えるni!n_i!通りは同じ並びを表すので、各iiについて割ります。▨

例 2.2 (文字の並べ替え). 文字列 MISSISSIPPI には M が1個、I が4個、S が4個、P が2個あります。異なる並べ方は

11!4!4!2!\frac{11!}{4!4!2!}

通りです。

3 円順列

公式 3.1 (円順列). 異なるnn個を円形に並べ、回転によって一致する並びを同一視すると、並べ方は(n−1)!(n-1)!通りあります。ただしn≥1n\ge1とします。

証明. 一つの対象を基準位置へ固定すると、残りのn−1n-1個を並べる順列と一対一に対応します。鏡映による一致は同一視していないので、さらに2で割りません。▨

4 重複を許す組合せ

公式 4.1 (重複組合せ).nn種類から重複を許して合計rr個を選ぶ方法は

n+r−1Cr{}_{n+r-1}C_r

通りあります。ただしn≥1, r≥0n\ge1,\ r\ge0とします。

証明. 各種類を選ぶ個数をx1,…,xnx_1,\ldots,x_nとすると、x1+⋯+xn=rx_1+\cdots+x_n=rを満たす非負整数解を数えればよいです。rr個の丸とn−1n-1本の仕切りを一列に並べる方法に対応するので、全n+r−1n+r-1箇所から丸のrr箇所を選びます。▨

5 演習

  1. 8人から会長と副会長を選ぶ方法と、委員2人を選ぶ方法をそれぞれ求めます。
  2. BANANA の異なる並べ方を求めます。
  3. 6人を円卓へ並べる方法を求めます。
  4. 4種類の菓子から重複を許して7個を選ぶ方法を求めます。

1は会長と副会長が8P2=56{}_8P_2=56通り、委員2人が8C2=28{}_8C_2=28通りです。2は6!/(3!2!)=606!/(3!2!)=60通り、3は5!=1205!=120通り、4は10C7=120{}_{10}C_7=120通りです。

例題

条件と何を求めるかを確認してから、式と答えの対応を見比べてください。

次の値を計算せよ。

解法の型nPr=n(n−1)⋯(n−r+1){}_{n}\mathrm{P}_{r} = n(n-1)\cdots(n-r+1)

  1. 例題 1

    5P4{}_{5}\mathrm{P}_{4}

解法の型nCr=nPr/r!{}_{n}\mathrm{C}_{r} = {}_{n}\mathrm{P}_{r}/r!。rr が大きければ nCn−r{}_{n}\mathrm{C}_{n-r} に直すと楽

  1. 例題 1

    6C4{}_{6}\mathrm{C}_{4}

演習

問題を解いてから「解答・解説」を開けます。

次の値を計算せよ。

演習を読み込み中…

演習を読み込み中…

前提記事