有名問題・定理から学ぶ数学

Well-Known Problems and Theorems in Mathematics

数式を枠からはみ出さずに表示するためには, 画面を横に傾けてください.

組分け

組分け

問題《同じものを含む順列の公式》

 $n_1$ 個の同じもの, $\cdots,$ $n_r$ 個の同じものを $1$ 列に並べる方法の総数は \[\frac{(n_1+\cdots +n_r)!}{n_1!\cdots n_r!}\] である.

証明

 積の法則により, 求める場合の数は \[\begin{aligned} &{}_{n_1+\cdots +n_r}\mathrm C_{n_1}\cdot\cdots\cdot{}_{n_k+\cdots +n_r}\mathrm C_k\cdot\cdots\cdot{}_{n_r}\mathrm C_{n_r} \\ &= \frac{(n_1+\cdots +n_r)!}{n_1!(n_2+\cdots +n_r)!}\cdot\cdots\cdot\frac{(n_k+\cdots +n_r)!}{n_k!(n_{k+1}+\cdots +n_r)!}\cdot\cdots\cdot\frac{n_r!}{n_r!0!} \\ &= \frac{(n_1+\cdots +n_r)!}{n_1!\cdots n_r!} \end{aligned}\] である.

別証明

 同じものごとに番号をふって $1$ 列に並べる方法は $(n_1+\cdots +n_r)!$ 通りあり, 番号を消したときに同一視されるものが $n_1!\cdots n_r!$ 通りずつあるから, 求める場合の数は \[\frac{(n_1+\cdots +n_r)!}{n_1!\cdots n_r!}\] である.

問題《重複組合せの公式》

 $n$ 種類のものから重複を許して $r$ 個選ぶ方法の総数は \[ {}_{n+r−1}\mathrm C_r​\] である.

証明

 $n$ 種類のものから重複を許して $r$ 個選ぶ方法を記録するには, $r$ 個の空欄〇と $n-1$ 個の仕切り|を横 $1$ 列に並べることで $r$ 個の空欄 〇 を $n$ 個の区画に分け (〇 が $0$ 個の区画があってもよい), 左から順に区画に種類の名前を記入すればよい. つまり, その場合の数は, $r$ 個の ◯ と $n-1$ 個の仕切り | を $1$ 列に並べる方法の総数 \[ {}_{r+(n−1)}\mathrm C_r​ = {}_{n+r−1}\mathrm C_r​\] に等しい.

問題《区別できる玉の組分け》

 次の各場合に, $r$ 個の玉を $n$ 個の箱に入れる方法の総数を求めよ. ただし, $1$ 個も玉の入らない箱があってもよいとする.
(1)
玉が区別できて, 箱が $\mathrm A_1,$ $\cdots,$ $\mathrm A_n$ と区別されている場合.
(2)
$n = 2$ であり, 玉が区別できて, 箱は区別できない場合.
(3)
$n = 3$ であり, 玉が区別できて, 箱は区別できない場合.
(参考: $2019$ 高知工科大, $1996$ 東京大)
標準先例$2018/09/10$$2022/05/07$

解答例

(1)
$1$ 個の玉につき $\mathrm A_1,$ $\cdots,$ $\mathrm A_n$ のどの箱に入れるかで $n$ 通りの方法があるから, 求める場合の数は $n^r$ である.
(2)
求める場合の数は, $n = 2$ のとき (1) において箱の区別をなくした場合の数に等しく, $\dfrac{2^r}{2!} = 2^{r-1}$ である.
(3)
求める場合の数を $N$ とおく.
(i)
$r$ 個の玉が $1$ つの箱に入る場合は, $1$ 通り. この状態から箱に $\mathrm A_1,$ $\mathrm A_2,$ $\mathrm A_3$ と名前をつけると, 名前のつけ方は $3$ 通りあるから, (1) の $3$ 通りが生じる.
(ii)
$r$ 個の玉が複数の箱に入る場合は, $N-1$ 通り. このとき,玉の入った箱は入っている玉によって区別でき, 空箱は高々 $1$ 個で玉の入った箱と区別できるから, 箱はすべて区別できる. よって, この状態から箱に $\mathrm A_1,$ $\mathrm A_2,$ $\mathrm A_3$ と名前をつけると, 名前のつけ方は $3!$ 通りあるから, (1) の $3!(N-1)$ 通りが生じる.
(i), (ii) と (1) の結果により \[ 3+3!(N-1) = 3^r\] が成り立つから, \[ N = \frac{3^r+3}{3!} = \frac{3^{r-1}+1}{2}\] である.

