初等整数論/パスカルの三角形
これはパスカルの三角形と呼ばれる三角形である。
端が全て 1 で、一段下の数字は上とずれている。一段下の数字をどう決めるかというと、上の左右2つの数字を足したものを書くのである。
例えば五段目の左から三番目の数は、四段目の左から二番目と三番目の数を足したもの、つまり 3 + 3 = 6 {\displaystyle 3+3=6} となっている。六段目の左からニ番目の数は、五段目の左から一番目の数に二番目の数を足したもの、つまり 1 + 4 = 5 {\displaystyle 1+4=5} 。
このような単純な仕組みで書かれる三角形だが、非常に奥深い性質を備えているのである。
組み合わせ論

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

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

3 ⋅ 2 ⋅ 1 = 6 {\displaystyle 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 ) {\displaystyle (A,B,C),(A,C,B),(B,A,C),(B,C,A),(C,A,B),(C,B,A)}
組み合わせ論

の 6 通りである。
組み合わせ論

これは次のようにも考えられる。
組み合わせ論

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

よって、 3 ⋅ 2 = 6 {\displaystyle 3\cdot 2=6}
組み合わせ論

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

今述べたことをまとめると、n 個のものを並べる通りの数を c ( n ) {\displaystyle c(n)} と表すことにすると、 c ( n + 1 ) = c ( n ) ( n + 1 ) {\displaystyle c(n+1)=c(n)(n+1)} となる、ということを言っているのである。
組み合わせ論

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

