COMPASS

真の理解のためのシンプルな数学のノート

数式を枠からはみ出さずに表示するためには, 画面を横に傾けてください(532 ピクセル以上推奨).

組合せ

組合せ

定義≪組合せ≫

 $n,$ $r$ を $n \geqq r > 0$ なる整数とする. 異なる $n$ 個のものから $r$ 個のものを選んで $1$ 組にしたものを, $n$ 個から $r$ 個を取る組合せ(combination)と呼び, その方法の総数を ${}_n\mathrm C_r$ で表す. $n = 0$ または $r = 0$ のときは, ${}_n\mathrm C_r = 1$ と定める. ${}_n\mathrm C_r$ の形に表された数を二項係数(binomial coefficient)と呼ぶ.

定理≪二項係数の公式≫

 $n \geqq r > 0$ なる整数 $n,$ $r$ に対して, \[ {}_n\mathrm C_r = \frac{{}_n\mathrm P_r}{r!} = \frac{n!}{r!(n-r)!}\] が成り立つ.

証明

 $n$ 個から $r$ 個を取る組合せにおいて, 取り出した $r$ 個に順序をつける方法は $r!$ 通りあり, それらを合算すると $n$ 個から $r$ 個を取る順列の総数 ${}_n\mathrm P_r$ になるから, \[ {}_n\mathrm C_r\times r! = {}_n\mathrm P_r\] が成り立つ. よって, 両辺を $r!$ で割ると, 求める等式が得られる.

問題≪パスカルの法則≫

 $0 < r < n$ なる整数 $n,$ $r$ に対して, 次のことを示せ.
(1)
${}_{n+1}\mathrm C_{r+1} = {}_n\mathrm C_r+{}_n\mathrm C_{r+1}$ が成り立つ.
(2)
$\displaystyle\sum\limits_{k = r}^n{}_k\mathrm C_r = {}_{n+1}\mathrm C_{r+1}$ が成り立つ.

解答例

(1)
二項係数の定義により, \begin{align*} {}_n\mathrm C_r+{}_n\mathrm C_{r+1} &= \frac{n!}{r!(n-r)!}+\frac{n!}{(r+1)!\{ n-(r+1)\}!} \\ &= \frac{n!\{ (r+1)+(n-r)\}}{(r+1)!(n-r)!} \\ &= \frac{(n+1)!}{(r+1)!\{ (n+1)-(r+1)\}!} \\ &= {}_{n+1}\mathrm C_{r+1} \end{align*} が成り立つ.
(2)
(1) により ${}_k\mathrm C_r = {}_{k+1}\mathrm C_{r+1}-{}_k\mathrm C_{r+1}$ であるから, \begin{align*} \sum_{k = r}^n{}_k\mathrm C_r &= {}_r\mathrm C_r+({}_{r+2}\mathrm C_{r+1}-{}_{r+1}\mathrm C_{r+1})\\ &\qquad +\cdots +({}_{n+1}\mathrm C_{r+1}-{}_n\mathrm C_{r+1}) \\ &= {}_r\mathrm C_r-{}_{r+1}\mathrm C_{r+1}+{}_{n+1}\mathrm C_{r+1} \\ &= 1-1+{}_{n+1}\mathrm C_{r+1} \\ &= {}_{n+1}\mathrm C_{r+1} \end{align*} が成り立つ.

別解

(1)
特定の人物 A を含む $n+1$ 人から $r+1$ 人を選ぶ方法を考える.
(i)
A を選ぶとき. A 以外の $n$ 人から $r$ 人を選ぶ ${}_n\mathrm C_r$ 通りある.
(ii)
A を選ばないとき. A 以外の $n$ 人から $r+1$ 人を選ぶ ${}_n\mathrm C_{r+1}$ 通りある.
(i), (ii) は排反であるから, ${}_{n+1}\mathrm C_{r+1} = {}_n\mathrm C_r+{}_n\mathrm C_{r+1}$ が成り立つ.

背景

 (1) の等式 ${}_{n+1}\mathrm C_{r+1} = {}_n\mathrm C_r+{}_n\mathrm C_{r+1}$ は「パスカルの法則」と呼ばれ, 二項係数を下図のように並べると(パスカルの三角形), 各位置の数は左上の数と右上の数の和になることを表している.
 (2) の等式については, 例えば $n = 4,$ $r = 2$ の場合の ${}_4\mathrm C_2 = {}_1\mathrm C_1+{}_2\mathrm C_1+{}_3\mathrm C_1$ の各項に色をつけると, 下図のようになる.