別解

(3)
区別ができる $r$ 個の玉を区別のできない $3$ つの箱に入れるとき, $r$ 個の玉が $1$ つの箱に入る場合の数を $a_r,$ ちょうど $2$ つの箱の箱に入る場合の数を $b_r,$ ちょうど $3$ つの箱に入る場合の数を $c_r$ とおき, その総数を $N_r$ とおく. このとき, \[\begin{aligned} N_r &= a_r+b_r+c_r, \\ a_{r+1} &= a_r, \\ b_{r+1} &= a_r+2b_r, \\ c_{r+1} &= b_r+3c_r \end{aligned}\] であるから, \[\begin{aligned} N_{r+1} &= a_{r+1}+b_{r+1}+c_{r+1} \\ &= a_r+(a_r+2b_r)+(b_r+3c_r) \\ &= 3(a_r+b_r+c_r)-a_r \\ &= 3N_r-1 \quad [1] \end{aligned}\] が成り立つ. よって, $[1]$ の辺々から $x = 3x-1$ の解 $x = \dfrac{1}{2}$ を引くと \[ N_{r+1}-\frac{1}{2} = 3\left( N_r-\frac{1}{2}\right)\] となる. したがって, $\left\{ N_r-\dfrac{1}{2}\right\}$ は初項 $N_1-\dfrac{1}{2} = \dfrac{1}{2},$ 公比 $3$ の等比数列であるから, \[\begin{aligned} N_r-\frac{1}{2} &= \frac{1}{2}\cdot 3^{r-1} \\ N_r &= \frac{3^{r-1}+1}{2} \end{aligned}\] である.

参考

 互いに区別できる $n$ 個のものを $r$ 個の組に分ける方法の総数を「第 $2$ 種スターリング数」(Stirling number of the second kind) と呼び, ${}_n\mathrm S_r$ で表す. (2), (3) の結果により ${}_n\mathrm S_1 = 1,$ ${}_n\mathrm S_1+{}_n\mathrm S_2 = 2^{n-1}, $ ${}_n\mathrm S_1+{}_n\mathrm S_2+{}_n\mathrm S_3 = \dfrac{3^{n-1}+1}{2}$ であるから, \[ {}_n\mathrm S_2 = 2^{n-1}-1, \quad {}_n\mathrm S_3 = \frac{3^{n-1}-2^n+1}{2}\] である.

問題《区別できない玉の組分け》

 次の各場合に, $r$ 個の玉を $n$ 個の箱に入れる方法の総数を求めよ. ただし, $1$ 個も玉の入らない箱があってもよいとする.
(1)
玉は区別できず, 箱が $\mathrm A_1,$ $\cdots,$ $\mathrm A_n$ と区別されている場合.
(2)
$n = 2$ であり, 玉は区別できず, 箱も区別できない場合.
(3)
$n = 3$ であり, 玉は区別できず, 箱も区別できない場合.
(参考: $1996$ 東京大)
実戦先例$2018/09/11$$2022/05/07$

解答例

