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: 組合せを利用

(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}$ が成り立つ.
(2)
$n+1$ 人 A${}_1,$ $\cdots,$ A${}_n,$ A${}_{n+1}$ から $r+1$ 人を選ぶ方法の総数は, ${}_{n+1}\mathrm C_{r+1}$ である.
このうち, A${}_1,$ $\cdots,$ A${}_{j-1}$ $(1 \leqq j \leqq n-r+1)$ を選ばず, A${}_j$ を選ぶ方法の総数は, A${}_{j+1},$ $\cdots,$ A${}_{n+1}$ から $r$ 人を選ぶ方法の総数に等しく, ${}_{n+1-j}\mathrm C_r$ である. これを $j$ の値を変えながら足しあわせると, \[ {}_{n+1}\mathrm C_{r+1} = \sum_{j = 1}^{n-r+1}{}_{n+1-j}\mathrm C_r = \sum_{k = r}^n{}_k\mathrm C_r\] が得られる.

別解 2: 二項定理(数学 II)を利用

(1)
\[ (1+x)^{n+1} = (1+x)^n+x(1+x)^n\] において, 左辺の展開式で $r+1$ 次の項は ${}_{n+1}\mathrm C_{r+1}x^{r+1}$ であり, 右辺の展開式で $r+1$ 次の項は \[ {}_n\mathrm C_{r+1}x^{r+1}+x\cdot {}_n\mathrm C_rx^r = ({}_n\mathrm C_r+{}_n\mathrm C_{r+1})x^{r+1}\] だから, 係数を比較すると ${}_{n+1}\mathrm C_{r+1} = {}_n\mathrm C_r+{}_n\mathrm C_{r+1}$ が得られる.

別解 3: 数学的帰納法

(2)
(i)
${}_1\mathrm C_1 = {}_2\mathrm C_2 = 1$ から, $n = 1$ のとき等式が成り立つ.
(ii)
$n = m$ ($m$: 正の整数)のとき等式が成り立つとすると, \begin{align*} \sum_{k = r}^{m+1}{}_k\mathrm C_r &= \sum_{k = r}^m{}_k\mathrm C_r+{}_{m+1}\mathrm C_r \\ &= {}_{m+1}\mathrm C_{r+1}+{}_{m+1}\mathrm C_r \\ &= {}_{m+2}\mathrm C_{r+1} \quad (\because (1)) \end{align*} となるから, $n = m+1$ のとき等式が成り立つ.
(i), (ii) から, すべての正の整数 $n$ に対して求める等式が成り立つ.

背景

  • (1) の等式 ${}_{n+1}\mathrm C_{r+1} = {}_n\mathrm C_r+{}_n\mathrm C_{r+1}$ は「パスカルの法則」(Pascal's rule)と呼ばれ, 二項係数を下図のように並べると(パスカルの三角形), 各位置の数は左上の数と右上の数の和になることを表している.
  • (2) の等式については, 例えば $n = 3,$ $r = 1$ の場合の ${}_4\mathrm C_2 = {}_1\mathrm C_1+{}_2\mathrm C_1+{}_3\mathrm C_1$ の各項に色をつけると, 下図のようになる. このことから, 等式 $\displaystyle\sum\limits_{k = r}^n{}_k\mathrm C_r = {}_{n+1}\mathrm C_{r+1}$ はしばしば「ホッケースティック恒等式」(hockey-stick identity)と呼ばれる.

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

 $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$ が原点に戻る確率については, こちらを参照されたい.