初等整数論/パスカルの三角形

これはパスカルの三角形と呼ばれる三角形である。

端が全て 1 で、一段下の数字は上とずれている。一段下の数字をどう決めるかというと、上の左右2つの数字を足したものを書くのである。

例えば五段目の左から三番目の数は、四段目の左から二番目と三番目の数を足したもの、つまり$3+3=6$ となっている。六段目の左からニ番目の数は、五段目の左から一番目の数に二番目の数を足したもの、つまり$1+4=5$。

このような単純な仕組みで書かれる三角形だが、非常に奥深い性質を備えているのである。

組み合わせ論

いきなり全く関係ない話に飛ぶのかと思われるかも知れないが少々お付き合いいただきたい。

n個のものを並べる

3個のものを並べるのには何通りあるかというと、まず3つの中から一つ選んで一番目にするのには 3 通り、その後残った2つの中から一つ選んで二番目にするのは 2 通り、最後に残った一つを選んで最後に配置するのはもちろん 1 通り、よってこれらをかけて、全部で

$3\cdot 2\cdot 1=6$

で 6 通り。

他の考え方としては、全て書き出す仮定で規則を見つけるということである。3つくらいなら書きだすのは簡単である。

$(A,B,C),(A,C,B),(B,A,C),(B,C,A),(C,A,B),(C,B,A)$

の 6 通りである。

これは次のようにも考えられる。

2 つのものがあるとき、並べるのは 2 通り。新しくもう一つ入れるには、一番目に入れるか、二番目に入れるか、三番目に入れるか、の 3 通りが考えられる。

よって、$3\cdot 2=6$

この論法は拡張性があって、n 個のものを並べるのに N 通りあるのならば、n+1 個のものを並べるのには、一番目に入れるか、二番目に入れるか、三番目に入れるか、・・・、n番目に入れるか、(n+1)番目に入れるか、の n+1 通り考えられるので、N・(n+1) 通りである、と分かる。

今述べたことをまとめると、n 個のものを並べる通りの数を $c(n)$ と表すことにすると、$c(n+1)=c(n)(n+1)$ となる、ということを言っているのである。

もちろん、$c(1)=1$ である。こうして、何通りあるかを簡単に計算できるようになった。それは次のような関数で表せる。