問題≪正多角形の頂点を結ぶ三角形の個数≫

 $n$ を $3$ 以上の整数とする. 正 $n$ 角形 $\mathrm P_1\mathrm P_2\cdots\mathrm P_n$ の頂点を結ぶ次のような三角形の個数をそれぞれ求めよ.
(1)
任意の三角形.
(2)
二等辺三角形.
(3)
鋭角三角形.

解答例

(1)
正 $n$ 角形の $n$ 個の頂点のうち $3$ 点を選べば三角形ができるから, 求める個数は \[ {}_n\mathrm C_3 = \frac{n(n-1)(n-2)}{6}\] である.
(2)
(I)
$n = 2m$ ($m$: $2$ 以上の整数)のとき.
(i)
$n$ が偶数で $3$ の倍数でないとき. 正三角形は存在せず, $\mathrm P_1$ を頂点とする二等辺三角形は $m-1$ 個あるから, 二等辺三角形の個数は \[ n(m-1) = \frac{n(n-2)}{2}\] である.
(ii)
$n$ が $6$ の倍数であるとき. (i) の二等辺三角形の中に $3\cdot\dfrac{n}{3}$ 個の正三角形が含まれているから, 二等辺三角形の個数は, 余分に数えられている個数 $2\cdot\dfrac{n}{3}$ を引いた \[ \frac{n(n-2)}{2}-2\cdot\frac{n}{3} = \frac{n(3n-10)}{6}\] である.
(II)
$n = 2m+1$ ($m$: 正の整数)のとき.
(i)
$n$ が奇数で $3$ の倍数でないとき. 正三角形は存在せず, $\mathrm P_1$ を頂点とする二等辺三角形は $m$ 個あるから, 二等辺三角形の個数は \[ nm = \frac{n(n-1)}{2}\] である.
(ii)
$n$ が奇数で $3$ の倍数であるとき. (i) の二等辺三角形の中に $3\cdot\dfrac{n}{3}$ 個の正三角形が含まれているから, 二等辺三角形の個数は, 余分に数えられている個数 $2\cdot\dfrac{n}{3}$ を引いた \[ \frac{n(n-1)}{2}-2\cdot\frac{n}{3} = \frac{n(3n-7)}{6}\] である.
(3)
$n$ の偶奇で場合分けして, 直角三角形, 鈍角三角形の個数を求め, それから鋭角三角形の個数を導き出す.
(i)
$n = 2m$ ($m$: $2$ 以上の整数)のとき. $\triangle\mathrm P_1\mathrm P_k\mathrm P_l$ $(2 \leqq k < l \leqq n)$ において $\angle\mathrm P_1 = 90^\circ$ であるためには \[ l = k+m, \quad 2 \leqq k < l \leqq n\] つまり \[ 2 \leqq k \leqq m, \quad l = k+m \quad [1]\] であることが必要十分である. $[1]$ を満たす整数 $k,$ $l$ の個数は $m-1$ であるから, 直角三角形の個数は \[ n(m-1) = \frac{n(n-2)}{2}\] である.
また, $\triangle\mathrm P_1\mathrm P_k\mathrm P_l$ $(2 \leqq k < l \leqq n)$ において $\angle\mathrm P_1$ が鈍角であるためには, \[ l-k > \frac{n}{2}, \quad 2 \leqq k < l \leqq n \quad \cdots [2]\] の成り立つことが必要十分である. \[ [2] \iff 2 \leqq k < l-m \leqq m\] であり, これを満たす整数 $k,$ $l$ つまり $k,$ $l-m$ の個数は \[ {}_{m-1}\mathrm C_2 = \frac{(m-1)(m-2)}{2}\] であるから, 鈍角三角形の個数は \begin{align*} n\cdot\frac{(m-1)(m-2)}{2} = \frac{n(n-2)(n-4)}{8} \end{align*} である.
ゆえに, 鋭角三角形の個数は \begin{align*} &\frac{n(n\!-\!1)(n\!-\!2)}{6}\!-\!\frac{n(n\!-\!2)}{2}\!-\!\frac{n(n\!-\!2)(n\!-\!4)}{8} \\ &= \frac{n(n-2)(n-4)}{24} \end{align*} である.
(ii)
$n = 2m+1$ ($m$: 正の整数)のとき. 直角三角形の個数は $0$ である. また, (i) と同様に, $\triangle\mathrm P_1\mathrm P_k\mathrm P_l$ $(2 \leqq k < l \leqq n)$ において $\angle\mathrm P_1$ が鈍角であるためには $[2]$ つまり \[ 2 \leqq k < l-m \leqq m+1\] の成り立つことが必要十分であり, これを満たす整数 $k,$ $l$ つまり $k,$ $l-m$ の個数は \[ {}_m\mathrm C_2 = \frac{m(m-1)}{2}\] であるから, 鈍角三角形の個数は \begin{align*} n\cdot\frac{m(m-1)}{2} = \frac{n(n-1)(n-3)}{8} \end{align*} である. ゆえに, 鋭角三角形の個数は \begin{align*} &\frac{n(n-1)(n-2)}{6}-\frac{n(n-1)(n-3)}{8} \\ &= \frac{(n+1)n(n-1)}{24} \end{align*} である.

