COMPASS

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

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

場合の数

教科書の補足

組合せ

定理≪$r!$ は ${}_n\mathrm P_r$ を割り切る≫

 $1 \leqq r \leqq n$ なる整数 $n,$ $r$ に対して, $r!$ は ${}_n\mathrm P_r$ を割り切る.

証明: 二重帰納法で示す

 $r$ に関する帰納法で示す.
(I)
$1! = 1$ は ${}_n\mathrm P_1 = n$ を割り切るので, $r = 1$ のとき成り立つ.
(II)
$r > 1$ とし, $r$ を $r-1$ に置き換えた命題が成り立つとして, $r$ に対する命題を $n$ に関する帰納法で示す.
(i)
$n = 1$ のとき, $r = 1$ であるから, $r! = 1$ は ${}_n\mathrm P_r = 1$ を割り切る.
(ii)
$n > 1$ として, $n$ を $n-1$ に置き換えた命題が成り立つとすると, \begin{align*} {}_n\mathrm P_r &= n(n-1)\cdots (n-r+1) \\ &= (n-r+r)(n-1)\cdots (n-r+1) \\ &= (n-1)\cdots (n-r+1)(n-r) \\ &\qquad +r(n-1)\cdots (n-r+1) \\ &= {}_{n-1}\mathrm P_r+r{}_{n-1}\mathrm P_{r-1} \end{align*} の右辺は $r! = r\cdot (r-1)!$ で割り切れるから, 左辺 ${}_n\mathrm P_r$ は $r!$ で割り切れる.
(i), (ii) から, 上記の $r$ について, すべての $n$ に対して命題が成り立つ.
(I), (II) から, すべて $r,$ $n$ に対して命題が成り立つ.

問題

場合の数の基本

問題≪個数定理とド・モルガンの法則≫

 $100$ 人にアンケートをとったところ, 和食が好きな人は $50$ 人, 洋食が好きな人は $30$ 人, 和食も洋食も好きな人は $10$ 人であった.
(1)
和食または洋食が好きな人の数を求めよ.
(2)
和食も洋食も嫌いな人の数を求めよ.

解答例

 アンケートをとった人全体の集合を $U,$ 和食な人が好きな人の集合を $A,$ 洋食が好きな人の集合を $B$ とおく.
(1)
求める人数は, \begin{align*} n(A\cup B) &= n(A)+n(B)-n(A\cap B) \\ &= 50+30-10 \\ &= 70. \end{align*}
(2)
求める人数は, \begin{align*} n(\bar A\cap\bar B) &= n(\overline{A\cup B}) \\ &= n(U)-n(A\cup B) \\ &= 100-70 \quad (\because (1)) \\ &= 30. \end{align*}

問題≪個数定理の拡張≫

 有限集合 $S$ の要素の個数を $n(S)$ で表す. 有限集合 $U$ の部分集合 $A,$ $B,$ $C$ に対して, 次の等式が成り立つことを示せ.
(1)
\begin{align*} &n(A\cup B\cup C) \!=\! n(A)\!+\!n(B)\!+\!n(C) \\ &\!-\!n(A\cap B)\!-\!n(B\cap C)\!-\!n(C\cap A)\!+\!n(A\cap B\cap C). \end{align*}
(2)
\begin{align*} &n(A\cap B\cap C) \!=\! n(A)\!+\!n(B)\!+\!n(C) \\ &\!-\!n(A\cup B)\!-\!n(B\cup C)\!-\!n(C\cup A)\!+\!n(A\cup B\cup C). \end{align*}

解答例

(1)
\begin{align*} &n(A\cup B\cup C) = n\big( (A\cup B)\cup C\big) \\ &= n(A\cup B)+n(C)-n\big( (A\cup B)\cap C\big) \\ &= n(A)+n(B)-n(A\cap B)+n(C) \\ &\quad -n\big( (B\cap C)\cup (C\cap A)\big) \\ &= n(A)+n(B)+n(C)-n(A\cap B) \\ &\quad -n(B\cap C)-n(C\cap A)+n(A\cap B\cap C) \\ &\qquad\qquad\quad \big(\because (B\cap C)\cap (C\cap A) = A\cap B\cap C\big). \end{align*}
(2)
\begin{align*} &n(A\cap B\cap C) = n(\bar{\bar A}\cap\bar{\bar B}\cap\bar{\bar C}) = n(\overline{\bar A\cup\bar B\cup\bar C}) \\ &= n(U)-n(\bar A\cup\bar B\cup\bar C) \\ &= n(U)\!-\!n(\bar A)\!-\!n(\bar B)\!-\!n(\bar C) \\ &\quad +\!n(\bar A\!\cap\!\bar B)\!+\!n(\bar B\!\cap\!\bar C)\!+\!n(\bar C\!\cap\!\bar A)\!-\!n(\bar A\!\cap\!\bar B\!\cap\!\bar C) \\ &= n(U)\!-\!n(\bar A)\!-\!n(\bar B)\!-\!n(\bar C) \\ &\quad +\!n(\overline{A\!\cup\!B})\!+\!n(\overline{B\!\cup\!C})\!+\!n(\overline{C\!\cup\!A})\!-\!n(\overline{A\!\cup\!B\!\cup\!C}) \\ &= n(U)\!-\!n(U)\!+\!n(A)\!-\!n(U)\!+\!n(B)\!-\!n(U)\!+\!n(C) \\ &\quad +\!n(U)\!-\!n(A\!\cup\!B)\!+\!n(U)\!-\!n(B\!\cup\!C) \\ &\quad +\!n(U)\!-\!n(C\!\cup\!A)\!-\!n(U)\!+\!n(A\!\cup\!B\!\cup\!C) \\ &= n(A)\!+\!n(B)\!+\!n(C) \\ &\quad -\!n(A\!\cup\!B)\!-\!n(B\!\cup\!C)\!-\!n(C\!\cup\!A)\!+\!n(A\!\cup\!B\!\cup\!C). \end{align*}

問題≪支払える金額の総数≫

 $100$ 円玉 $4$ 枚, $50$ 円玉 $5$ 枚, $10$ 円玉 $6$ 枚を使ってお釣りのないように支払うことのできる金額は何通りあるか.