$\{\begin{array}{cc}c(1)& =1\\ c(n+1)& =c(n)(n+1)\end{array}$

この関数は階乗と呼ばれ、$c(n)=n!$ と書く。また、$0!=1$ と定義する。こうすることで色々と都合が良いのである。

例

$5!=5\cdot 4\cdot 3\cdot 2\cdot 1=120$

n 個の中から m 個選んで並べる

n 個の中から m 個選んで並べる、というのは、後ろの n-m 個の並び順がどうであろうと、前のものが同じならば問わないということであるので、$\frac{n!}{(n-m)!}$ という式で表せる。

これを、

${}_n{\mathrm{P}}_m=\frac{n!}{(n-m)!}$

という関数で表す。もちろん、n ≧ のときだけ意味を持つ。

n 個の中から m 個選ぶ

n 個の中から m 個選ぶというのは、n 個の中から m 個選んで並べた際に、その順番は問わないということだから、

$\frac{{}_n{\mathrm{P}}_m}{m!}=\frac{n!}{m!(n-m)!}$ と表せる。

これを、

${}_n{\mathrm{C}}_m=\frac{n!}{m!(n-m)!}$ という関数で表す。他にも、$(\genfrac{}{}{0ex}{}{n}{m})$ で表すこともある。またこれを二項係数ということがある。その理由は後に分かるだろう。

組み合わせとパスカルの三角形の関係

組み合わせの関数、P, C の意味を見れば整数であることは自明だろう。P, C が整数になることの証明は興味のある読者に任せる。

さて、ここで色々と計算をしてみる。

$\begin{array}{cc}{}_0{\mathrm{C}}_0& =1\\ {}_1{\mathrm{C}}_0& =1,{}_1{\mathrm{C}}_1=1\\ {}_2{\mathrm{C}}_0& =1,{}_2{\mathrm{C}}_1=2,{}_2{\mathrm{C}}_2=1\\ {}_3{\mathrm{C}}_0& =1,{}_3{\mathrm{C}}_1=3,{}_3{\mathrm{C}}_2=3,{}_3{\mathrm{C}}_3=1\\ {}_4{\mathrm{C}}_0& =1,{}_4{\mathrm{C}}_1=4,{}_4{\mathrm{C}}_2=6,{}_4{\mathrm{C}}_3=4,{}_4{\mathrm{C}}_4=1\\ {}_5{\mathrm{C}}_0& =1,{}_5{\mathrm{C}}_1=5,{}_5{\mathrm{C}}_2=10,{}_5{\mathrm{C}}_3=10,{}_5{\mathrm{C}}_4=5,{}_5{\mathrm{C}}_5=1\\ \end{array}$

これの結果だけを書いて、

$\begin{array}{cc}& 1\\ & 11\\ & 121\\ & 1331\\ & 14641\\ & 15101051\\ \end{array}$

と、ここまで書けば察しがつくだろう。そう、二項係数はパスカルの三角形をなすのである。

しかし、これはまだ単なる推測に過ぎない。そのためには、パスカルの三角形と同じ性質を持つことを証明しなければならない。

$\begin{array}{cc}{}_m{\mathrm{C}}_0& =\frac{m!}{0!(m-0)!}\\ & =\frac{m!}{1\cdot m!}\\ & =1\\ {}_m{\mathrm{C}}_m& =\frac{m!}{m!(m-m)!}\\ & =\frac{m!}{m!\cdot 1}\\ & =1\end{array}$

つまり、端の数は全て 1 である。

また、${}_n{\mathrm{C}}_m+{}_n{\mathrm{C}}_{m+1}={}_{n+1}{\mathrm{C}}_{m+1}\cdots (1)$ が成り立つことを示す。

$\begin{array}{cc}{}_n{\mathrm{C}}_m+{}_n{\mathrm{C}}_{m+1}& =\frac{n!}{m!(n-m)!}+\frac{n!}{(m+1)!(n-(m+1))!}\\ & =\frac{n!}{m!(n-m-1)!}(\frac{1}{n-m}+\frac{1}{m+1})\\ & =\frac{n!}{m!(n-m-1)!}\left(\frac{(n-m)+(m+1)}{(n-m)(m+1)}\right)\\ & =\frac{n!(n+1)}{m!(m+1)(n-m-1)!(n-m)}\\ & =\frac{(n+1)!}{(m+1)!(n-m)!}\\ & =\frac{(n+1)!}{(m+1)!((n+1)-(m+1))!}\\ & ={}_{n+1}{\mathrm{C}}_{m+1}\\ \end{array}$

よって、パスカルの三角形の性質を備え、パスカルの三角形の各項を二項係数で表すことができることが証明された。

二項定理

さて、$(a+b{)}^n$ を展開したときの a, b の各係数について考察していこう。まずは小さい数で試してみる。

$\begin{array}{c}(a+b{)}^0=1\\ (a+b{)}^1& =1a+1b\\ (a+b{)}^2& =1a^2+2ab+1b^2\\ (a+b{)}^3& =1a^3+3a^{2}b+3a{b}^2+1b^3\\ (a+b{)}^4& =1a^4+4a^{3}b+6a^2{b}^2+4a{b}^3+1b^4\\ \end{array}$

テンプレート:Wikipedia おそらくここまで書けば分かるだろう。これもパスカルの三角形になっているのである。先ほどの二項係数との関係と合わせて、次の定理（二項定理）が成り立つことが予想できる。

定理

$(x+y{)}^n=(\genfrac{}{}{0ex}{}{n}{0})x^n{y}^0+(\genfrac{}{}{0ex}{}{n}{1})x^{n-1}{y}^1+(\genfrac{}{}{0ex}{}{n}{2})x^{n-2}{y}^2+\cdots +(\genfrac{}{}{0ex}{}{n}{n-1})x^1{y}^{n-1}+(\genfrac{}{}{0ex}{}{n}{n})x^0{y}^n$

証明
これを n に関する数学的帰納法で証明する。

n = 0 のときは自明。n = 1 のときは、$(x+y{)}^1=x+y=(\genfrac{}{}{0ex}{}{1}{0})x+(\genfrac{}{}{0ex}{}{0}{1})y(\because (\genfrac{}{}{0ex}{}{1}{0})=(\genfrac{}{}{0ex}{}{1}{1})=1)$ より成り立つ。

仮に n = k のとき成り立っていたとする。すると、

$\begin{array}{cc}(x+y{)}^{k+1}& =(x+y{)}^k(x+y)\\ & =((\genfrac{}{}{0ex}{}{k}{0})x^k{y}^0+(\genfrac{}{}{0ex}{}{k}{1})x^{k-1}{y}^1+\cdots +(\genfrac{}{}{0ex}{}{k}{k-1})x^1{y}^{k-1}+(\genfrac{}{}{0ex}{}{k}{k})x^0{y}^k)(x+y)\\ & =((\genfrac{}{}{0ex}{}{k}{0})x^{k+1}{y}^0+(\genfrac{}{}{0ex}{}{k}{1})x^k{y}^1+\cdots +(\genfrac{}{}{0ex}{}{k}{k-1})x^2{y}^{k-1}+(\genfrac{}{}{0ex}{}{k}{k})x^1{y}^k)\\ & +((\genfrac{}{}{0ex}{}{k}{0})x^k{y}^1+(\genfrac{}{}{0ex}{}{k}{1})x^{k-1}{y}^2+\cdots +(\genfrac{}{}{0ex}{}{k}{k-1})x^1{y}^k+(\genfrac{}{}{0ex}{}{k}{k})x^0{y}^{k+1})\\ & =(\genfrac{}{}{0ex}{}{k}{0})x^{k+1}{y}^0+((\genfrac{}{}{0ex}{}{k}{1})+(\genfrac{}{}{0ex}{}{k}{0}))x^k{y}^1+((\genfrac{}{}{0ex}{}{k}{2})+(\genfrac{}{}{0ex}{}{k}{1}))x^{k-1}{y}^2+\cdots \\ & +((\genfrac{}{}{0ex}{}{k}{k-1})+(\genfrac{}{}{0ex}{}{k}{k-2}))x^2{y}^{k-1}+((\genfrac{}{}{0ex}{}{k}{k})+(\genfrac{}{}{0ex}{}{k}{k-1}))+(\genfrac{}{}{0ex}{}{k}{k})x^0{y}^{k+1}\\ & =(\genfrac{}{}{0ex}{}{k+1}{0})x^{k+1}{y}^0+(\genfrac{}{}{0ex}{}{k+1}{1})x^k{y}^1+\cdots +(\genfrac{}{}{0ex}{}{k+1}{k})x^1{y}^k+(\genfrac{}{}{0ex}{}{k+1}{k+1})x^0{y}^{k+1}\\ & (\because (1),(\genfrac{}{}{0ex}{}{k}{k})=(\genfrac{}{}{0ex}{}{l}{l})=(\genfrac{}{}{0ex}{}{k}{0})=(\genfrac{}{}{0ex}{}{l}{0})=1,)\end{array}$

より、k+1 のときも正しい。

以上より、数学的帰納法によって証明される。

多角数

さて、今度はパスカルの三角形を斜めに見てみよう。左から二番目の数を抜き出してみると、

1, 2, 3, 4 ...

となっている。では左から三番目の数はどうなっているかというと、

1, 3, 6, 10, ...

となっている。これらは、

1, 1+2, 1+2+3, 1+2+3+4, ...

となっている。また、次のような図形との関連がある。

三角数

1		3		6		10		15		21

これは三角数と呼ばれる。

さて、三角数の一般項はどうなっているのだろうか。三角数はある数以下の自然数の総和である。すなわち、等差数列の問題に帰着できる。

$\begin{array}{cc}S& =1+2+3+\cdots +(n-1)+n\\ S& =n+(n-1)+(n-2)+\cdots +2+1\\ \end{array}$

$\therefore 2S=n(n+1)⟺S=\frac{n(n+1)}{2}$

四角数

四角数は図を書いてみれば分かるが、そのまま平方数である。

ここで n 角数の m 項目を ${\mathrm{P}}_{n}m$ と書くことにする。例えば、三角数の 4 項目は 10 であるから、

${\mathrm{P}}_{3}4=10$

${\mathrm{P}}_{3}n=\frac{1}{2}n(n+1)$ であることは先ほど証明した通りである。

1		4		9		16

このように書いてみれば分かる通り、

${\mathrm{P}}_{4}n=n^2$

五角数

1		5		12		22

ここで、次のことが簡単に分かる。

${\mathrm{P}}_{5}1=1,{\mathrm{P}}_5(n+1)={\mathrm{P}}_{5}n+3n+1$

二番目の式は、次の五角形になるときに、(一辺の長さ + 1) × 3 - (重なって足してしまった頂点の数) = (n + 1) × 3 - 2 = 3n + 1

もしくは、n ずつなぞると 3 回なぞれて、最後に一個残るから、3n + 1

の分だけ増えるということから導ける。よって、五角数の一般項は、次の式で与えられる。

$\begin{array}{cc}{\mathrm{P}}_{5}n& ={\mathrm{P}}_{5}1+\sum _k^{n-1}(3k+1)\\ & =1+3\sum _k^{n-1}i+\sum _{ik}^{n-1}1\\ & =1+\frac{3}{2}(n-1+1)(n-1)+(n-1)\\ & =\frac{3n^2-3n+2n}{2}\\ & =\frac{n(3n-1)}{2}\\ \end{array}$

六角数

1		6		15		28

五角数のときと同様に考えると、

${\mathrm{P}}_{6}1=1,{\mathrm{P}}_6(n+1)={\mathrm{P}}_{6}n+(4n+1)$

したがって、六角数の一般項は、

$\begin{array}{cc}{\mathrm{P}}_{6}n& ={\mathrm{P}}_{6}1+\sum _k^{n-1}(4k+1)\\ & =1+4su{m}_k^{n-1}k+su{m}_k^{n-1}1\\ & =1+2(n-1)n+(n-1)\\ & =n+2(n-1)n\\ & =n(2n-1)\end{array}$

m角数

さて、今度は一般の場合を考えてみよう。

第一項はもちろん 1 である。${\mathrm{P}}_{m}1=1.$

n+1 項目は n 項目から (m-2)n + 1 分だけ増える。すなわち、${\mathrm{P}}_m(n+1)=(m-2)n+1$

したがって、m 角数の n 項目の一般項は、次の式で与えられる :

$\begin{array}{cc}{\mathrm{P}}_{m}n& ={\mathrm{P}}_{m}1+\sum _k^{n-1}((m-2)k+1)\\ & =1+(m-2)\sum _k^{n-1}k+\sum _k^{n-1}1\\ & =1+\frac{m-2}{2}(n-1)n+(n-1)\\ & =\frac{1}{2}\{2+(m-2)(n-1)\}\\ & =\frac{n}{2}\{2+mn-2n-m+2)\\ & =\frac{n}{2}(mn-2n-m+4)\\ & =\frac{(m-2)n^2-(m-4)n}{2}\end{array}$

このようにして、多角数の一般項が得られた。

多角数定理

フェルマーの最終定理で知られる、フェルマーは次のような定理を予想した。

（多角数定理） 任意の数は p 個以下の p 角数の和で表せる。

フェルマーは p = 3 の場合を証明した。p = 4 の場合は四平方の定理として知られる。一般の場合はコーシーによって証明された。