(1)
$\mathrm A_1,$ $\cdots,$ $\mathrm A_n$ の各箱に入る玉の個数を $x_1,$ $\cdots,$ $x_n$ とおくと, \[ x_1+\cdots +x_n = r, \quad x_1,\ \cdots,\ x_n \geqq 0\] となり, $x_1,$ $\cdots,$ $x_n$ はそれぞれ $r$ 個の〇と $n-1$ 本の|の順列において|で仕切られた〇の個数に対応するから, 求める場合の数は \[ {}_{r+(n-1)}\mathrm C_r = {}_{r+(n-1)}\mathrm C_{n-1} = \frac{(n+r-1)!}{(n-1)!r!}\] である.
(2)
$n = 2$ のとき, (1) の場合の数は \[ {}_{r+(2-1)}\mathrm C_{2-1} = r+1\] である. 求める場合の数を $N$ とおく.
(I)
$r$ が奇数の場合. $2$ つの箱に入る玉の個数は異なるので, この状態から箱に $\mathrm A_1,$ $\mathrm A_2$ と名前をつける方法は $2!$ 通りある. よって, (1) の場合の数について \[ 2!N = r+1\] が成り立つから, \[ N = \frac{r+1}{2}\] である.
(II)
$r = 2k$ ($k$: 正の整数) の場合.
(i)
$2$ つの箱に入る玉の個数が等しい場合, 玉の個数の組合せは $\{ k,k\}$ の $1$ 通り. この状態から箱に $\mathrm A_1,$ $\mathrm A_2$ と名前をつけると, 名前のつけ方は $1$ 通りあるから, (1) の $1$ 通りが生じる.
(ii)
$2$ つの箱に入る玉の個数が異なる場合, 玉の個数の組合せは $N-1$ 通り. この状態から箱に $\mathrm A_1,$ $\mathrm A_2$ と名前をつけると, 名前のつけ方は $2!$ 通りあるから, (1) の $2!(N-1)$ 通りが生じる.
(i), (ii) から (1) の場合の数は \[ 1+2!(N-1) = r+1\] と表せるので, これを $N$ について解くと \[ N = \frac{r}{2}+1\] が得られる.
(3)
$n = 3$ のとき, (1) の場合の数は \[ {}_{r+(3-1)}\mathrm C_{3-1} = \frac{(r+2)(r+1)}{2} \quad \cdots [1]\] である. 求める場合の数を $N$ とおく.
(I)
$r = 6k$ ($k$: 正の整数) の場合.
(i)
各箱に入る玉の個数がすべて等しい場合, 玉の個数の組合せは $\{ 2k,2k,2k\}$ の $1$ 通り. この状態から箱に $\mathrm A_1,$ $\mathrm A_2,$ $\mathrm A_3$ と名前をつけると, 名前のつけ方は $1$ 通りあるから, (1) の $1$ 通りが生じる.
(ii)
各箱に入る玉の個数が $2$ 箱だけ等しい場合, 玉の個数の組合せは $\{ 0,0,6k\},$ $\cdots,$ $\{ 3k,3k,0\}$ から (i) の場合を除いた $3k$ 通り. この状態から箱に $\mathrm A_1,$ $\mathrm A_2,$ $\mathrm A_3$ と名前をつけると, 名前のつけ方は $\dfrac{3!}{2!} = 3$ 通りあるから, (1) の $3\cdot 3k$ 通りが生じる.
(iii)
各箱に入る玉の個数がすべて異なる場合, 玉の個数の組合せは $N-3k-1$ 通り. この状態から箱に $\mathrm A_1,$ $\mathrm A_2,$ $\mathrm A_3$ と名前をつけると, 名前のつけ方は $3!$ 通りあるから, (1) の $3!(N-3k-1)$ 通りが生じる.
(i)~(iii) から (1) の場合の数は \[\begin{aligned} &1+3\cdot 3k+3!(N-3k-1) \\ &= 6N-9k-5 = 6N-\frac{3r+10}{2} \quad \cdots [2] \end{aligned}\] と表せるので, $[1] = [2]$ を $N$ について解くと \[ N = \frac{r^2+6r+12}{12}\] が得られる.
(II)
$r = 6k+1$ ($k$: 非負整数) の場合. (I) と同様にして (1) の場合の数は \[\begin{aligned} &0+3(3k+1)+3!(N-3k-1) \\ &= 6N-9k-3 = 6N-\frac{3(r+1)}{2} \end{aligned}\] と表せるから, \[ N = \frac{(r+1)(r+5)}{12}\] である.
(III)
$r = 6k+2$ ($k$: 非負整数) の場合. (I) と同様にして (1) の場合の数は \[\begin{aligned} &0+3(3k+2)+3!(N-3k-2) \\ &= 6N-9k-6 = 6N-\frac{3(r+2)}{2} \end{aligned}\] と表せるから, \[ N = \frac{(r+2)(r+4)}{12}\] である.
(IV)
$r = 6k+3$ ($k$: 非負整数) の場合. (I) と同様にして (1) の場合の数は \[\begin{aligned} &1+3(3k+1)+3!(N-3k-2) \\ &= 6N-9k-8 = 6N-\frac{3r+7}{2} \end{aligned}\] と表せるから, \[ N = \frac{(r+3)^2}{12}\] である.
(V)
$r = 6k+4$ ($k$: 非負整数) の場合. (I) と同様にして (1) の場合の数は \[\begin{aligned} &0+3(3k+3)+3!(N-3k-3) \\ &= 6N-9k-9 = 6N-\frac{3(r+2)}{2} \end{aligned}\] と表せるから, \[ N = \frac{(r+2)(r+4)}{12}\] である.
(VI)
$r = 6k+5$ ($k$: 非負整数) の場合. (I) と同様にして (1) の場合の数は \[\begin{aligned} &0+3(3k+3)+3!(N-3k-3) \\ &= 6N-9k-9 = 6N-\frac{3(r+1)}{2} \end{aligned}\] と表せるから, \[ N = \frac{(r+1)(r+5)}{12}\] である.

