$_{n}\text{C}_{r}$の性質

組合せ $_{n}\mathrm{C}_{r}$ について次の式が成り立つ.

$_{n}\mathrm{C}_{r}$ の性質

  1. $_{n}\mathrm{C}_{r}=\ _{n}\mathrm{C}_{n-r}$
  2. (選ばれるもの・選ばれないもの)

  3. $_{n}\mathrm{C}_{r}=\ _{n-1}\mathrm{C}_{r}+\ _{n-1}\mathrm{C}_{r-1}$
  4. (特定のものについての場合分け)

  5. $r_{n}\mathrm{C}_{r}=n\ _{n-1}\mathrm{C}_{r-1}$
  6. (リーダーの公式)

暗記$_{n}\mathrm{C}_{r}$ の性質の証明

上の i. ~ iii. が成り立つことを,

  1. 計算式を用いた方法
  2. 組合せの意味を考えた説明

でそれぞれ証明せよ.

  1. $_{n}\mathrm{C}_{r}=\ _{n}\mathrm{C}_{n−r}$
    1. ~計算式を用いた方法~
    2. \begin{align} &\ _{n}\mathrm{C}_{r}\\ =&\ \frac{_{n}\mathrm{P}_{r}}{r!}\\ =&\ \frac{n!}{(n-r)!r!}\\ =&\ \frac{1}{(n-r)!}\cdot\frac{n!}{r!}\\ =&\ \frac{1}{(n-r)!}\cdot\frac{n!}{\left\{n-(n-r)\right\}!}\\ =&\ \frac{1}{(n-r)!}\cdot\ _{n}\mathrm{P}_{n-r}\\ =&\ \frac{_{n}\mathrm{P}_{n-r}}{(n-r)!}\\ =&\ _{n}\mathrm{C}_{n-r} \end{align}

      $\uparrow$ 組合せ $_{n}\mathrm{C}_{r}$ の計算順列 $_{n}\mathrm{P}_{r}$ の計算参照

    3. ~組合せの意味を考えた説明~
    4. 異なる $n$ 個の中から $r$ 個選ぶ $_{n}\mathrm{C}_{r}$ 通りそれぞれは, $n$ 個のものから選ばずに残す $(n−r)$ 個のものを選ぶ $_{n}\mathrm{C}_{n−r}$ 通りと 一対一に対応する.つまり, $r$ 個選ぶとは,選ばない $n−r$ を「選ぶ」ことと等しい. よって

      \begin{align} _{n}\mathrm{C}_{r}=\ _{n}\mathrm{C}_{n-r} \end{align}

      が成り立つ.

  2. $_{n}\mathrm{C}_{r}=\ _{n−1}\mathrm{C}_{r}+\ _{n−1}\mathrm{C}_{r−1}$
    1. ~計算式を用いた方法~
    2. \begin{align} &\ _{n-1}\mathrm{C}_{r}+\ _{n-1}\mathrm{C}_{r-1}\\ =&\frac{_{n-1}\mathrm{P}_{r}}{r!}+\frac{_{n-1}\mathrm{P}_{r-1}}{(r-1)!}\\ =&\frac{(n-1)!}{\left\{(n-1)-r\right\}!r!}\!\\ &\qquad+\!\frac{(n-1)!}{\left\{(n-1)-(r-1)\right\}!(r-1)!}\\ =&\frac{(n-1)!}{(n-r-1)!r!}+\frac{(n-1)!}{(n-r)!(r-1)!}\\ =&\frac{(n-1)!}{(n-r-1)!(r-1)!}\left\{\frac{1}{r}+\frac{1}{n-r}\right\}\\ =&\frac{(n-1)!}{(n-r-1)!(r-1)!}\cdot\frac{n}{r(n-r)}\\ =&\frac{n!}{(n-r)!r!}\\ =&\frac{_{n}\mathrm{P}_{r}}{r!}\\ =&_{n}\mathrm{C}_{r} \end{align}

      $\uparrow$ 組合せ $_{n}\mathrm{C}_{r}$ の計算順列 $_{n}\mathrm{P}_{r}$ の計算参照

    3. ~組合せの意味を考えた説明~
    4. 異なるn個のものの中からr個選ぶ方法は,次の2つの場合に分けることができる.

      1. ある特定の1個を含まないで $r$ 個選ぶ
      2. $\uparrow\ _{n−1}\mathrm{C}_{r}$ 通り

      3. ある特定の1個を含んで $r$ 個選ぶ
      4. $\uparrow\ _{n−1}\mathrm{C}_{r−1}$ 通り

      この2つは同時に起こることはないので

      \begin{align} _{n}\mathrm{C}_{r}=\ _{n-1}\mathrm{C}_{r}+\ _{n-1}\mathrm{C}_{r-1} \end{align}

      $\uparrow$ 和の法則

      が成り立つ.

  3. $r\ _{n}\mathrm{C}_{r}=n\ _{n-1}\mathrm{C}_{r-1}$
    1. ~計算式を用いた方法~
    2. \begin{align} &\ r\ _{n}\mathrm{C}_{r}\\ =&\ r\times\frac{_{n}\mathrm{P}_{r}}{r!}\\ =&\ r\times\frac{n!}{(n-r)!r!}\\ =&\ \frac{n!}{(n-r)!(r-1)!}\\ =&\ n\times\frac{(n-1)!}{\left\{n-1-(r-1)\right\}!(r-1)!}\\ =&\ n\times\frac{_{n-1}\mathrm{P}_{r-1}}{(r-1)!}\\ =&\ n\ _{n-1}\mathrm{C}_{r-1} \end{align}

      $\uparrow$ 組合せ $_{n}\mathrm{C}_{r}$ の計算順列 $_{n}\mathrm{P}_{r}$ の計算参照

    3. ~組合せの意味を考えた説明~
    4. $n$ 人の中から $r$ 人の班をつくり班長を決める場合の数について考える. $n$ 人の中から班員 $r$ 人選び,その $r$ 人の中からリーダーを1人決める方法には $_{n}\mathrm{C}_{r}\times{r}$ 通りある. また別の方法として, $n$ 人の中から先にリーダーを決めておき,残りの班員 $r−1$ 人を選ぶ方法には $n\ _{n−1}\mathrm{C}_{r−1}$ 通りある. よって

      \begin{align} r_{n}\mathrm{C}_{r}=n\ _{n-1}\mathrm{C}_{r-1} \end{align}

      が成り立つ.