解答例

 $10$ 円玉を $1$ 枚だけ残し, 残りの $5$ 枚を $50$ 円玉 $1$ 枚に両替すると, $100$ 円玉 $4$ 枚, $50$ 円玉 $6$ 枚, $10$ 円玉 $1$ 枚になる. さらに, $50$ 円玉を $2$ 枚だけ残し, 残りの $4$ 枚を $100$ 円玉 $2$ 枚に両替すると, $100$ 円玉 $6$ 枚, $50$ 円玉 $2$ 枚, $10$ 円玉 $1$ 枚になる. このようにしても, 支払える金額は変化しない.
$50$ 円玉を出す枚数によって次の場合がある:
(i)
$50$ 円玉を出さない.
(ii)
$50$ 円玉を $1$ 枚だけ出す.
(iii)
$50$ 円玉を $2$ 枚出す.
この各場合に, $100$ 円玉, $10$ 円玉の出し方の総数は, \[ (6+1)\cdot (1+1) = 14.\] (i) と (ii), および (ii) と (iii) で支払える金額で重複するものはない.
$50$ 円玉 $2$ 枚は $100$ 円玉 $1$ 枚の価値があるから, (i) と (iii) で金額が重複するのは, (i) において $100$ 円玉を $1$ 枚以上出す場合と (iii) で $100$ 円玉を $5$ 枚以下出す場合の $5$ 通りである.
よって, 硬貨の出し方の総数は, \[ 3\cdot 14-5 = 37.\] これから硬貨を $1$ 枚も出さない場合を除いて, 支払える金額の総数は \[ 37-1 = 36.\]

順列

問題≪順列の漸化式≫

 $0 \leqq r \leqq n$ なる任意の整数 $n,$ $r$ に対して, 次の公式が成り立つことを示せ. \[ (r+1){}_n\mathrm P_r+{}_n\mathrm P_{r+1} = {}_{n+1}\mathrm P_{r+1}.\]

解答例

\begin{align*} &(r+1){}_n\mathrm P_r+{}_n\mathrm P_{r+1} = (r+1)\frac{n!}{(n-r)!}+\frac{n!}{(n-r-1)!} \\ &= (r+1+n-r)\frac{n!}{(n-r)!} = \frac{(n+1)!}{(n-r)!} \\ &= \frac{(n+1)!}{(n+1-r-1)!} = {}_{n+1}\mathrm P_{r+1}. \end{align*}

別解

 $n+1$ 人のうち $r+1$ 人を並べる順列を考える. $n+1$ 人の中に含まれる特定の人物 A を選ぶか選ばないかで場合分けして数える.
(i)
A を選ぶ場合. A が何番目に並ぶかを決めた後, 残りの $n$ 人のうち $r$ 人を他の場所に並べる $(r+1){}_n\mathrm P_r$ 通りの並べ方がある.
(ii)
A を選ばない場合. 残りの $n$ 人のうち $r+1$ 人を並べる ${}_n\mathrm P_{r+1}$ 通りの並べ方がある.
(i), (ii) は排反だから, \[ {}_{n+1}\mathrm P_{r+1} = (r+1){}_n\mathrm P_r+{}_n\mathrm P_{r+1}.\]

問題≪条件付き順列≫

 男子 $3$ 人, 女子 $3$ 人の計 $6$ 人が一列に並ぶとき, 次の場合の数を求めよ.
(a)
特定の男子 A と女子 B が隣り合う.
(b)
男子 $3$ 人が隣り合う.
(c)
男子と女子が交互に並ぶ.

解答例

(a)
A と B の $2$ 人組を $1$ つのものと考えると, $5!$ 通り.
その各々について, A, B の並び方が $2!$ 通り.
よって, A, B が隣り合う並び方は, $5!\times 2! = 240$ 通り.
(b)
男子 $3$ 人組を $1$ つのものと考えると, $4!$ 通り.
その各々について, 男子の並び方が $3!$ 通り.
よって, 男子 $3$ 人が隣り合う並び方は, $4!\times 3! = 144$ 通り.
(c)
男女どちらが先頭になるかで $2$ 通り.
その各々について, 男子の並び方が $3!$ 通り.
その各々について, 女子の並び方が $3!$ 通り.
よって, 男女が交互に並ぶ並び方は, $2\times 3!\times 3! = 72$ 通り.

問題≪$0$ を含む順列≫

 数字 $0,$ $1,$ $2,$ $3,$ $4,$ $5$ から異なる $4$ 個の数字使ってできる $4$ 桁の偶数の総数を求めよ.

解答例

(i)
一の位が $0$ であるとき.
千, 百, 十の位は $0$ 以外の $5$ 個から $3$ 個を取って並べる順列で ${}_5\mathrm P_3$ 通り.
(ii)
一の位が $2,$ $4$ のとき. 一の位の選び方が $2$ 通り.
その各々について, 千の位は $0$ を除く残り $4$ 個から $1$ 個を取る $4$ 通り.
百, 十の位は残り $4$ 個から $2$ 個を取って並べる順列で ${}_4\mathrm P_2$ 通り.
ゆえに, 求める個数は, \[ {}_5\mathrm P_3+2\times 4\times {}_4\mathrm P_2 = 10+96 = 106.\]

問題≪文字列の並び替えの総数≫

(a)
STUDY の $5$ 文字を並び替えてできる文字列の総数を求めよ.
(b)
MATHEMATICS の $11$ 文字を並び替えてできる文字列の総数を求めよ.

解答例

(a)
\[ 5! = 5\cdot 4\cdot 3\cdot 2\cdot 1 = 120.\]
(b)
$2$ 個の A, M, T をすべて異なるものとして, $11$ 文字 A, A', M, M', T, T', C, E, H, I, S の順列を考えると, 全部で $11!$ 通り.
A = A' とすると, 同じものが $2!$ 通り.
M = M' とすると, 同じものが $2!$ 通り.
T = T' とすると, 同じものが $2!$ 通り.
ゆえに, 求める文字列の総数は, \[\frac{11!}{2!2!2!} = 11\cdot 10\cdot 9\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2 = 4989600.\]

(b) の別解