参考

 (1) のように $n$ 種類のものから重複を許して $r$ 個を取る選び方を「重複組合せ」(combination with repetition) と呼び, その総数を ${}_n\mathrm H_r$ で表す.

問題《重複組合せの漸化式》

 相異なる $n$ 個のものから重複を許して $r$ 個を取る組合せの総数を ${}_n\mathrm H_r$ で表す. また, ${}_n\mathrm H_0 = 1$ と定める. $r \geqq 0$ のとき, 次のことを示せ.
(1)
${}_{n+1}\mathrm H_{r+1} = {}_{n+1}\mathrm H_r+{}_n\mathrm H_{r+1}$ が成り立つ.
(2)
$\displaystyle\sum_{k = 1}^n{}_k\mathrm H_r = {}_n\mathrm H_{r+1}$ が成り立つ.
標準定理$2016/04/19$$2022/12/21$

解答例

(1)
\[\begin{aligned} {}_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{aligned}\] ($[2]$ の証明についてはこちらを参照) であるから, \[\begin{aligned} {}_{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{aligned}\] が成り立つ.
(2)
(1) を繰り返し使うと, \[\begin{aligned} {}_n\mathrm H_{r+1} &= {}_n\mathrm H_r+{}_{n-1}\mathrm H_{r+1} \\ &= \cdots \\ &= {}_n\mathrm H_r+\cdots +{}_k\mathrm H_{r+1} \\ &= {}_n\mathrm H_r+\cdots +{}_k\mathrm H_r+{}_{k-1}\mathrm H_{r+1} \\ &= \cdots \\ &= {}_n\mathrm H_r+\cdots +{}_2\mathrm H_r+{}_1\mathrm H_{r+1} \\ &= {}_n\mathrm H_r+\cdots +{}_2\mathrm H_r+{}_1\mathrm H_r \end{aligned}\] が得られる.

別解

(1)
$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}\] が成り立つ.

参考

  • (2) は,「ホッケー・スティック恒等式」(こちらを参照) により, \[\sum_{k = 1}^n{}_k\mathrm H_r = \sum_{k = 1}^n{}_{k+r-1}\mathrm C_r = \sum_{l = r}^{n+r-1}{}_l\mathrm C_r = {}_{n+r}\mathrm C_{r+1} = {}_n\mathrm H_{r+1}\] と証明できる.
  • $|x| < 1$ のとき \[ (1+x)^{-n} = \sum_{r = 0}^\infty (-1)^r{}_n\mathrm H_r\,x^r\] の成り立つことが知られている.

問題《第 $1$ 種スターリング数》

 $n,$ $r$ を非負整数とする. $n \geqq r > 0$ のとき, $n$ 人を $r$ 個の組に分けて各組で $1$ つの円順列を作る方法の総数を $s(n,r)$ で表す. さらに, $s(0,0) = 1,$ $s(n,0) = 0$ $(n > 0)$ と定める. また, $x$ の $n$ 次関数 $x^{\bar n}$ を $x^{\bar 0} = 1,$ $x^{\overline{n+1}} = x^{\overline n}(x+n)$ で定める. つまり, $m$ が正の整数であるとき, $m^{\bar n} = {}_{m+n-1}\mathrm P_n$ である. 次のことを示せ.
(1)
$n > r$ ならば, \[ s(n+1,r+1) = s(n,r)+ns(n,r+1) \quad \cdots [1]\] が成り立つ.
(2)
\[ x^{\bar n} = \sum_{k = 0}^ns(n,k)x^k \quad \cdots [2]\] が成り立つ.
実戦定理$2022/12/07$$2023/06/27$

解答例

(1)
$n > r = 0$ のとき, \[\begin{aligned} s(n+1,1) &= \{ (n+1)-1\} ! = n!, \\ s(n,0)+ns(n,1) &= 0+n\cdot (n-1)! = n! \end{aligned}\] であるから, $[1]$ が成り立つ.
 以下, $n > r > 0$ のとき, 特定の人物 A を含む $n+1$ 人を $r+1$ 個の組に分けて各組で $1$ つの円順列を作る方法を考える.