最短経路

説明文

説明文

図のように,東西に走る道路と南北に走る道路があるとする.南西の角にあるA地点から,北東の角にあるB地点に至る

最短経路について以下の問に答えよ.

  1. 最短経路は全部で何通りあるか求めよ.
  2. C地点を通る最短経路は何通りあるか.また,D地点を通る最短経路は何通りあるか,それぞれ求めよ.
  3. C地点またはD地点を通る最短経路は何通りあるか求めよ.

北に1区画進むことを↑,東に1区画進むことを→で表すと,例えば図のように進む場合には

$\uparrow\rightarrow\rightarrow\rightarrow\uparrow\uparrow\rightarrow\uparrow\uparrow\rightarrow\rightarrow$

と表すことができる.

  1. 北に1区画進むことを $\uparrow$ ,東に1区画進むことを $\rightarrow$ で表すと,A地点からB地点への最短経路は,5個の $\uparrow$ と6個の $\rightarrow$ ($\uparrow\uparrow\uparrow\uparrow\uparrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow$ ) を一列に並べる順列の総数に等しい.
  2. よって,求める最短経路の数は

    $\dfrac{11!}{5!6!}=\boldsymbol{462}$ 通り

    $\uparrow$ 同じ物を含む順列 $\text{C}(n_1,n_2,\cdots,n_m)$ の計算

    となる.

    1. (C地点を通る最短経路)
    2. まず,A地点からC地点までの最短経路の数は

      $\dfrac{4!}{2!2!}=6$ 通り

      であり,この6通りそれぞれに対し,C地点からB地点までの最短経路

      $\dfrac{7!}{3!4!}=35$ 通り

      が決まるから,積の法則より

      $6\times35=\boldsymbol{210}$ 通り

    3. (D地点を通る最短経路)
    4. 同様にして

      $\dfrac{7!}{4!3!}\times\dfrac{4!}{1!3!}=35\times4=\boldsymbol{140}$ 通り

  3. 集合C,Dをそれぞれ
  4. $C$ :C地点を通る最短経路

    $D$ :D地点を通る最短経路

    とおくと, $n(C\cap D)$ ,つまりC,D両地点を通る最短経路の数は

    \begin{align} n(C\cap D)=&\ \frac{4!}{2!2!}\times\frac{3!}{2!1!}\times\frac{4!}{1!3!}\\ =&\ 6\times3\times4=72 \end{align}

    であるから, $n(C\cup D)$ ,つまり求める最短経路の数は

    \begin{align} n(C\cup D)&=n(C)+n(D)-n(C\cap D)\\ &=210+140-72=\boldsymbol{278} \end{align}

    ∴278通り

    $\uparrow$ 包含と排除の原理 (2集合版)