カタラン数

問題≪カタラン数≫

(1)
$xy$ 平面の原点を出発して, $x$ 軸方向に $1$ だけ進む, $y$ 軸方向に $1$ だけ進むのいずれかを繰り返して, 点 $(n,n)$ に至る経路において, 直線 $y = x$ をまたがないような場合の数 $C_n$ を求めたい. ここで, 直線 $y = x$ をまたぐような経路は, 初めて直線 $y = x$ をまたぐ点までの部分を直線 $y = x+1$ に関して折り返すことで, 点 $(-1,1)$ から点 $(n,n)$ に至る経路に対応づけることができる.
このことを利用して, \[ C_n = \frac{{}_{2n}\mathrm C_n}{n+1}\] であることを示せ.
(2)
数直線上の動点 $\mathrm P$ は, 原点 $\mathrm O$ を出発して, コインを投げて表が出る度に正の方向に $1$ だけ移動し, 裏が出る度に負の方向に $1$ だけ移動する. 横軸をコインを投げた回数 $t$ とした $\mathrm P$ の座標 $x$ の折れ線グラフを考えることによって, $2n$ 回コインを投げた時点で $\mathrm P$ が $\mathrm O$ に初めて戻る場合の数は $\dfrac{2{}_{2n-2}\mathrm C_{n-1}}{n}$ であることを示せ.

解答例

(1)
直線 $y = x$ をまたぐような経路の総数は ${}_{2n}\mathrm C_{n+1}$ である. また, 直線 $y = x$ をまたいでもまたがなくてもよいとしたときの経路の総数は ${}_{2n}\mathrm C_n$ であるから, \begin{align*} C_n &= {}_{2n}\mathrm C_n-{}_{2n}\mathrm C_{n+1} \\ &= \frac{(2n)!}{n!n!}-\frac{(2n)!}{(n+1)!(n-1)!} \\ &= \frac{(2n)!}{n!n!(n+1)}(n+1-n) \\ &= \frac{{}_{2n}\mathrm C_n}{n+1} \end{align*} である.
(2)
$1$ 回目に表が出て $t = 2n$ のときに初めて $x = 0$ となるとき, 動点 $\mathrm P$ の座標 $x$ の折れ線グラフは, $(0,0),$ $(1,1)$ を結ぶ線分, $(2n-1,1),$ $(2n,0)$ を結ぶ線分と, $2n-2$ 本の直線 $x = t-2k+2,$ $x = -t+2k-2$ $(1 \leqq k \leqq n-1)$ が走る碁盤目の $x \geqq 1$ の部分から成る.
その総数は (1) により \[ C_{n-1} = \frac{{}_{2n-2}\mathrm C_{n-1}}{n}\] であるから, 対称性により, 求める場合の数は \[ 2C_{n-1} = \frac{2{}_{2n-2}\mathrm C_{n-1}}{n}\] である.

背景

  • (1) の場合の数は「カタラン数」(Catalan number)と呼ばれる.
  • (2) の動点 $\mathrm P$ のように, 次に移動する位置が確率的に無作為に決まる運動を「ランダム・ウォーク」(random walk)と呼ぶ. コインを $2n$ 回投げ終えるまでに $\mathrm P$ が原点に戻る確率については, こちらを参照されたい.

組分け

問題≪組分け≫

 $n$ を正の整数とする. 次の各場合に, $n$ 個の玉を $3$ 個の箱に入れる方法の総数を求めよ. ただし, $1$ 個も玉の入らない箱があってもよいとする.
(A1)
玉が区別できて, 箱が A, B, C と区別されている場合.
(A2)
玉が区別できて, 箱は区別できない場合.
(B1)
玉は区別できず, 箱が A, B, C と区別されている場合.
(B2)
玉は区別できず, 箱も区別できない場合.

解答例