(i)
A が単独の場合. A 以外の $n$ 人を $r$ 個の組に分けて各組で $1$ つの円順列を作る $s(n,r)$ 通りある.
(ii)
A が単独でない場合. まず A 以外の $n$ 人を $r+1$ 個の組に分けてから A が誰の右隣に入るかを考えると, $ns(n,r+1)$ 通りあることがわかる.
(i), (ii) は同時に起こらないから, \[ s(n+1,r+1) = s(n,r)+ns(n,r+1) \quad \cdots [1]\] が成り立つ.
(2)
$n = 0$ のとき. \[ x^{\bar n} = s(0,0)x^0 = 1\] であるから, $[2]$ が成り立つ.
 以下, 正の整数 $n$ に関する数学的帰納法で $[2]$ を示す.
(i)
$n = 1$ のとき. \[ x^{\bar 1} = s(1,0)x^0+s(1,1)x^1 = x\] であるから, $[2]$ が成り立つ.
(ii)
与えられた正の整数 $n$ に対して $[2]$ が成り立つとする. このとき, \[\begin{aligned} &x^{\overline{n+1}} = x^{\overline n}(x+n) \\ &= \left\{\sum_{k = 0}^ns(n,k)x^k\right\}(x+n) \\ &= \sum_{k = 0}^ns(n,k)x^{k+1}+n\sum_{k = 0}^ns(n,k)x^k \\ &= \sum_{k = 1}^{n+1}s(n,k-1)x^k+n\sum_{k = 0}^ns(n,k)x^k \\ &= ns(n,0)x^0+\sum_{k = 1}^n\{ s(n,k-1)+ns(n,k)\} x^k \\ &\qquad +s(n,n)x^{n+1} \\ &= s(n\!+\!1,0)x^0\!+\!\sum_{k = 1}^ns(n\!+\!1,k)x^k\!+\!s(n\!+\!1,n\!+\!1)x^{n+1} \\ &\qquad \left(\begin{array}{ll} \because [1], & s(n,0) = s(n+1,0) = 0, \\ {} & s(n,n) = s(n+1,n+1) = 1 \end{array}\right) \\ &= \sum_{k = 0}^{n+1}s(n+1,k)x^k \end{aligned}\] となるから, $[2]$ において $n$ を $n+1$ に置き換えた等式が成り立つ.
 以上から, すべての非負整数 $n$ に対して $[2]$ が成り立つ.

参考

  • 互いに区別できる $n$ 個のものを $r$ 個の組に分けて各組で $1$ つの円順列を作る方法の総数を「第 $1$ 種スターリング数」(Stirling number of the first kind) と呼ぶ. 世界的には $\begin{bmatrix} n \\ r \end{bmatrix}$ という記号で表すことが多い. 初めの方の「第 $1$ 種スターリング数」を求めると, 次の表のようになる.