まず A $2$ 個の位置を決めると, ${}_{11}\mathrm C_2$ 通り.
次に M $2$ 個の位置を決めると, ${}_9\mathrm C_2$ 通り.
さらに T $2$ 個の位置を決めると, ${}_7\mathrm C_2$ 通り.
最後に残りの文字の位置を決めると, $7!$ 通り.
ゆえに, 求める文字列の総数は, \[ {}_{11}\mathrm C_2\times {}_9\mathrm C_2\times {}_7\mathrm C_2\times 7! = \frac{11!}{2!2!2!} = 4989600.\]

問題≪非隣接順列≫

 次の文字を $1$ 列に並べるとき, 同じ文字が隣り合わないような並べ方は何通りあるか.
(a)
P, R, O, O, F の $5$ 文字.
(b)
C, O, M, P, U, T, A, T, I, O, N の $11$ 文字.

解答例

(a)
P, R, O, O, F の $5$ 文字の並べ方は, $5!/2!$ 通り.
このうち, O, O が隣り合うような並べ方は, OO を $1$ つの文字と考えて, $4!$ 通り.
ゆえに, O, O が隣り合わないような並べ方は, \[\frac{5!}{2!}-4! = \frac{5\cdot 4}{2}\cdot 3!-4\cdot 3! = (10-4)3! = 36.\]
(b)
C, O, M, P, U, T, A, T, I, O, N の $11$ 文字の並べ方は, $11!/2!2!$ 通り.
このうち, O, O が隣り合うような並べ方は, OO を $1$ つの文字と考えて, $10!/2!$ 通り.
同様に, T, T が隣り合うような並べ方は, $10!/2!$ 通り.
O, O が隣り合い, T, T も隣り合うような並べ方は, OO, TT をそれぞれ $1$ つの文字と考えて, $9!$ 通り.
ゆえに, 同じ文字が隣り合わないような並べ方の総数は, \begin{align*} &\frac{11!}{2!2!}-\frac{10!}{2!}-\frac{10!}{2!}+9! \\ &= \frac{11\cdot 10\cdot 9\cdot 8}{4}\cdot 7!-2\cdot\frac{10\cdot 9\cdot 8}{2}\cdot 7!+9! \\ &= (1980-720+72)7! = 1332\cdot 5040 = 6713280. \end{align*}

別解

(a)
P, R, F の $3$ 文字を並べて, その文字の間と両端の $4$ か所のいずれかに O, O を入れると考ると, O, O が隣り合わないような並べ方の総数は \[ 3!\cdot {}_4\mathrm C_2 = 36.\]
(b)
同じ文字は O, O と T, T である. まず, T, T 以外の $9$ 文字を並べる.
(i)
O, O が隣り合うとき. その並べ方は, OO を $1$ つと見て
$8! = 40320$ 通り.
さらに, O と O の間に T を入れ OTO を $1$ つと見て, C, OTO, M, P, U, A, I, N の $8$ 文字の間と両端の $9$ か所のいずれかに残りの T を入れると考えると,
$40320\cdot 9 = 362880$ 通り.
(ii)
O, O が隣り合わないとき. その並べ方は, C, M, P, U, A, I, N の $7$ 文字の間と両端の $8$ か所のいずれかに O, O を入れると考えて
$7!\cdot {}_8\mathrm C_2 = 141120$ 通り.
さらに, この $9$ 文字の間と両端の $10$ か所のいずれかに T, T を入れると考えて,
$141120\cdot {}_{10}\mathrm C_2 = 6350400$ 通り.
(i), (ii) から, 同じ文字が隣り合わないような並べ方の総数は, \[ 362880+6350400 = 6713280.\]

問題≪数珠順列≫

 赤 $4$ 個, 黄 $3$ 個, 青 $2$ 個, 白 $1$ 個, 計 $10$ 個のビーズをつないでブレスレットを作る.
(1)
作り方の総数を求めよ.
(2)
青 $2$ 個が隣り合うような作り方の総数を求めよ.
ただし, 同色の玉は区別しないものとする.

解答例

(1)
白 $1$ 個を固定すると, 残りの $9$ 個を円形に並べる方法の総数は, \[\frac{9!}{4!3!2!} = 1260.\] このうち左右対称であるのは, 白の向かいに黄 $1$ 個を配置する場合に限り, 残りの赤 $2$ 個, 黄 $1$ 個, 青 $1$ 個, 計 $4$ 個の $2$ 組がその間に向かい合って並ぶ. これら \[\frac{4!}{2!} = 12\] 通りは裏返しても配置が変わらず, その他は裏返すと同じ配置になるものが $2$ 通りずつある. ゆえに, 求める場合の数は, \[ 12+\frac{1260-12}{2} = 636.\]
(2)
白 $1$ 個を固定して青 $2$ 個が隣り合うように円形に並べる方法の総数は, 赤 $4$ 個, 黄 $3$ 個, 青 $1$ 個, 計 $8$ 個を円形に並べる方法の総数に等しく, \[\frac{8!}{4!3!} = 280.\] (1) の議論より, このうち左右対称なものは存在せず, 裏返すと同じ配置になるものが $2$ 通りずつある. ゆえに, 求める場合の数は, \[\frac{280}{2} = 140.\]

補足

 どの色も互いに隣り合わないような作り方の総数はいくつか. これは, かなり場合分けが複雑だが, 実用的な問題である. 興味のある方はチャレンジされたい.

組合せ

問題≪二項係数の漸化式≫

 $0 \leqq r \leqq n$ なる任意の整数 $n,$ $r$ に対して, 次の公式が成り立つことを示せ. \[ {}_n\mathrm C_r+{}_n\mathrm C_{r+1} = {}_{n+1}\mathrm C_{r+1}.\]

解答例

 二項係数の定義により, \begin{align*} &{}_n\mathrm C_r+{}_n\mathrm C_{r+1} \\ &= \frac{n!}{r!(n-r)!}+\frac{n!}{(r+1)!(n-r-1)!} \\ &= n!\frac{(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*}

別解

 $n+1$ 人から $r+1$ 人を選ぶ組合せを考える. $n+1$ 人の中に含まれる特定の人物 A を選ぶか選ばないかで場合分けして数える.
(i)
A を選ぶ場合. 残りの $n$ 人から $r$ 人を選ぶ ${}_n\mathrm C_r$ 通りの組合せがある.
(ii)
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}.\]