(A1)
$1$ 個の玉につき A, B, C のどの箱に入れるかで $3$ 通りの方法があるから, 全部で $3^n$ 通りの方法がある.
(A2)
求める場合の数を $N$ とおく.
(i)
$n$ 個の玉が $1$ つの箱に入る場合は, $1$ 通り.
この状態から箱に A, B, C と名前をつけると, 名前のつけ方は $3$ 通りあるから, (A1) の $3$ 通りが生じる.
(ii)
$n$ 個の玉が複数の箱に入る場合は, $N-1$ 通り.
このとき,玉の入った箱は入っている玉によって区別でき, 空箱は高々 $1$ 個で玉の入った箱と区別できるから, 箱はすべて区別できる. よって, この状態から箱に A, B, C と名前をつけると, 名前のつけ方は $3!$ 通りあるから, (A1) の $3!(N-1)$ 通りが生じる.
(i), (ii) と (A1) の結果により \[ 3+3!(N-1) = 3^n\] が成り立つから, \[ N = \frac{3^n+3}{3!} = \frac{3^{n-1}+1}{2}\] である.
(B1)
A, B, C の各箱に入る玉の個数を $a,$ $b,$ $c$ とおくと, \[ a+b+c = n, \quad a \geqq 0, \quad b \geqq 0, \quad c \geqq 0\] となり, $a,$ $b,$ $c$ はそれぞれ $n$ 個の〇と $2$ 本の|の順列において|で仕切られた〇の個数に対応するから, 全部で \[ {}_{n+2}\mathrm C_2 = \frac{(n+2)(n+1)}{2} \quad \cdots [1]\] 通りの方法がある.
(B2)
求める場合の数を $N$ とおく.
(I)
$n = 6m$ ($m$: 正の整数)の場合.
(i)
各箱に入る玉の個数がすべて等しい場合, 玉の個数の組合せは $\{ 2m,2m,2m\}$ の $1$ 通り.
この状態から箱に A, B, C と名前をつけると, 名前のつけ方は $1$ 通りあるから, (B1) の $1$ 通りが生じる.
(ii)
各箱に入る玉の個数が $2$ 箱だけ等しい場合, 玉の個数の組合せは $\{ 0,0,6m\},$ $\cdots,$ $\{ 3m,3m,0\}$ から (i) の場合を除いた $3m$ 通り.
この状態から箱に A, B, C と名前をつけると, 名前のつけ方は $\dfrac{3!}{2!} = 3$ 通りあるから, (B1) の $3\cdot 3m$ 通りが生じる.
(iii)
各箱に入る玉の個数がすべて異なる場合は, $N-3m-1$ 通り.
この状態から箱に A, B, C と名前をつけると, 名前のつけ方は $3!$ 通りあるから, (B1) の $3!(N-3m-1)$ 通りが生じる.
(i)~(iii) から (B1) の場合の数は \begin{align*} &1+3\cdot 3m+3!(N-3m-1) \\ &= 6N-9m-5 = 6N-\frac{3n+10}{2} \quad \cdots [2] \end{align*} と表せるので, $[1] = [2]$ を $N$ について解くと \[ N = \frac{n^2+6n+12}{12}\] が得られる.
(II)
$n = 6m+1$ ($m$: 正の整数)の場合. (I) と同様に考えて (B1) の場合の数は \begin{align*} &0+3(3m+1)+3!(N-3m-1) \\ &= 6N-9m-3 = 6N-\frac{3(n+1)}{2} \end{align*} と表せるから, \[ N = \frac{(n+1)(n+5)}{12}\] である.
(III)
$n = 6m+2$ ($m$: 正の整数)の場合. (I) と同様に考えて (B1) の場合の数は \begin{align*} &0+3(3m+2)+3!(N-3m-2) \\ &= 6N-9m-6 = 6N-\frac{3(n+2)}{2} \end{align*} と表せるから, \[ N = \frac{(n+2)(n+4)}{12}\] である.
(IV)
$n = 6m+3$ ($m$: 正の整数)の場合. (I) と同様に考えて (B1) の場合の数は \begin{align*} &1+3(3m+1)+3!(N-3m-2) \\ &= 6N-9m-8 = 6N-\frac{3n+7}{2} \end{align*} と表せるから, \[ N = \frac{(n+3)^2}{12}\] である.
(V)
$n = 6m+4$ ($m$: 正の整数)の場合. (I) と同様に考えて (B1) の場合の数は \begin{align*} &0+3(3m+3)+3!(N-3m-3) \\ &= 6N-9m-9 = 6N-\frac{3(n+2)}{2} \end{align*} と表せるから, \[ N = \frac{(n+2)(n+4)}{12}\] である.
(VI)
$n = 6m+5$ ($m$: 正の整数)の場合. (I) と同様に考えて (B1) の場合の数は \begin{align*} &0+3(3m+3)+3!(N-3m-3) \\ &= 6N-9m-9 = 6N-\frac{3(n+1)}{2} \end{align*} と表せるから, \[ N = \frac{(n+1)(n+5)}{12}\] である.