$n$\$r$$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$
$1$$1$
$2$$1$$1$
$3$$2$$3$$1$
$4$$6$$11$$6$$1$
$5$$24$$50$$35$$10$$1$
$6$$120$$274$$225$$85$$15$$1$
$7$$720$$1764$$1624$$735$$175$$21$$1$
$8$$5040$$13068$$13132$$6769$$1960$$322$$28$$1$
$9$$40320$$109584$$118124$$67284$$22449$$4536$$546$$36$$1$
$10$$362880$$1026576$$1172700$$723680$$269325$$63273$$9450$$870$$45$$1$
  • $x^{\bar n}$ を $x$ の「上昇階乗べき」と呼ぶ.
  • (2) で示した等式 $x^{\bar n} = \displaystyle\sum_{k = 0}^n\begin{bmatrix} n \\ k \end{bmatrix}x^k$ をもとに「第 $1$ 種スターリング数」$\begin{bmatrix} n \\ r \end{bmatrix}$ を定義することも多い (こちらを参照).
  • $x^{\underline 0} = 1,$ $x^{\underline{n+1}} = x^{\underline n}(x-n)$ で定まる $x$ の「下降階乗べき」$x^{\underline n}$ について, $x^{\underline n} = \displaystyle\sum_{k = 0}^n(-1)^{n-k}\begin{bmatrix} n \\ k \end{bmatrix}x^k$ が成り立つ. $(-1)^{n-r}\begin{bmatrix} n \\ r \end{bmatrix}$ にあたる整数を「第 $1$ 種スターリング数」として定義する流儀もあるため, 注意されたい.

  • 問題《第 $2$ 種スターリング数》

     $n,$ $r$ を非負整数とする. $n \geqq r > 0$ のとき, $n$ 人を $r$ 個の組に分ける方法の総数を ${}_n\mathrm S_r$ で表す. さらに, ${}_0\mathrm S_0 = 1,$ ${}_n\mathrm S_0 = 0$ $(n > 0)$ と定める. また, $x$ の $n$ 次関数 $x^{\underline n}$ を $x^{\underline 0} = 1,$ $x^{\underline{n+1}} = x^{\underline n}(x-n)$ で定める. つまり, $m$ が $n$ 以上の整数であるとき, $m^{\underline n} = {}_m\mathrm P_n$ である. 次のことを示せ.
    (1)
    $n > r$ ならば, \[ {}_{n+1}\mathrm S_{r+1} = {}_n\mathrm S_r+(r+1)\,{}_n\mathrm S_{r+1} \quad \cdots [1]\] が成り立つ.
    (2)
    \[ x^{\underline n}x = x^{\underline{n+1}}+nx^{\underline n} \quad \cdots [2]\] が成り立つ.
    (3)
    \[ x^n = \sum_{k = 0}^n{}_n\mathrm S_k\,x^{\underline k} \quad \cdots [3]\] が成り立つ.
    (参考: $2012$ 奈良女子大)
    実戦定理$2019/03/08$$2022/12/16$

    解答例

    (1)
    $n > r = 0$ のとき, \[ {}_{n+1}\mathrm S_1 = 1, \quad {}_n\mathrm S_0+1\cdot \,{}_n\mathrm S_1 = 0+1\cdot 1 = 1\] であるから, $[1]$ が成り立つ.
     以下, $n > r > 0$ のとき, 特定の人物 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} \quad \cdots [1]\] が成り立つ.
    (2)
    定義により, \[\begin{aligned} x^{\underline{n+1}}+nx^{\underline n} &= x^{\underline n}(x-n)+nx^{\underline n} = x^{\underline n}\{ (x-n)+n\} \\ &= x^{\underline n}x \quad \cdots [2] \end{aligned}\] が成り立つ.
    (3)
    $n = 0$ のとき. \[ x^0 = {}_0\mathrm S_0x^{\underline 0} = 1\] であるから, $[3]$ が成り立つ.
     以下, 正の整数 $n$ に関する数学的帰納法で $[3]$ を示す.
    (i)
    $n = 1$ のとき. \[ x^1 = {}_1\mathrm S_0x^{\underline 0}+{}_1\mathrm S_1x^{\underline 1} = x\] であるから, $[3]$ が成り立つ.
    (ii)
    与えられた正の整数 $n$ に対して $[3]$ が成り立つとする. このとき, \[\begin{aligned} &x^{n+1} = x^nx \\ &= \left(\sum_{k = 0}^n{}_n\mathrm S_k\,x^{\underline k}\right) x = \sum_{k = 0}^n{}_n\mathrm S_k\,x^{\underline k}x \\ &= \sum_{k = 0}^n{}_n\mathrm S_k\,(x^{\underline{k+1}}+kx^{\underline k}) \quad (\because [2]) \\ &= \sum_{k = 0}^n{}_n\mathrm S_k\,x^{\underline{k+1}}+\sum_{k = 0}^nk\,{}_n\mathrm S_k\,x^{\underline k} \\ &= \sum_{k = 1}^{n+1}{}_n\mathrm S_{k-1}\,x^{\underline k}+\sum_{k = 0}^nk\,{}_n\mathrm S_k\,x^{\underline k} \\ &= 0\cdot{}_n\mathrm S_0\,x^{\underline 0}+\sum_{k = 1}^n({}_n\mathrm S_{k-1}+k\,{}_n\mathrm S_k)\,x^{\underline k}+{}_n\mathrm S_n\,x^{\underline{n+1}} \\ &= {}_{n+1}\mathrm S_0\,x^{\underline 0}+\sum_{k = 1}^n{}_{n+1}\mathrm S_k\,x^{\underline k}+{}_{n+1}\mathrm S_{n+1}\,x^{\underline{n+1}} \\ &\qquad \left(\begin{array}{ll} \because [1], & {}_n\mathrm S_0 = {}_{n+1}\mathrm S_0 = 0, \\ {} & {}_n\mathrm S_n = {}_{n+1}\mathrm S_{n+1} = 1 \end{array}\right) \\ &= \sum_{k = 0}^{n+1}{}_{n+1}\mathrm S_k\,x^{\underline k} \end{aligned}\] となるから, $[3]$ において $n$ を $n+1$ に置き換えた等式が成り立つ.
     以上から, すべての非負整数 $n$ に対して $[3]$ が成り立つ.

    参考

    • 互いに区別できる $n$ 個のものを $r$ 個の組に分ける方法の総数を「第 $2$ 種スターリング数」(Stirling number of the second kind) と呼ぶ. 世界的には $\begin{Bmatrix} n \\ r \end{Bmatrix}$ という記号で表すことが多い. 初めの方の「第 $2$ 種スターリング数」を求めると, 次の表のようになる.
      $n$\$r$$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$
      $1$$1$
      $2$$1$$1$
      $3$$1$$3$$1$
      $4$$1$$7$$6$$1$
      $5$$1$$15$$25$$10$$1$
      $6$$1$$31$$90$$65$$15$$1$
      $7$$1$$63$$301$$350$$140$$21$$1$
      $8$$1$$127$$966$$1701$$1050$$266$$28$$1$
      $9$$1$$255$$3025$$7770$$6951$$2646$$462$$36$$1$
      $10$$1$$511$$9330$$34105$$42525$$22827$$5880$$750$$45$$1$
    • $x^{\underline n}$ を $x$ の「下降階乗べき」と呼ぶ.
    • (2) の等式 $x^n = \displaystyle\sum_{k = 0}^n\begin{Bmatrix} n \\ k \end{Bmatrix}x^{\underline k}$ をもとに「第 $2$ 種スターリング数」$\begin{Bmatrix} n \\ k \end{Bmatrix}$ を定義することも多い.
    • 「第 $1$ 種スターリング数」と「第 $2$ 種スターリング数」の値は, 漸化式により, 次の要領で求められる.
      $\begin{bmatrix} n \\ r \end{bmatrix}$:「第 $1$ 種スターリング数」
      $n$\$r$$\cdots$$r$$r+1$
      $\vdots$$\ddots$
      $n$$\cdots$$\begin{bmatrix} n \\ r \end{bmatrix}$$+n$$\begin{bmatrix} n \\ r+1 \end{bmatrix}$
      $||$
      $n+1$$\cdots$$\cdots$$\begin{bmatrix} n+1 \\ r+1 \end{bmatrix}$
      $\begin{Bmatrix} n \\ r \end{Bmatrix}$:「第 $2$ 種スターリング数」
      $n$\$r$$\cdots$$r$$r+1$
      $\vdots$$\ddots$
      $n$$\cdots$$\begin{Bmatrix} n \\ r \end{Bmatrix}$$+(r+1)$$\begin{Bmatrix} n \\ r+1 \end{Bmatrix}$
      $||$
      $n+1$$\cdots$$\cdots$$\begin{Bmatrix} n+1 \\ r+1 \end{Bmatrix}$

    問題《ベル数》

     $n$ 人を $1$ 人以上の組に分ける方法の総数を $B(n)$ で表し, $B(0) = 1$ と定める. このとき, $B(n+1) = \sum\limits_{k = 0}^n{}_n\mathrm C_kB(k)$ が成り立つことを示せ.
    実戦定理$2016/04/04$$2022/12/12$

    解答例

     特定の人物 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{aligned} 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{aligned}\] が成り立つ.

    参考

     互いに区別できる $n$ 個のものを $1$ 個以上のものからなる組に分ける方法の総数を「ベル数」(Bell number) と呼び, $B(n)$ で表す. 「ベル数」は「第 $2$ 種スターリング数」を使って $B(n) = \displaystyle\sum\limits_{k = 1}^n\begin{Bmatrix} n \\ k \end{Bmatrix}$ と表される. 初めの方の「ベル数」を求めると, \[\begin{aligned} B(1) &= 1, & B(2) &= 2, & B(3) &= 5, \\ B(4) &= 15, & B(5) &= 52, & B(6) &= 52, \\ B(7) &= 203, & B(8) &= 877, & B(9) &= 4140, \\ B(10) &= 21147, & \cdots & & & \end{aligned}\] のようになる.
    問題一覧 (場合の数)場合の数の基本 順列・円順列
    組合せ 組分け