問題≪ファンデルモンドの畳み込み≫

 $m,$ $n$ を正整数とし, $r$ を $0 \leqq r \leqq m+n$ なる整数とする. 次の公式が成り立つことを示せ. \[\sum\limits_{k = 0}^r{}_m\mathrm C_k\cdot {}_n\mathrm C_{r-k} = {}_{m+n}\mathrm C_r.\]

解答例

 男子 $m$ 人, 女子 $n$ 人の合計 $m+n$ 人から $r$ 人を選ぶ組合せを考える. 男子 $m$ 人から何人を選ぶかで場合分けして数える. 男子 $m$ 人から $k$ 人を選ぶとき, 女子からは $r-k$ 人を選ぶことになるから, 全部で ${}_m\mathrm C_k\cdot {}_n\mathrm C_{r-k}$ 通りの組み合わせがある. 異なる整数 $k$ の値について, これらは排反だから, \[ {}_{m+n}\mathrm C_r = \sum\limits_{k = 0}^r{}_m\mathrm C_k\cdot {}_n\mathrm C_{r-k}\]

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

 $n$ を $3$ 以上の整数とする. 正 $n$ 角形の $3$ 頂点を結んでできる次の図形の個数をそれぞれ求めよ:
(a1)
三角形.
(a2)
直角三角形.
(a3)
鋭角三角形.
(a4)
鈍角三角形.
(b1)
正三角形.
(b2)
二等辺三角形.
ただし, 回転による同一視はせずに数えよ.

解答例

