二項定理
二項定理
定理《二項定理》
すべての正の整数 $n$ に対して,
\[ (x+y)^n = \sum_{k = 0}^n{}_n\mathrm C_k\,x^{n-k}y^k\]
が成り立つ.
証明
左辺 $(x+y)^n = (x+y)\cdots (x+y)$ を展開すると,
各かっこ $(x+y)$ において $x,$ $y$ のいずれかを選んで掛け合わせることで $x^{n-k}y^k$ $(0 \leqq k \leqq n)$ の形の項が得られ,
逆にこの形以外の項は出てこない.
$x^{n-k}y^k$ の形の項は, $n$ 個のかっこのうち $k$ 個から $y$ を選ぶ方法の総数 ${}_n\mathrm C_k$ だけあるから,
同類項をまとめると求める等式が得られる.
別証明: 数学的帰納法 (数学 B) と「パスカルの法則」を利用
こちらを参照.
問題《パスカルの法則と二項定理》
「パスカルの法則」
\[ {}_{n+1}\mathrm C_r = {}_n\mathrm C_{r-1}+{}_n\mathrm C_r \quad (n \geqq r > 0)\]
(こちらを参照) から二項定理
\[ (x+y)^n = \sum_{k = 0}^n{}_n\mathrm C_k\,x^{n-k}y^k \quad \cdots [*]\]
を導け.
解答例
- (i)
- $n = 1$ のとき. \[ (x+y)^1 = x+y = {}_1\mathrm C_0\,x^1y^0+{}_1\mathrm C_1\,x^0y^1\] であるから, $[*]$ が成り立つ.
- (ii)
- 与えられた正の整数 $n$ に対して $[*]$ が成り立つとする. このとき, \[\begin{aligned} (x+y)^{n+1} &= (x+y)^n(x+y) \\ &= (x+y)^nx+(x+y)^ny \\ &= \left(\sum_{k = 0}^n{}_n\mathrm C_k\,x^{n-k}y^k\right) x+\left(\sum_{k = 0}^n{}_n\mathrm C_k\,x^{n-k}y^k\right) y \\ &= \sum_{k = 0}^n{}_n\mathrm C_k\,x^{n+1-k}y^k+\sum_{k = 0}^n{}_n\mathrm C_k\,x^{n-k}y^{k+1} \\ &= \sum_{k = 0}^n{}_n\mathrm C_k\,x^{n+1-k}y^k+\sum_{k = 1}^{n+1}{}_n\mathrm C_{k-1}\,x^{n+1-k}y^k \\ &= x^{n+1}+\sum_{k = 1}^n({}_n\mathrm C_{k-1}+{}_n\mathrm C_k)x^{n+1-k}y^k+y^{n+1} \\ &= \sum_{k = 0}^{n+1}{}_{n+1}\mathrm C_k\,x^{n+1-k}y^k \end{aligned}\] となるから, $[*]$ において $n$ を $n+1$ に置き換えた等式が成り立つ.
参考
「パスカルの法則」と二項定理は同値な定理である.
二項定理から「パスカルの法則」を導く証明については, こちらを参照されたい.
問題《くくり出し公式とフェルマーの小定理》
$n$ を正の整数, $r$ を $0 < r < n$ なる整数, $p$ を素数, $k$ を $0 < k < p$ なる整数とする.
次のことを示せ.
- (1)
- $r\,{}_n\mathrm C_r = n\,{}_{n-1}\mathrm C_{r-1}$ が成り立つ.
- (2)
- ${}_p\mathrm C_k$ は $p$ の倍数である.
- (3)
- すべての整数 $a$ に対して, $a^p-a$ は $p$ の倍数である.
(参考: $2020$ 大阪教育大, $2014$ 富山大, $1978$ 京都大, $1974$ 早稲田大)
解答例
- (1)
- 二項係数の定義により, \[\begin{aligned} r\,{}_n\mathrm C_r &= r\cdot\frac{n!}{r!(n-r)!} \\ &= r\cdot\frac{n}{r}\cdot\frac{(n-1)!}{(r-1)!\{ (n-1)-(r-1)\} !} \\ &= n\,{}_{n-1}\mathrm C_{r-1} \end{aligned}\] が成り立つ.
- (2)
- (1) により, $k\,{}_p\mathrm C_k$ は $p$ の倍数である. また, $p$ は素数であり, $1 \leqq k \leqq p-1$ であるから, $p,$ $k$ は互いに素である. よって, ${}_p\mathrm C_k$ は $p$ の倍数である.
- (3)
- (I)
- $a \geqq 0$ のとき.
$a$ に関する数学的帰納法で示す.
- (i)
- $a = 0$ のとき. $0^p-0 = 0$ から, $a^p-a$ は $p$ の倍数である.
- (ii)
- 与えられた非負整数 $a$ に対して $a^p-a$ が $p$ の倍数であるとする. このとき, (2) により \[\begin{aligned} &(a+1)^p-(a+1) \\ &= \left( a^p+\sum\limits_{k = 1}^{p-1}{}_p\mathrm C_k\,a^{p-k}+1\right) -(a+1) \\ &= (a^p-a)+\sum\limits_{k = 1}^{p-1}{}_p\mathrm C_k\,a^{p-k} \end{aligned}\] は $p$ の倍数である.
- (II)
- $a < 0,$ $p \geqq 3$ のとき. $p$ は奇数であるから \[ (-a)^p-(-a) = -(a^p-a)\] であり, これは (i) から $p$ の倍数である. よって, $a^p-a$ も $p$ の倍数である.
- (III)
- $a < 0,$ $p = 2$ のとき. 連続する $2$ 個の整数の積 \[ a^2-a = a(a-1)\] は偶数であるから, $a^p-a$ は $p$ の倍数である.
別解
- (1)
- $n$ 人から $r$ 人を選び, その $r$ 人からリーダー $1$ 人を選ぶ方法は, 全部で ${}_n\mathrm C_r\cdot r$ 通りある. 同様にするには, $n$ 人からリーダー $1$ 人 L を選んでおき, L を除く $n-1$ 人から残りの $r-1$ 人を選べばよいから, これは $n\,{}_{n-1}\mathrm C_{r-1}$ に等しい. よって, $r\,{}_n\mathrm C_r = n\,{}_{n-1}\mathrm C_{r-1}$ が成り立つ.
参考
- 二項係数 ${}_n\mathrm C_r$ は, 世界的には, $\displaystyle\binom{n}{r}$ で表すことが多い. (1) の等式は, $\displaystyle\binom{n}{r} = \frac{n}{r}\binom{n-1}{r-1}$ の形に変形できるから, しばしば二項係数に関する「くくり出し公式」と呼ばれる.
- (3) で示した命題は,「フェルマーの小定理」(Fermat's little theorem) と呼ばれ, 整数論の諸定理の証明に使われている.
- この定理の対偶から, ある整数 $a$ に対して $a^n-a$ が $n$ の倍数にならないような $1$ より大きい整数 $n$ は合成数であることが言える. これを利用して素数の候補を見つける方法は「フェルマー・テスト」として知られている.
問題《フロベニウス写像》
整数 $a,$ $b$ と素数 $p$ に対して, $(a+b)^p-a^p-b^p$ は $p$ で割り切れることを示せ.
解答例
$0 < k < p$ なる整数 $k$ に対して, $k!$ と $(p-k)!$ は $p$ で割り切れないから, ${}_p\mathrm C_k = \dfrac{p!}{k!(p-k)!}$ は $p$ で割り切れる.
よって,
\[ (a+b)^p-a^p-b^p = \sum _{k = 1}^{p-1}{}_p\mathrm C_ka^{n-k}b^k\]
は $p$ で割り切れる.
参考
整数を素数 $p$ で割った余りの集合として定義される「$p$ 元体」(field of order $p$) という数の世界において, 関数 $f(x) = x^p$ は「フロベニウス写像」(Frobenius map) と呼ばれ, 基本的な役割を果たす.
本問で示したことは, 加法に関して「準同型写像」(homomorphism) であるという $f(x)$ の性質
\[ f(x_1+x_2) = f(x_1)+f(x_2)\]
に対応している.
問題《二項係数の和と交代和》
$n$ を正の整数とする.
二項係数について
(1) $\displaystyle\sum_{k = 0}^n{}_n\mathrm C_k = 2^n$ (2) $\displaystyle\sum_{k = 0}^n(-1)^k{}_n\mathrm C_k = 0$
(3) $\displaystyle\sum_{k = 0}^nk\,{}_n\mathrm C_k = n\cdot 2^{n-1}$
が成り立つことを示せ.
(1) $\displaystyle\sum_{k = 0}^n{}_n\mathrm C_k = 2^n$ (2) $\displaystyle\sum_{k = 0}^n(-1)^k{}_n\mathrm C_k = 0$
(3) $\displaystyle\sum_{k = 0}^nk\,{}_n\mathrm C_k = n\cdot 2^{n-1}$
が成り立つことを示せ.
解答例
- (1)
- 二項定理の等式 \[ (x+y)^n = \sum_{k = 0}^n{}_n\mathrm C_k\,x^{n-k}y^k \quad \cdots [*]\] に $x = y = 1$ を代入すると, \[ 2^n = (1+1)^n = \sum_{k = 0}^n{}_n\mathrm C_k\cdot 1^{n-k}\cdot 1^k = \sum_{k = 0}^n{}_n\mathrm C_k\] が得られる.
- (2)
- $[*]$ に $x = 1,$ $y = -1$ を代入すると, \[ 0 \!=\! (1\!-\!1)^n \!=\! \sum_{k = 0}^n{}_n\mathrm C_k\!\cdot\!1^{n-k}\!\cdot\!(-1)^k \!=\! \sum_{k = 0}^n(-1)^k{}_n\mathrm C_k\] が得られる.
- (3)
- \[ S = \sum_{k = 0}^nk\,{}_n\mathrm C_k\] とおくと, \[ S = \sum_{k = 0}^nk\,{}_n\mathrm C_{n-k} = \sum_{k = 0}^n(n-k)\,{}_n\mathrm C_k\] となるので, \[\begin{aligned} 2S &= \sum_{k = 0}^nk\,{}_n\mathrm C_k+\sum_{k = 0}^n(n-k)\,{}_n\mathrm C_k \\ &= \sum_{k = 0}^n\{ k+(n-k)\}{}_n\mathrm C_k \\ &= n\sum_{k = 0}^n{}_n\mathrm C_k = n\cdot 2^n \end{aligned}\] から \[ S = n\cdot 2^{n-1}\] が得られる.
別解 1: 組合せを利用
$1$ 以上 $n$ 以下の整数全体からなる集合 $\{ 1,\cdots,n\}$ を $A$ とおく.
- (1)
- $A$ の部分集合の個数は, $k$ 個の要素からなる部分集合の個数の和と考えると $\displaystyle\sum_{k = 0}^n{}_n\mathrm C_k$ と表され, 各整数が部分集合に属するか否かを考えると $2^n$ と表される. よって, 求める等式が成り立つ.
- (2)
- $A$ の偶数個の要素からなる部分集合の個数, 奇数個の要素からなる部分集合の個数は, $2k,$ $2k+1$ 個の要素からなる部分集合の個数の和と考えるとそれぞれ ${}_n\mathrm C_0+{}_n\mathrm C_2+\cdots,$ ${}_n\mathrm C_1+{}_n\mathrm C_3+\cdots$ と表され, $1$ から $n-1$ までの整数が部分集合に属するか否かを考える ($n$ はそれに応じて部分集合に属するか否かが自動的に決まると考える) とともに $2^{n-1}$ と表される. よって, \[{}_n\mathrm C_0+{}_n\mathrm C_2+\cdots = {}_n\mathrm C_1+{}_n\mathrm C_3+\cdots = 2^{n-1}\] から, $\displaystyle\sum_{k = 0}^n(-1)^k{}_n\mathrm C_k = 0$ が成り立つ.
- (3)
- $A$ の空集合でない部分集合をとり, さらにその中から $1$ 個の要素 (代表と呼ぶ) を選ぶ方法の総数は, $k$ 個の要素からなる部分集合とその代表の組の個数の和と考えると $\displaystyle\sum_{k = 1}^nk\,{}_n\mathrm C_k = \sum_{k = 0}^nk\,{}_n\mathrm C_k$ と表され, 代表となる要素を選んでからそれ以外の $n-1$ 個の整数が部分集合に属するか否かを考えると $n\cdot 2^{n-1}$ と表される. よって, 求める等式が成り立つ.
別解 2: 二項係数の関係式を利用
- (1)
- (i)
- $n = 1$ のとき, ${}_1\mathrm C_0+{}_1\mathrm C_1 = 1+1 = 2 = 2^1$ から, 等式が成り立つ.
- (ii)
- $n = m$ ($m$: 正の整数) のとき等式が成り立つとすると, 「パスカルの法則」${}_n\mathrm C_r+{}_n\mathrm C_{r+1} = {}_{n+1}\mathrm C_{r+1}$ $(0 \leqq r < n)$ により, \[\begin{aligned} &{}_{m+1}\mathrm C_0+{}_{m+1}\mathrm C_1+\cdots +{}_{m+1}\mathrm C_m+{}_{m+1}\mathrm C_{m+1} \\ &= {}_{m+1}\mathrm C_0+({}_m\mathrm C_0+{}_m\mathrm C_1) \\ &\qquad +\cdots +({}_m\mathrm C_{m-1}+{}_m\mathrm C_m)+{}_{m+1}\mathrm C_{m+1} \\ &= {}_m\mathrm C_0+({}_m\mathrm C_0+{}_m\mathrm C_1) \\ &\qquad +\cdots +({}_m\mathrm C_{m-1}+{}_m\mathrm C_m)+{}_m\mathrm C_m \\ &= 2({}_m\mathrm C_0+\cdots +{}_m\mathrm C_m) \\ &= 2\cdot 2^m = 2^{m+1} \end{aligned}\] となるから, $n = m+1$ のとき等式が成り立つ.
- (3)
- $k\,{}_n\mathrm C_k = n\,{}_{n-1}\mathrm C_{k-1}$ $(1 \leqq k \leqq n)$ と (1) により, \[\begin{aligned} \sum_{k = 0}^nk\,{}_n\mathrm C_k &= \sum_{k = 1}^nk\,{}_n\mathrm C_k = \sum_{k = 1}^nn\,{}_{n-1}\mathrm C_{k-1} \\ &= n\sum_{k = 0}^{n-1}\,{}_{n-1}\mathrm C_k = n\cdot 2^{n-1} \end{aligned}\] が成り立つ.
別解 3: 合成関数の微分法を利用 (数学 III)
- (3)
- $(1+x)^n = 1+\displaystyle\sum_{k = 1}^n{}_n\mathrm C_kx^k$ の両辺を $x$ で微分すると \[ n(1+x)^{n-1} = \sum_{k = 1}^nk\,{}_n\mathrm C_kx^{k-1}\] となるから, $x = 1$ を代入すると \[ n\cdot 2^{n-1} = \sum_{k = 1}^nk\,{}_n\mathrm C_k = \sum_{k = 0}^nk\,{}_n\mathrm C_k\] が得られる.
問題《メビウス関数の基本公式》
正の整数 $n$ が
と素因数分解されるとする.
| $n = p_1{}^{e_1}\cdots p_r{}^{e_r}$ ($p_1,$ $\cdots,$ $p_r$: 相異なる素数, $e_1,$ $\cdots,$ $e_r$: 正の整数) $\cdots [\ast ]$ |
- $(e_1,\cdots,e_r) \neq (1,\cdots,1)$ のとき $\mu (n) = 0$
- $(e_1,\cdots,e_r) = (1,\cdots,1)$ のとき $\mu (n) = (-1)^r$
- (1)
- 相異なる $k$ 個の素数の積であるような $n$ の正の約数の個数を求めよ.
- (2)
- $n > 1$ のとき, $n$ のすべての正の約数 $d$ にわたる $\mu (d)$ の和 $S$ の値を求めよ.
解答例
- (1)
- 求める個数は, $p_1,$ $\cdots,$ $p_r$ から $k$ 個を選ぶ組合せの総数に等しく, ${}_r\mathrm C_k$ である.
- (2)
- $n$ の正の約数 $d$ について, 定義により $d$ が $1$ 以外の平方数で割り切れるとき $\mu (d) = 0$ であるから, $S$ は相異なる素数の積に分解されるような $d$ にわたる $\mu (d)$ の和に等しい. このような $d$ のうち $k$ 個の素数の積であるものは ${}_r\mathrm C_k$ 個あり, $\mu (d) = (-1)^k$ を満たすから, 求める和は \[ S = \sum_{k = 0}^r{}_r\mathrm C_k\,(-1)^k = \{ 1+(-1)\} ^r = 0\] である.
参考
- 関数 $\mu (n)$ を「メビウス関数」(Möbius function) と呼ぶ.
- 本問の公式を使って, 正の整数全体を定義域とする複素数値関数 $f(n),$ $g(n)$ について,「メビウスの反転公式」(Möbius inversion formula) \[\begin{aligned} &g(n) = \sum_{0 < d \mid n}f(d) \\ &\Longrightarrow f(n) = \sum_{0 < d \mid n}\mu\left(\frac{n}{d}\right) g(d) = \sum_{0 < d \mid n}\mu (d)f\left(\frac{n}{d}\right) \end{aligned}\] の成り立つことが示される (数論で重要). ここで, $\displaystyle\sum_{0 < d \mid n}$ は $n$ の正の約数全体にわたる和を表す. 例えば, 正の整数 $m$ に対して \[\sigma _m(n) = \sum_{0 < d \mid n}d^m\] で定まる「約数関数」$\sigma _m(n)$ について,「メビウスの反転公式」により \[\sum_{0 < d \mid n}\mu\left(\frac{n}{d}\right) \sigma _m(d) = n^m\] の成り立つことがわかる.
- 「メビウス関数」の他の性質については, こちらを参照.
問題《ファンデルモンドの畳み込み》
- (1)
- $m,$ $n$ を正の整数とし, $r$ を $0 \leqq r \leqq m+n$ なる整数とする. $(1+x)^{m+n}$ の展開式を考えることにより, \[\sum_{k = 0}^r{}_m\mathrm C_k\cdot {}_n\mathrm C_{r-k} = {}_{m+n}\mathrm C_r\] が成り立つことを示せ.
- (2)
- $n$ を正の整数とする. \[\sum_{k = 0}^n{}_n\mathrm C_k{}^2 = {}_{2n}\mathrm C_n\] が成り立つことを示せ.
解答例
- (1)
- \[ (1+x)^{m+n} = (1+x)^m(1+x)^n\] の各べきを展開すると \[\begin{aligned} \sum\limits_{r = 0}^{m+n}{}_{m+n}\mathrm C_r\,x^r &= \left(\sum\limits_{k = 0}^m{}_m\mathrm C_k\,x^k\right)\left(\sum\limits_{l = 0}^n{}_n\mathrm C_l\,x^l\right) \\ &= \sum\limits_{r = 0}^{m+n}\left(\sum\limits_{k+l = r}{}_m\mathrm C_k\cdot {}_n\mathrm C_l\right) x^r \\ &= \sum\limits_{r = 0}^{m+n}\left(\sum\limits_{k = 0}^r{}_m\mathrm C_k\cdot {}_n\mathrm C_{r-k}\right) x^r \end{aligned}\] となる. ただし, 第 $2$ 行, 第 $2$ のシグマ記号は $k+l = r,$ $0 \leqq k \leqq m,$ $0 \leqq l \leqq n$ なる整数 $k,$ $l$ にわたる和を意味する. 両辺の各項の係数を比較すると, 求める等式が得られる.
- (2)
- (1) において $m = n = r$ とすると, \[\begin{aligned} \sum_{k = 0}^n{}_n\mathrm C_k\cdot {}_n\mathrm C_{n-k} &= {}_{n+n}\mathrm C_n \\ \sum_{k = 0}^n{}_n\mathrm C_k{}^2 &= {}_{2n}\mathrm C_n \end{aligned}\] が得られる.
別解
- (2)
- 白色の札 $n$ 枚と黒色の札 $n$ 枚に, それぞれ $1$ から $n$ までの番号をふる. これら $2n$ 枚の札から $n$ 枚を取り出す場合の数は, ${}_{2n}\mathrm C_n$ である. 一方, これは, 白色の札から $k$ 枚, 黒色の札から $n-k$ 枚を取り出す場合の数 ${}_n\mathrm C_k\cdot {}_n\mathrm C_{n-k} = {}_n\mathrm C_k{}^2$ の総和と考えると, $\displaystyle\sum_{k = 0}^n{}_n\mathrm C_k{}^2$ と表される. よって, 求める等式が成り立つ.
参考
(1)の等式は「ファンデルモンドの畳み込み」(Vandermonde's convolution) として知られている.
問題《二項係数を含む多項式の和》
$n$ を正の整数とする.
- (1)
- $\displaystyle\sum_{k = 0}^n{}_n\mathrm C_kx^k(1-x)^{n-k} = 1$
- (2)
- $\displaystyle\sum_{k = 0}^nk\,{}_n\mathrm C_kx^k(1-x)^{n-k} = nx$
- (3)
- $\displaystyle\sum_{k = 0}^nk(k-1)\,{}_n\mathrm C_kx^k(1-x)^{n-k} = n(n-1)x^2$
解答例
- (1)
- 二項定理により, \[\sum_{k = 0}^n{}_n\mathrm C_kx^k(1-x)^{n-k} = \{ x+(1-x)\} ^n = 1^n = 1\] が成り立つ.
- (2)
- 二項係数の「くくり出し公式」と (1) の結果により, \[\begin{aligned} &\sum_{k = 0}^nk\,{}_n\mathrm C_kx^k(1-x)^{n-k} = \sum_{k = 0}^nn\,{}_{n-1}\mathrm C_{k-1}x^k(1-x)^{n-k} \\ &= nx\sum_{k = 0}^n{}_{n-1}\mathrm C_{k-1}x^{k-1}(1-x)^{(n-1)-(k-1)} \\ &= nx\cdot 1 = nx \end{aligned}\] が成り立つ.
- (3)
- 二項係数の「くくり出し公式」と (2) の結果により, \[\begin{aligned} &\sum_{k = 0}^nk(k-1)\,{}_n\mathrm C_kx^k(1-x)^{n-k} \\ &= \sum_{k = 1}^nk(k-1)\,{}_n\mathrm C_kx^k(1-x)^{n-k} \\ &= \sum_{k = 1}^nn(k-1)\,{}_{n-1}\mathrm C_{k-1}x^k(1-x)^{n-k} \\ &= nx\sum_{k = 1}^n(k-1)\,{}_{n-1}\mathrm C_{k-1}x^{k-1}(1-x)^{(n-1)-(k-1)} \\ &= nx\sum_{l = 0}^{n-1}l\,{}_{n-1}\mathrm C_lx^l(1-x)^{(n-1)-l} \\ &= nx\cdot (n-1)x = n(n-1)x^2 \end{aligned}\] が成り立つ.
参考
本問の結果は, 次の「ワイエルシュトラスの近似定理」(Weierstrass approximation theorem) の証明に使われる.
$f(x)$ を閉区間 $[a,b]$ で定義された実数値連続関数とする.
このとき, 任意の正の数 $\varepsilon$ に対して,
\[ |f(x)-p(x)| < \varepsilon \quad (x \in [a,b])\]
なる実数係数多項式 $p(x)$ が存在する.
問題《第 $1$ 種スターリング数と二項係数の関係式》
$n,$ $r$ を $n \geqq r$ なる非負整数とする.
$x$ の $n$ 次関数 $x^{\bar n}$ を $x^{\bar 0} = 1,$ $x^{\overline{n+1}} = x^{\overline n}(x+n)$ で定め,
\[ x^{\bar n} = \sum_{k = 0}^ns(n,k)x^k\]
とおく.
\[ s(n+1,r+1) = \sum_{k = r}^ns(n,k)\,{}_k\mathrm C_r\]
が成り立つことを示せ.
(参考: $2023$ 名古屋大)
解答例
$x^{\overline{n+1}} = x(x+1)^{\bar n},$ 二項定理により
\[\begin{aligned}
\sum_{k = 0}^{n+1}s(n+1,k)x^k &= x\sum_{k = 0}^ns(n,k)(x+1)^k \\
&= x\sum_{k = 0}^ns(n,k)\sum_{j = 0}^k{}_k\mathrm C_j\,x^j \\
&= \sum_{k = 0}^n\sum_{j = 0}^ks(n,k)\,{}_k\mathrm C_j\,x^{j+1}
\end{aligned}\]
が成り立つから, $x^{r+1}$ の係数を比較すると
\[ s(n+1,r+1) = \sum_{k = r}^ns(n,k)\,{}_k\mathrm C_r\]
が得られる.
参考
- $x^{\bar n}$ を $x$ の「上昇階乗べき」と呼ぶ.
- $x^{\bar n} = \displaystyle\sum_{k = 0}^ns(n,k)x^k$ の係数 $s(n,k)$ を「第 $1$ 種スターリング数」(Stirling number of the first kind) と呼ぶ. 世界的には $\begin{bmatrix} n \\ k \end{bmatrix}$ という記号で表すことが多い.
- $\begin{bmatrix} n \\ r \end{bmatrix}$ は, 互いに区別できる $n$ 個のものを $r$ 個の組に分けて各組で $1$ つの円順列を作る方法の総数に等しい (こちらを参照). 初めの方の「第 $1$ 種スターリング数」を求めると, 次の表のようになる.
| $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$ |
多項定理
問題《多項定理の項の係数とフェルマーの小定理》
$p$ を素数, $n$ を正の整数とする.
次のことを示せ.
- (1)
- $(x_1+\cdots +x_n)^p-(x_1{}^p+\cdots +x_n{}^p)$ を展開して整理した式における各項の係数は $p$ で割り切れる.
- (2)
- $n^p-n$ は $p$ で割り切れる.
解答例
- (1)
- \[ (x_1+\cdots +x_n)^p-(x_1{}^p+\cdots +x_n{}^p) \quad \cdots [1]\] を展開して整理した式における各項の係数は, $0$ 以上 $p-1$ 以下の整数 $r_1,$ $\cdots,$ $r_n$ を用いて \[\frac{p!}{r_1!\cdots r_n!} = p\cdot\frac{(p-1)!}{r_1!\cdots r_n!} \quad \cdots [2]\] と表される. ここで, $r_1!,$ $\cdots,$ $r_n!$ は $p$ と互いに素であるから, $[2]$ は $p$ の倍数である.
- (2)
- (1) により, $[1]$ に $x_1 = \cdots = x_n = 1$ を代入した値 $n^p-n$ は, $p$ の倍数の和の形に表されるから, $p$ の倍数である.