{ c ( 1 ) = 1 c ( n + 1 ) = c ( n ) ( n + 1 ) {\displaystyle {\begin{cases}c(1)&=1\\c(n+1)&=c(n)(n+1)\end{cases}}}
組み合わせ論

この関数は階乗と呼ばれ、 c ( n ) = n ! {\displaystyle c(n)=n!} と書く。また、 0 ! = 1 {\displaystyle 0!=1} と定義する。こうすることで色々と都合が良いのである。
組み合わせ論

例
組み合わせ論

5 ! = 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅ 1 = 120 {\displaystyle 5!=5\cdot 4\cdot 3\cdot 2\cdot 1=120}
組み合わせ論

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

これを、
組み合わせ論

n P m = n ! ( n − m ) ! {\displaystyle {}_{n}\mathrm {P} _{m}={\frac {n!}{(n-m)!}}}
組み合わせ論

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

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

n P m m ! = n ! m ! ( n − m ) ! {\displaystyle {\frac {{}_{n}\mathrm {P} _{m}}{m!}}={\frac {n!}{m!(n-m)!}}} と表せる。
組み合わせ論

これを、
組み合わせ論

n C m = n ! m ! ( n − m ) ! {\displaystyle {}_{n}\mathrm {C} _{m}={\frac {n!}{m!(n-m)!}}} という関数で表す。他にも、 ( n m ) {\displaystyle {\binom {n}{m}}} で表すこともある。またこれを二項係数ということがある。その理由は後に分かるだろう。
組み合わせとパスカルの三角形の関係

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

さて、ここで色々と計算をしてみる。
組み合わせとパスカルの三角形の関係

0 C 0 = 1 1 C 0 = 1 , 1 C 1 = 1 2 C 0 = 1 , 2 C 1 = 2 , 2 C 2 = 1 3 C 0 = 1 , 3 C 1 = 3 , 3 C 2 = 3 , 3 C 3 = 1 4 C 0 = 1 , 4 C 1 = 4 , 4 C 2 = 6 , 4 C 3 = 4 , 4 C 4 = 1 5 C 0 = 1 , 5 C 1 = 5 , 5 C 2 = 10 , 5 C 3 = 10 , 5 C 4 = 5 , 5 C 5 = 1 {\displaystyle {\begin{aligned}{}_{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{aligned}}}
組み合わせとパスカルの三角形の関係

これの結果だけを書いて、
組み合わせとパスカルの三角形の関係

1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 {\displaystyle {\begin{aligned}&1\\&1\ 1\\&1\ 2\ 1\\&1\ 3\ 3\ 1\\&1\ 4\ 6\ 4\ 1\\&1\ 5\ 10\ 10\ 5\ 1\\\end{aligned}}}
組み合わせとパスカルの三角形の関係

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

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

m C 0 = m ! 0 ! ( m − 0 ) ! = m ! 1 ⋅ m ! = 1 m C m = m ! m ! ( m − m ) ! = m ! m ! ⋅ 1 = 1 {\displaystyle {\begin{aligned}{}_{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{aligned}}}
組み合わせとパスカルの三角形の関係

つまり、端の数は全て 1 である。
組み合わせとパスカルの三角形の関係

また、 n C m + n C m + 1 = n + 1 C m + 1 ⋯ ( 1 ) {\displaystyle {}_{n}\mathrm {C} _{m}+{}_{n}\mathrm {C} _{m+1}={}_{n+1}\mathrm {C} _{m+1}\cdots (1)} が成り立つことを示す。
組み合わせとパスカルの三角形の関係

n C m + n C m + 1 = n ! m ! ( n − m ) ! + n ! ( m + 1 ) ! ( n − ( m + 1 ) ) ! = n ! m ! ( n − m − 1 ) ! ( 1 n − m + 1 m + 1 ) = n ! m ! ( n − m − 1 ) ! ( ( n − m ) + ( m + 1 ) ( n − m ) ( m + 1 ) ) = n ! ( n + 1 ) m ! ( m + 1 ) ( n − m − 1 ) ! ( n − m ) = ( n + 1 ) ! ( m + 1 ) ! ( n − m ) ! = ( n + 1 ) ! ( m + 1 ) ! ( ( n + 1 ) − ( m + 1 ) ) ! = n + 1 C m + 1 {\displaystyle {\begin{aligned}{}_{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)!}}\left({\frac {1}{n-m}}+{\frac {1}{m+1}}\right)\\&={\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{aligned}}}
組み合わせとパスカルの三角形の関係

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

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

( a + b ) 0 = 1 ( a + b ) 1 = 1 a + 1 b ( a + b ) 2 = 1 a 2 + 2 a b + 1 b 2 ( a + b ) 3 = 1 a 3 + 3 a 2 b + 3 a b 2 + 1 b 3 ( a + b ) 4 = 1 a 4 + 4 a 3 b + 6 a 2 b 2 + 4 a b 3 + 1 b 4 {\displaystyle {\begin{aligned}(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+3ab^{2}+1b^{3}\\(a+b)^{4}&=1a^{4}+4a^{3}b+6a^{2}b^{2}+4ab^{3}+1b^{4}\\\end{aligned}}}
二項定理

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

定理 (w:二項定理)
二項定理

( x + y ) n = ( n 0 ) x n y 0 + ( n 1 ) x n − 1 y 1 + ( n 2 ) x n − 2 y 2 + ⋯ + ( n n − 1 ) x 1 y n − 1 + ( n n ) x 0 y n {\displaystyle (x+y)^{n}={n \choose 0}x^{n}y^{0}+{n \choose 1}x^{n-1}y^{1}+{n \choose 2}x^{n-2}y^{2}+\cdots +{n \choose n-1}x^{1}y^{n-1}+{n \choose n}x^{0}y^{n}}
二項定理

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

n = 0 のときは自明。n = 1 のときは、 ( x + y ) 1 = x + y = ( 1 0 ) x + ( 0 1 ) y ( ∵ ( 1 0 ) = ( 1 1 ) = 1 ) {\displaystyle (x+y)^{1}=x+y={1 \choose 0}x+{0 \choose 1}y\ \ \ (\because {1 \choose 0}={1 \choose 1}=1)} より成り立つ。
二項定理

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

( x + y ) k + 1 = ( x + y ) k ( x + y ) = ( ( k 0 ) x k y 0 + ( k 1 ) x k − 1 y 1 + ⋯ + ( k k − 1 ) x 1 y k − 1 + ( k k ) x 0 y k ) ( x + y ) = ( ( k 0 ) x k + 1 y 0 + ( k 1 ) x k y 1 + ⋯ + ( k k − 1 ) x 2 y k − 1 + ( k k ) x 1 y k ) + ( ( k 0 ) x k y 1 + ( k 1 ) x k − 1 y 2 + ⋯ + ( k k − 1 ) x 1 y k + ( k k ) x 0 y k + 1 ) = ( k 0 ) x k + 1 y 0 + ( ( k 1 ) + ( k 0 ) ) x k y 1 + ( ( k 2 ) + ( k 1 ) ) x k − 1 y 2 + ⋯ + ( ( k k − 1 ) + ( k k − 2 ) ) x 2 y k − 1 + ( ( k k ) + ( k k − 1 ) ) + ( k k ) x 0 y k + 1 = ( k + 1 0 ) x k + 1 y 0 + ( k + 1 1 ) x k y 1 + ⋯ + ( k + 1 k ) x 1 y k + ( k + 1 k + 1 ) x 0 y k + 1 ( ∵ ( 1 ) , ( k k ) = ( l l ) = ( k 0 ) = ( l 0 ) = 1 , ) {\displaystyle {\begin{aligned}(x+y)^{k+1}&=(x+y)^{k}(x+y)\\&=\left({k \choose 0}x^{k}y^{0}+{k \choose 1}x^{k-1}y^{1}+\cdots +{k \choose k-1}x^{1}y^{k-1}+{k \choose k}x^{0}y^{k}\right)(x+y)\\&=\left({k \choose 0}x^{k+1}y^{0}+{k \choose 1}x^{k}y^{1}+\cdots +{k \choose k-1}x^{2}y^{k-1}+{k \choose k}x^{1}y^{k}\right)\\&+\left({k \choose 0}x^{k}y^{1}+{k \choose 1}x^{k-1}y^{2}+\cdots +{k \choose k-1}x^{1}y^{k}+{k \choose k}x^{0}y^{k+1}\right)\\&={k \choose 0}x^{k+1}y^{0}+\left({k \choose 1}+{k \choose 0}\right)x^{k}y^{1}+\left({k \choose 2}+{k \choose 1}\right)x^{k-1}y^{2}+\cdots \\&+\left({k \choose k-1}+{k \choose k-2}\right)x^{2}y^{k-1}+\left({k \choose k}+{k \choose k-1}\right)+{k \choose k}x^{0}y^{k+1}\\&={k+1 \choose 0}x^{k+1}y^{0}+{k+1 \choose 1}x^{k}y^{1}+\cdots +{k+1 \choose k}x^{1}y^{k}+{k+1 \choose k+1}x^{0}y^{k+1}\\&\ \ (\because (1),{k \choose k}={l \choose l}={k \choose 0}={l \choose 0}=1,)\end{aligned}}}
二項定理

より、k+1 のときも正しい。
二項定理

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

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

1, 2, 3, 4 ...
多角数

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

1, 3, 6, 10, ...
多角数

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

1, 1+2, 1+2+3, 1+2+3+4, ...
多角数

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

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

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

S = 1 + 2 + 3 + ⋯ + ( n − 1 ) + n S = n + ( n − 1 ) + ( n − 2 ) + ⋯ + 2 + 1 {\displaystyle {\begin{aligned}S&=1+2+3+\cdots +(n-1)+n\\S&=n+(n-1)+(n-2)+\cdots +2+1\\\end{aligned}}}
多角数

∴ 2 S = n ( n + 1 ) ⟺ S = n ( n + 1 ) 2 {\displaystyle \therefore 2S=n(n+1)\iff S={\frac {n(n+1)}{2}}}
多角数

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

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

P 3 4 = 10 {\displaystyle \mathrm {P} _{3}4=10}
多角数

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

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

P 4 n = n 2 {\displaystyle \mathrm {P} _{4}n=n^{2}}
多角数

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

P 5 1 = 1 , P 5 ( n + 1 ) = P 5 n + 3 n + 1 {\displaystyle \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
多角数

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

P 5 n = P 5 1 + ∑ k n − 1 ( 3 k + 1 ) = 1 + 3 ∑ k n − 1 i + ∑ i k n − 1 1 = 1 + 3 2 ( n − 1 + 1 ) ( n − 1 ) + ( n − 1 ) = 3 n 2 − 3 n + 2 n 2 = n ( 3 n − 1 ) 2 {\displaystyle {\begin{aligned}\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{aligned}}}
多角数

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

P 6 1 = 1 , P 6 ( n + 1 ) = P 6 n + ( 4 n + 1 ) {\displaystyle \mathrm {P} _{6}1=1,\mathrm {P} _{6}(n+1)=\mathrm {P} _{6}n+(4n+1)}
多角数

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

P 6 n = P 6 1 + ∑ k n − 1 ( 4 k + 1 ) = 1 + 4 s u m k n − 1 k + s u m k n − 1 1 = 1 + 2 ( n − 1 ) n + ( n − 1 ) = n + 2 ( n − 1 ) n = n ( 2 n − 1 ) {\displaystyle {\begin{aligned}\mathrm {P} _{6}n&=\mathrm {P} _{6}1+\sum _{k}^{n-1}(4k+1)\\&=1+4sum_{k}^{n-1}k+sum_{k}^{n-1}1\\&=1+2(n-1)n+(n-1)\\&=n+2(n-1)n\\&=n(2n-1)\end{aligned}}}
多角数

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

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

n+1 項目は n 項目から (m-2)n + 1 分だけ増える。すなわち、 P m ( n + 1 ) = ( m − 2 ) n + 1 {\displaystyle \mathrm {P} _{m}(n+1)=(m-2)n+1}
多角数

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

P m n = P m 1 + ∑ k n − 1 ( ( m − 2 ) k + 1 ) = 1 + ( m − 2 ) ∑ k n − 1 k + ∑ k n − 1 1 = 1 + m − 2 2 ( n − 1 ) n + ( n − 1 ) = 1 2 { 2 + ( m − 2 ) ( n − 1 ) } = n 2 { 2 + m n − 2 n − m + 2 ) = n 2 ( m n − 2 n − m + 4 ) = ( m − 2 ) n 2 − ( m − 4 ) n 2 {\displaystyle {\begin{aligned}\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{aligned}}}
多角数

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

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

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

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