(a1)
正 $n$ 角形の頂点を結ぶ三角形の個数は, $n$ 個の頂点から $3$ 個を選ぶ方法の総数に等しく, \[ {}_n\mathrm C_3 = \frac{n(n-1)(n-2)}{6}.\]
(a2)
正 $n$ 角形の $3$ 頂点を結んで直角三角形ができるとき, その斜辺は外接円の直径となる.
(i)
$n$ が奇数のとき. 与えられた頂点を通る外接円の直径は対辺の中点を通るから, $3$ 頂点を結ぶ直角三角形の個数は $0.$
(ii)
$n$ が偶数のとき. 与えられた頂点を通る外接円の直径は対角の頂点を通る. 斜辺の選び方が $\dfrac{n}{2}$ 通りあり, その各々に対して直角の選び方が $n-2$ 通りあるから, $3$ 頂点を結ぶ直角三角形の個数は $\dfrac{n(n-2)}{2}.$
(a3)
(i)
$n$ が奇数のとき. $n = 2m+1$ とおく. まず, 正 $n$ 角形 $\mathrm A_1\cdots\mathrm A_n$ において頂点 $\mathrm A_1$ と他の $2$ 頂点を結ぶ鋭角三角形を数える.
$2 \leqq k \leqq m+1$ のとき, $\angle\mathrm A_1,$ $\angle\mathrm A_k$ の二等分線と外接円の交点をそれぞれ $\mathrm B_1,$ $\mathrm B_k$ とおくと, $\triangle\mathrm A_1\mathrm A_k\mathrm B_1,$ $\triangle\mathrm A_1\mathrm A_k\mathrm B_k$ は直角三角形だから, 外接円の弧 $\mathrm B_1\mathrm B_k$ 上に頂点を持つ $\triangle\mathrm A_1\mathrm A_k\mathrm A_\ell$ ($m+1 < \ell < m+k+1$)は鋭角三角形なので, $\mathrm A_1,$ $\mathrm A_k$ と他の頂点を結ぶ鋭角三角形の個数は $k.$
よって, 頂点 $\mathrm A_1$ と他の $2$ 頂点を結ぶ鋭角三角形の個数は, \begin{align*} \sum\limits_{k = 2}^{m+1}k &= \sum\limits_{k = 1}^m(k+1) = \frac{m(m+1)}{2}+m \\ &= \frac{(n-1)(n+5)}{8}. \end{align*} これらの鋭角三角形を $\dfrac{n}{360}^\circ$ ずつ $n$ 回回転させると, この $n$ 倍個の三角形の中に同じ三角形が $3$ 個ずつ現れるから, 求める個数は \[ n\times\frac{(n-1)(n+5)}{8}\div 3 = \frac{n(n-1)(n+5)}{24}.\]
(ii)
$n$ が偶数のとき. $n = 2m$ とおく. まず, 正 $n$ 角形 $\mathrm A_1\cdots\mathrm A_n$ において頂点 $\mathrm A_1$ と他の $2$ 頂点を結ぶ鋭角三角形を数える.
$\mathrm A_1,$ $\mathrm A_2$ と他の頂点を結ぶ鋭角三角形は存在しない.
$3 \leqq k \leqq m$ のとき, $\triangle\mathrm A_1\mathrm A_k\mathrm A_{m+1},$ $\triangle\mathrm A_1\mathrm A_k\mathrm A_{m+k}$ は直角三角形だから, 外接円の弧 $\mathrm A_{m+1}\mathrm A_{m+k}$ 上に頂点を持つ $\triangle\mathrm A_1\mathrm A_k\mathrm A_\ell$ ($m+1 < \ell < m+k$)は鋭角三角形なので, $\mathrm A_1,$ $\mathrm A_k$ と他の頂点を結ぶ鋭角三角形の個数は $k-2.$
よって, 頂点 $\mathrm A_1$ と他の $2$ 頂点を結ぶ鋭角三角形の個数は, \begin{align*} \sum\limits_{k = 2}^m(k-2) &= \sum\limits_{k = 1}^{m-1}(k-1) = \frac{1}{2}(m-1)m \\ &= \frac{n(n-2)}{2}. \end{align*} これらの鋭角三角形を $\dfrac{n}{360}^\circ$ ずつ $n$ 回回転させると, この $n$ 倍個の三角形の中に同じ三角形が $3$ 個ずつ現れるから, 求める個数は \[ n\times\frac{n(n-2)}{2}\div 3 = \frac{n^2(n-2)}{6}.\]
(a4)
(a1)~(a3) より, 正 $n$ 角形の頂点を結ぶ鈍角三角形の個数は,
(i)
$n$ が奇数のとき, \begin{align*} &\frac{n(n-1)(n-2)}{3}-\frac{n(n-1)(n+5)}{24} \\ &= \frac{7n(n-1)(n-3)}{24}. \end{align*}
(ii)
$n$ が偶数のとき, \begin{align*} &\frac{n(n-1)(n-2)}{3}-\frac{n^2(n-2)}{6}-\frac{n(n-2)}{2} \\ &= \frac{n(n-2)(n-5)}{6}. \end{align*}
(b1)
正 $n$ 角形の頂点を結ぶ正三角形の個数は,
(I)
$n$ が $3$ の倍数のとき $\dfrac{n}{3},$
(II)
$n$ が $3$ の倍数でないとき $0.$
(b2)
$2$ 以上のある整数 $m$ に対して, $n = 2m-1$ または $n = 2m$ と書ける.
$\mathrm A$ を $1$ つの頂点とする. $\mathrm{AP} = \mathrm{AQ}$ を満たす頂点 $\mathrm P,$ $\mathrm Q$ は $\angle\mathrm A$ の二等分線について対称だから, このような二等辺三角形 $\mathrm{APQ}$ の個数は \[ m-1 = \left\{\begin{array}{l} \dfrac{n+1}{2}-1 = \dfrac{n-1}{2} & (n = 2m-1), \\ \dfrac{n}{2}-1 = \dfrac{n-2}{2} & (n = 2m). \end{array}\right.\]
点 $\mathrm A$ を任意の頂点に置き換えて得られる $n(m-1)$ 個の二等辺三角形の中には同じ正三角形が $3$ 個ずつある.
ゆえに, 正 $n$ 角形の頂点を結ぶ二等辺三角形の個数は,
(i)
$n$ が奇数で $3$ の倍数のとき $\dfrac{n(n-1)}{2}-\dfrac{2n}{3} = \dfrac{n(3n-7)}{6},$
(ii)
$n$ が偶数で $3$ の倍数でないとき $\dfrac{n(n-2)}{2},$
(iii)
$n$ が奇数で $3$ の倍数でないとき $\dfrac{n(n-1)}{2},$
(iv)
$n$ が $6$ の倍数のとき $\dfrac{n(n-2)}{2}-\dfrac{2n}{3} = \dfrac{n(3n-10)}{6}.$

補足

 鋭角三角形, 鈍角三角形についても考察されたい. また, 回転による同一視をする場合にはどうなるか.

問題≪立方体の配色≫

(1)
与えられた $6$ 色を使って, 立方体の面を $1$ 色ずつ $6$ 色以下で塗り分ける方法の総数を求めよ.
(2)
また, 隣り合う面に異なる色を塗る場合にはどうなるか.

解答例

(1)
各面の塗り方が $6$ 通りあるから, 塗り方の総数は \[ 6^6 = 46656.\]
(2)
ちょうど $n$ 色で隣り合う面に異なる色を塗る方法を考える. 立方体の $1$ 頂点に集まる面の数は $3$ だから, $n \geqq 3$ が必要である. 向かい合う面にしか同じ色を塗れないことに注意しておく.
(i)
$n = 6$ のとき. 使う色の決め方は ${}_6\mathrm C_6 = 1$ 通り.
上面の色を決めると, 下面の塗り方は $5$ 通り, 側面の塗り方は $4!$ 通りで, 回転方法は正面の色を決める $4$ 通り.
よって, $n = 6$ のときの塗り方の総数は, \[\frac{1\cdot 5\cdot 4!}{4} = 30.\]
(ii)
$n = 5$ のとき. 使う色の決め方は ${}_6\mathrm C_5 = 6$ 通り, $2$ つの面に塗られる色の決め方は ${}_5\mathrm C_1 = 5$ 通り.
上下面を $1$ 色で塗ると決めると, 側面の塗り方は $4!$ 通りで, 回転方法は側面の回転と上下の反転を考慮して $4\cdot 2$ 通り.
よって, $n = 5$ のときの塗り方の総数は, \[\frac{6\cdot 5\cdot 4!}{4\cdot 2} = 90.\]
(iii)
$n = 4$ のとき. 使う色の決め方は ${}_6\mathrm C_4$ 通り, $2$ つの面に塗られる色の決め方は ${}_4\mathrm C_2$ 通り.
側面を $2$ 色で塗って正面の色を決めると, 上下面の塗り方は $2!$ 通りで, 回転方法は $2$ 通り.
よって, $n = 4$ のときの塗り方の総数は, \[\frac{{}_6\mathrm C_4\cdot {}_4\mathrm C_2\cdot 2!}{2} = 90.\]
(iv)
$n = 3$ のとき. 使う色の決め方は ${}_6\mathrm C_3$ 通り.
上下面の色を決めると, 側面の塗り方は $2!$ 通りで, 回転方法は $2$ 通り.
よって, $n = 3$ のときの塗り方の総数は, \[\frac{{}_6\mathrm C_3\cdot 2!}{2} = 20.\]
(i)~(iv) は排反だから, 後者の塗り方の総数は, \[ 30+90+90+20 = 230.\]

解説

 解答例のように使う色と上下面の色を指定して回転まで考慮すると, (i) の側面の塗り方は円順列, (ii) の側面の塗り方は数珠順列になる.

重複組合せ

問題≪重複組合せ≫

 $15$ 個のみかんを A, B, C の $3$ 人に配る.
(1)
配り方の総数を求めよ.
(2)
A より B に多く配る方法の総数を求めよ.
ただし, 全員少なくとも $1$ 個は受け取るとする.

解答例

 A, B, C に配るみかんの個数をそれぞれ $a,$ $b,$ $c,$ とおく.
(1)
A, B, C に $1$ こずつみかんを配ると, $12$ 個残る. この $12$ 個と仕切り $2$ つを横 $1$ 列に並べ, 左の仕切りより左側にあるみかんを A に, 左右の仕切りの間にあるみかんを B に, 右の仕切りより右側にあるみかんを C に配れば, 残りのみかんの配り方が決まる. よって, 配り方の総数は, \[ _{12+2}\mathrm C_2 = \frac{14\cdot 13}{2\cdot 1} = 91.\]
(2)
$15$ 個のみかんを A, B, C に配って A と B が同数になるのは, $a+b+c = 2a+c = 15$ より $1 \leqq a \leqq 7$ のときに限るから, 全部で $7$ 通りある. $a > b$ となる場合と $a < b$ となる場合の数は等しく, これを $n$ とおくと $2n+7 = 91$ となるから, \[ n= \frac{91-7}{2} = 42.\]

問題≪和が一定である正整数の組の個数≫

 $X+Y+Z = 10$ を満たす正整数の組 $(X,\ Y,\ Z)$ の総数を求めよ.

解答例

 求める数は, $x+y+z = 7$ を満たす非負整数の組 $(x,\ y,\ z)$ の個数に等しい. これは, $7$ 個の○と $2$ 個の仕切りの並べ方の総数に等しいから, 求める数は \[ {}_9\mathrm C_2 = \frac{9\cdot 8}{2\cdot 1} = 36.\]

別解

 求める数は, 一列に並んだ $10$ 個の○の隙間 $9$ 個のうち $2$ 個に仕切りを入れる総数に等しいから, \[ {}_9\mathrm C_2 = \frac{9\cdot 8}{2\cdot 1} = 36.\]

問題≪和が一定値以下の非負整数の組の個数≫

 $x+y \leqq 7$ を満たす非負整数の組 $(x,\ y)$ の総数を求めよ.

解答例

 求める数は, $x+y+z = 7$ を満たす非負整数の組 $(x,\ y,\ z)$ の個数に等しい. これは, $7$ 個の○と $2$ 個の仕切りの並べ方の総数に等しいから, 求める数は \[ {}_9\mathrm C_2 = \frac{9\cdot 8}{2\cdot 1} = 36.\]

問題≪桁の和の上限が与えられた $n$ 桁の整数の個数≫

 各桁の和の数字の和が $r$ 以下であるような $n$ 桁の正の整数の個数を求めよ.
[東京医科歯科大 2006]

解答例

 $n \geqq 2$ とする. 十進法で表された $n$ 桁の正の整数 $10^{n-1}a_{n-1}+10a_1+a_0$ について, 各桁の和が \[ a_{n-1}+\cdots +a_0 \leqq r\] であるとする. \[ S_i = \sum_{k = 0}^{n-1}a_{n-1-k}\] とおくと, \[ 1 \leqq S_0 \leqq S_1 \leqq \cdots \leqq S_{n-1} \leqq r\] となる. この条件を満たす数列 $\{ S_i\}$ と $\{ a_i\}$ は $1:1$ に対応するから, 求める個数は \[ {}_{n+r-1}\mathrm C_n = \frac{(n+r-1)!}{n!(r-1)!}\] 個. これは $n = 1$ のときも成り立つ.

問題≪重複組合せの漸化式≫

 相異なる $n$ 個のものから重複を許して $r$ 個をとる組合せの総数を ${}_n\mathrm H_r$ で表す. 次の等式が成り立つことを示せ. \[ {}_{n+1}\mathrm H_{r+1} = {}_{n+1}\mathrm H_r+{}_n\mathrm H_{r+1}.\]

解答例

\begin{align*} {}_n\mathrm H_r &= {}_{n+r-1}\mathrm C_r \quad \cdots [1], \\ {}_{n+1}\mathrm C_{r+1} &= {}_n\mathrm C_r+{}_n\mathrm C_{r+1} \quad \cdots [2] \end{align*} より, \begin{align*} {}_{n+1}\mathrm H_{r+1} &= {}_{n+r+1}\mathrm C_{r+1} \quad (\because [1]) \\ &= {}_{n+r}\mathrm C_r+{}_{n+r}\mathrm C_{r+1} \quad (\because [2]) \\ &= {}_{n+1}\mathrm H_r+{}_n\mathrm H_{r+1} \quad (\because [1]). \end{align*}

別解

 $n+1$ 人から重複を許して $r+1$ 人の役を選ぶ組合せを考える. $n+1$ 人の中に含まれる特定の人物 A を選ぶか選ばないかで場合分けして数える.
(i)
A を選ぶ場合. $n+1$ 人から残りの $r$ 人の役を選ぶ ${}_n\mathrm H_r$ 通りの組合せがある.
(ii)
A を選ばない場合. 残りの $n$ 人から $r+1$ 人の役を選ぶ ${}_n\mathrm H_{r+1}$ 通りの組合せがある.
(i), (ii) は排反だから, \[ {}_{n+1}\mathrm H_{r+1} = {}_n\mathrm H_r+{}_n\mathrm H_{r+1}.\]

組分け

問題≪組分け≫

 次の各設定の下で, $n$ 個の玉を $3$ つの袋に入れる方法の総数を求めよ:
(a)
玉も袋も区別する.
(b)
球を区別し, 袋は区別しない.
(c)
玉は区別せず, 袋を区別する.
(d)
$n$ が $6$ の倍数であり, 玉も袋も区別しない.

解答例

(a)
$n$ 個の玉を $3$ つの袋に入れるとき, 各玉に対して入れる袋の選び方が $3$ 通りあるから, 玉の入れ方は全部で $3^n$ 通り.
(b)
袋を区別せずに玉を入れる場合の数を $b$ とおく.
(i)
$n$ 個の玉を $1$ つの袋に入れるとき, 空袋は区別できないので, 玉の入れ方は $1$ 通りしかない. この状態から袋に名前を付ける方法は $\dfrac{3!}{2!} = 3$ 通り.
(ii)
$n$ 個の玉を $2$ つ以上の袋に入れるとき, 玉の入れ方は全部で $b-1$ 通り. $3$ つの袋の中身は区別できるから, この各状態から袋に名前を付ける方法は $3!$ 通り.
袋を区別せずに玉を入れて袋に名前を付ければ (a) の設定に戻るから, \[ 1\cdot 3+(b-1)\cdot 3! = 3^n.\] ゆえに, 求める場合の数は, \[ b = \frac{3^n+3}{3!} = \frac{3^{n-1}+1}{2}.\]
(c)
袋に A, B, C と名前を付ける. $n$ 個の玉と $2$ 個の仕切りを横一列に並べ, 左の仕切りより左側にある玉を袋 A に, 左右の仕切りの間にある玉を袋 B に, 右の仕切りより右側にある玉を袋 C に入れれば, $n$ 個の玉を区別せずに袋 A~C に入れる方法が決まる. よって, 求める場合の数は, \[ {}_{n+2}\mathrm C_2 = \frac{(n+2)(n+1)}{2}.\]
(d)
$n = 6m$ ($m:$ 正の整数)とおき, 玉も袋も区別せずに玉を入れる場合の数を $d$ とおく.
(i)
袋に入る玉の数がすべて等しいとき, どの袋にも $2m$ 個の玉が入るから, 玉の入れ方は $1$ 通りしかない. $3$ つの袋の中身は区別できないから, この状態から袋に名前を付ける方法は $\dfrac{3!}{3!} = 1$ 通りしかない.
(ii)
袋に入る玉の数が $2$ つだけ等しいとき, 玉の入れ方は, 残りの袋の玉の数で決まるから, $6m,$ $6m-2,$ $\cdots,$ $0$ から $2m$ を除いた $(3m+1)-1 = 3m = \dfrac{n}{2}$ 通り. この各状態から袋に名前をつける方法は, $\dfrac{3!}{2!} = 3$ 通り.
(iii)
袋に入る玉の数がすべて異なるとき, 玉の入れ方は $d-1-\dfrac{n}{2}$ 通り. 玉の数で袋は区別できるから, この各状態から袋に名前を付ける方法は, $3!$ 通り.
玉も袋も区別せずに玉を入れて袋に名前を付ければ (c) の設定に戻るから, \[ 1\cdot 1+\frac{n}{2}\cdot 3+\left( d-1-\frac{n}{2}\right)\cdot 3! = \frac{(n+2)(n+1)}{2}.\] ゆえに, 求める場合の数は, $6\left( d-1-\dfrac{n}{2}\right) = \dfrac{1}{2}(n^2+3n+2)-\dfrac{3}{2}n-1 = \dfrac{n^2}{2}$ より, \[ d = \frac{n^2}{12}+\frac{n}{2}+1.\]

問題≪スターリング数の漸化式≫

 互いに区別できる $n$ 個の対象を $r$ 個のグループに分ける方法の総数を ${}_n\mathrm S_r$ で表す. ${}_{n+1}\mathrm S_{r+1} = {}_n\mathrm S_r+(r+1){}_n\mathrm S_{r+1}$ が成り立つことを示せ.

解答例

 A を含む $n+1$ 個を $r+1$ 個のグループに分ける方法を考える.
(i)
A が単独のとき. A 以外の $n$ 個を $r$ 個のグループに分ける ${}_n\mathrm S_r$ 通りある.
(ii)
A が単独でないとき. まず A 以外の $n$ 個を $r+1$ 個のグループに分けてから A がどのグループに加わるかを考えると, $(r+1){}_n\mathrm S_{r+1}$ 通りある.
(i), (ii) は排反だから, ${}_{n+1}\mathrm S_{r+1} = {}_n\mathrm S_r+(r+1){}_n\mathrm S_{r+1}.$

問題≪ベル数の漸化式≫

 互いに区別できる $n$ 個の対象をグループに分ける方法の総数を $B(n)$ で表す. $B(0) = 1$ と定める.
(1)
次の等式が成り立つことを示せ. \[ B(n+1) = \sum\limits_{k = 0}^n{}_n\mathrm C_kB(k).\]
(2)
$B(5)$ を求めよ.

解答例

(1)
特定の人物 A を含む $n+1$ 人をグループに分ける場合の数を考える.
$0 \leqq k \leqq n$ なる整数 $k$ について A が $k+1$ 人から成るグループに分けられるとき,
A と同じグループに属する人の選び方は A を除く $n$ 人から $k$ 人を選ぶ組合せ ${}_n\mathrm C_k$ だけ方法があり,
その各場合について残りの $(n+1)-(k+1) = n-k$ 人をグループに分ける $B(n-k)$ 通りの方法があるから,
グループ分けの方法の総数は ${}_n\mathrm C_kB(n-k)$ 通りある.
ゆえに, \begin{align*} B(n+1) &= \sum\limits_{k = 0}^n{}_n\mathrm C_kB(n-k) = \sum\limits_{k = 0}^n{}_n\mathrm C_{n-k}B(n-k) \\ &= \sum\limits_{k = 0}^n{}_n\mathrm C_kB(k). \end{align*}
(2)
(1) より, \begin{align*} B(1) &= {}_0\mathrm C_0B(0) = 1, \\ B(2) &= {}_1\mathrm C_0B(0)+{}_1\mathrm C_1B(1) \\ &= 1\cdot 1+1\cdot 1 = 2, \\ B(3) &= {}_2\mathrm C_0B(0)+{}_2\mathrm C_1B(1)+{}_2\mathrm C_2B(2) \\ &= 1\cdot 1+2\cdot 1+1\cdot 2 = 5, \\ B(4) &= {}_3\mathrm C_0B(0)+{}_3\mathrm C_1B(1)+{}_3\mathrm C_2B(2)+{}_3\mathrm C_3B(3) \\ &= 1\cdot 1+3\cdot 1+3\cdot 2+1\cdot 5 = 15, \\ B(5) &= {}_4\mathrm C_0B(0)+{}_4\mathrm C_1B(1)+{}_4\mathrm C_2B(2) \\ &\qquad +{}_4\mathrm C_3B(3)+{}_4\mathrm C_4B(4) \\ &= 1\cdot 1+4\cdot 1+6\cdot 2+4\cdot 5+1\cdot 15 = 52. \end{align*}

約数の個数

問題≪与えられた個数の約数を持つ最小の自然数≫

 正の約数の個数が $100$ であるような最小の自然数 $n$ を求めよ.

解答例

 $n$ を $n = p_1^{m_1}\cdots p_r^{m_r}$ と異なる素因数 $p_1 < \cdots < p_r$ の積に分解すると, $n$ の正の約数の個数は \[ (m_1+1)\cdots (m_r+1) = 100 = 2^2\cdot 5^2.\] 右辺の素因数は重複度を込めて $4$ だから, $r \leqq 4.$ $n$ の最小性より, \[p_1 = 2, \quad p_2 = 3, \quad p_3 = 5, \quad p_4 = 7.\] べき乗関数 $x^m$ は単調増加だから, $n$ の最小性より, $(m_1+1,\ m_2+1,\ m_3+1,\ m_4+1)$ の候補は \begin{align*} &(5,\ 5,\ 2,\ 2),\ (5,\ 5,\ 4,\ 1), \\ &(10,\ 5,\ 2,\ 1),\ (25,\ 2,\ 2,\ 1), \\ &(20,\ 5,\ 1,\ 1),\ (25,\ 4,\ 1,\ 1), \\ &(50,\ 2,\ 1,\ 1),\ (100,\ 1,\ 1,\ 1). \end{align*} よって, $m_1,$ $m_2,$ $m_3,$ $m_4$ の候補は, \begin{align*} (m'_1,\ m'_2,\ m'_3,\ m'_4) = &(4,\ 4,\ 1,\ 1),\ (4,\ 4,\ 3,\ 0), \\ &(9,\ 4,\ 1,\ 0),\ (24,\ 1,\ 1,\ 0), \\ &(19,\ 4,\ 0,\ 0),\ (24,\ 3,\ 0,\ 0), \\ &(49,\ 1,\ 0,\ 0),\ (99,\ 0,\ 0,\ 0). \end{align*} これらの値に対して $2^{m'_1}3^{m'_2}5^{m'_3}7^{m'_4}$ の値を比較すると, $7 < 5^2 = 25 < 2^5 = 32,$ $3^45^1 = 405 < 2^{10} = 1024$ より \[ 2^43^45^17^1 < 2^43^45^3 < 2^93^45^1 < 2^{19} < 2^{24} < 2^{49} < 2^{99}\] だから, \[ n = 2^43^45^17^1 = 45360.\]

その他

問題≪道順の総数≫

 次の地図において, 道に沿って右, 上, 右上の $3$ 方向にのみ進めるとき, 点 $\mathrm A$ から点 $\mathrm B$ に至る経路の総数を求めよ.

解答例

 次のように座標軸を定める.
このとき, すべての経路は次のように分類される:
(P1)
点 $\mathrm P_1(3,\ 2)$ を通る($16^2$ 通り).
(P2)
点 $\mathrm P_2(4,\ 1)$ を通る($8^2$ 通り).
(P3)
点 $\mathrm P_3(5,\ 0)$ を通る($1^2$ 通り).
(Q1)
点 $\mathrm Q_1(2,\ 2),$ $\mathrm Q'_1(3,\ 3)$ を通る($6^2$ 通り).
(Q2)
点 $\mathrm Q_2(3,\ 1),$ $\mathrm Q'_2(4,\ 2)$ を通る($6^2$ 通り).
(Q3)
点 $\mathrm Q_3(4,\ 0),$ $\mathrm Q'_3(5,\ 1)$ を通る($1^2$ 通り).
各場合の経路の数は次のことに注意すると () 内のように求まる. ただし, $1 \leqq k \leqq 3$ とする.
  • 点 $\mathrm A$ から点 $\mathrm A$ までの経路の数は $1.$
  • 各地点までの経路の数は, すぐ左, すぐ下, すぐ左下の地点までの経路の数の和に等しい.
  • (Pk) において, 点 $\mathrm A$ から $\mathrm P_k$ までの経路の数は, 点 $\mathrm P_k$ から $\mathrm B$ までの経路の数に等しい.
  • (Qk) において, 点 $\mathrm A$ から $\mathrm Q_k$ までの経路の数は, 点 $\mathrm Q'_k$ から $\mathrm B$ までの経路の数に等しい.
  • (Qk) において, 点 $\mathrm Q_k$ から $\mathrm Q'_k$ へは右上に進むように限定されている.
(P1)~(P3), (Q1)~(Q3) は排反だから, 求める場合の数は \[ 6^2+16^2+6^2+8^2+1^2+1^2 = 394.\]

問題≪回転するタイルの配色≫

 白色の正方形のタイルを縦に $3$ 枚, 横に $3$ 枚並べて正方形を作る. この $9$ 枚のうちの $3$ 枚を黒色で塗る. 回転により一致する配色を同一視するとき, 塗り方は何タイプあるか.

解答例

 固定された $9$ 枚のタイルに色を塗る方法の総数は, \[ {}_9\mathrm C_3 = 84.\] これらを, 回転して自身に重なる角度によって分類すると, 次の $2$ つに分けられる:
(i)
$180^\circ$ の回転で自身に重なる場合. 塗り方は次の $2$ タイプで $2$ 通りずつある.
(ii)
その他の場合. 回転して一致する配色は, $1$ タイプにつき $4$ 通りずつ存在する.
回転による同一視をすると, 塗り方は $\dfrac{84-2\cdot 2}{4} = 20$ タイプある.
よって, 求める場合の数は, \[ 2+20 = 22.\]

問題≪整数の分割≫

(a)
$10$ を $3$ 個の正整数の和に表す方法は何通りあるか.
(b)
$7$ を $3$ 以下の正整数の和に表す方法は何通りあるか.
ただし, 和の順序は交換可能とする.

解答例

(a)
$10$ を $3$ 個の正整数の和に表す方法を, 辞書式に並べると次のようになるから, 求める数は $8$ 通り. \begin{align*} 10 &= 1+1+8 = 2+2+6 = 3+3+4 \\ &= 1+2+7 = 2+3+5 \\ &= 1+3+6 = 2+4+4 \\ &= 1+4+5. \end{align*}
(b)
$7$ を $3$ 以下の正整数の和に表す方法を, $3$ の個数, 次いで $2$ の個数の多い順に並べて書くと次のようになるから, 求める数は $8$ 通り. \begin{align*} 7 &= 3+3+1 \\ &= 3+2+2 = 3+2+1+1 = 3+1+1+1+1 \\ &= 2+2+2+1 \\ &= 2+2+1+1+1 \\ &= 2+1+1+1+1+1 \\ &= 1+1+1+1+1+1+1. \end{align*}

問題≪試合数≫

(a)
$n$ 人がトーナメント戦で優勝者を決めるのに必要な試合数を求めよ.
(b)
$n$ 人が総当たりのリーグ戦を行うときの試合数を求めよ.

解答例

(a)
トーナメント戦では, $1$ 試合ごとにちょうど $1$ 人の敗者が決まり, 最後に $1$ 度も負けなかった $1$ 人が優勝するから, 求める試合数は $n-1.$
(b)
各選手の試合数は $n-1.$ 各試合で対戦記録がつけられるとすれば, $n(n-1)$ 回選手名が記録されることになるが, 各試合で $2$ 回の選手名が記録されるから, 求める試合数は $\dfrac{n(n-1)}{2}.$