第３章 算術三角形論と冪和
著者:梅谷 武
第３章 算術三角形論と冪和の数式・表・プログラム一覧。
作成:2013-09-04
更新:2013-09-04
第３章 算術三角形論と冪和
3.1 算術三角形論
3.1.2 算術三角形に関する19の帰結
(3.1)
C(i,j) = C(i－1,j) + C(i,j－1),  i,j ≧ 0
算譜301 パスカルの算術三角形 (samp301.rb)
# 算術三角形の生成
max = 10
C = Array.new(max) { Array.new(max) { 0 } }
C[0][0] = 1
for i in 1...max
  C[i][0] = 1
end
for j in 1...max
  C[0][j] = 1
end
for i in 1...max
  for j in 1...(max-i)
    C[i][j] = C[i-1][j] + C[i][j-1]
  end
end
 
# 算術三角形の印字
for i in 0...max
  for j in 0...(max-i)
    printf " %3d", C[i][j]
  end
  print "\n\n"
end
 samp301.rb の実行結果 
   1    1    1    1    1    1    1    1    1    1 
 
   1    2    3    4    5    6    7    8    9 
 
   1    3    6   10   15   21   28   36 
 
   1    4   10   20   35   56   84 
 
   1    5   15   35   70  126 
 
   1    6   21   56  126 
 
   1    7   28   84 
 
   1    8   36 
 
   1    9 
 
   1

定理3.1 算術三角形に関する19の帰結

 任意の母数の算術三角形について以下に示す帰結が導き出される。特に指定がない場合、i,j,kは任意の自然数と考える。
(P1) 第０行と第０列のすべての細胞は母細胞と同じである。
C(0,0) = C(0,j) = C(i,0)
(P2) 各細胞はその上の行の左端からその細胞の上までのすべての細胞の和に等しい。
C(i,j) =
j
∑
k = 0
C(i－1,k)
(P3) 各細胞はその左の列の上端からその細胞の左までのすべての細胞の和に等しい。
C(i,j) =
i
∑
k = 0
C(k,j－1)
(P4) 各細胞から１を引いたものはその細胞を含む行の上側と列の左側との間のその行と列は除いた部分に含まれるすべての細胞の和に等しい。
C(i,j) － 1 =
j－1
∑
t = 0
i－1
∑
s = 0
C(s,t)
(P5) 各細胞はその相反細胞に等しい。
C(i,j) = C(j,i)
(P6) 行指数と列指数が同じ値ｋをもつ第ｋ行と第ｋ列はまったく同じ細胞から成っている。
C(k,i) = C(i,k)
(P7) 各底辺の細胞の和は、その上の底辺の細胞の和の２倍である。
 
∑
i + j = k
C(i,j)
 = 2
 
∑
i + j = k－1
C(i,j)
(P8) 各底辺の細胞の和は、１から始まる公比２の等比級数の一項であり、その指数は底辺の指数と同じである。
 
∑
i + j = k
C(i,j)
 = 2k
(P9) 各底辺の細胞の和から１を引いたものは、それより上のすべての底辺の細胞の和に等しい。
 
∑
i + j = k
C(i,j)
 － 1 =
k－1
∑
r = 0
(
 
∑
i + j = r
C(i,j)
)
 =
k－1
∑
r = 0
2r
(P10) ある底辺の一端から連続した細胞の和は、その上の底辺の一端から同じ長さの細胞の和に、長さを一つ減じた細胞の和を加えたものに等しい。
n
∑
j = 0
C(k－j,j)
 =
n
∑
j = 0
C(k－1－j,j)
 +
n－1
∑
j = 0
C(k－1－j,j)
(P11) 分割線上の細胞はその上または左で隣り合う細胞の２倍である。
C(i,i) = 2C(i,i－1) = 2C(i－1,i)
(P12) 同じ底辺にあって隣接する二つの細胞について上の細胞と下の細胞との比は、上の細胞から底辺の最上段までの細胞の個数と下の細胞から底辺の最下段までの細胞の個数との比に等しい。
C(i,j) : C(i+1,j－1) = i + 1 : j
(P13) 同じ列にあって隣接する二つの細胞について下の細胞と上の細胞との比は、上の細胞の底辺の指数に１を加えたものと行指数に１を加えたものとの比に等しい。
C(i+1,j) : C(i,j) = i + j + 1 : i + 1
(P14) 同じ行にあって隣接する二つの細胞について右の細胞と左の細胞との比は、左の細胞の底辺の指数に１を加えたものと列指数に１を加えたものとの比に等しい。
C(i,j+1) : C(i,j) = i + j + 1 : j + 1
(P15) ある算術三角形の行の細胞の和と同じ行の右端の細胞との比は、底辺の指数に１を加えたものとその行指数に１を加えたものとの比に等しい。
j
∑
k = 0
C(i,k)
 : C(i,j) = i + j + 1 : i + 1
(P16) ある算術三角形の行の細胞の和とその下の行の細胞の和との比は、下の行の指数に１を加えたものとその行の細胞の個数との比に等しい。
j
∑
k = 0
C(i,k)
 :
j－1
∑
k = 0
C(i+1,k)
 = i + 2 : j
(P17) ある細胞にそれを含む列の上側のすべての細胞を加えたものと同じ細胞にそれを含む行の左側のすべての細胞を加えたものとの比は、それぞれの細胞の個数の比に等しい。
i
∑
k = 0
C(k,j)
 :
j
∑
k = 0
C(i,k)
 = i + 1 : j + 1
(P18) 上下端から等距離にある二つの行の細胞の和の比は、それらの細胞の個数の比に等しい。
k－i
∑
j = 0
C(i,j)
 :
i
∑
j = 0
C(k－i,j)
 = k － i + 1 : i + 1
(P19) 分割線上にあって隣接する二つの細胞について、下の細胞と上の細胞の4倍との比は、上の細胞の底辺の指数に1を加えたものとさらにそれに1を加えた数との比に等しい。
C(i,i) : 4C(i－1,i－1) = 2i － 1 : 2i

命題3.2 細胞の階乗公式

 任意の自然数i,j(j＞0)に対して次の式が成り立つ。
(3.2)
C(i,j) =
(i+1)⋯(i+j)
j!
3.1.3 組み合わせの数

補題3.4 組み合わせの加法公式

 任意の自然数a,b(a＜b)に対して次が成り立つ。
(3.3)
(b
a		)
 +
(b
a+1		)
 =
(b+1
a+1		)

定理3.5 細胞と組み合わせ

 任意の自然数i,jに対して次が成り立つ。
(3.4)
C(i,j) =
(i+j
j		)

系3.6 組み合わせの計算公式

 任意の自然数n,k(n≧k)に対して次が成り立つ。
(3.5)
(n
k		)
 =
n!
(n－k)!k!

系3.7 組み合わせに関する19の帰結

 特に指定がない場合、n,k(n≧k)は任意の自然数と考える。
(P1)
(0
0		)
 =
(n
n		)
 =
(n
0		)
 = 1
(P2)
(n
k		)
 =
k
∑
i = 0
(n－k－1+i
i		)
(P3)
(n
k		)
 =
n－k
∑
i = 0
(k+i
k		)
(P4)
(n
k		)
 － 1 =
n－k－1
∑
i = 0
k－1
∑
j = 0
(i+j
j		)
(P5)
(n
k		)
 =
(n
n－k		)
(P6)
(k+i
i		)
 =
(i+k
k		)
(P7)
n
∑
i = 0
(n
i		)
 = 2
n－1
∑
i = 0
(n－1
i		)
(P8)
n
∑
i = 0
(n
i		)
 = 2n
(P9)
n
∑
i = 0
(n
i		)
 － 1 =
n－1
∑
r = 0
(
r
∑
i=0
(r
i		)
) =
n－1
∑
r = 0
2r
(P10)
r
∑
i = 0
(n
i		)
 =
r
∑
i = 0
(n－1
i		)
 +
r－1
∑
i = 0
(n－1
i		)
(P11)
(2n
n		)
 = 2
(2n－1
n－1		)
 = 2
(2n－1
n		)
(P12)
(n
k		)
 =
n－k+1
k
(n
k－1		)
(P13)
(n
k		)
 =
n
n－k
(n－1
k		)
(P14)
(n
k		)
 =
n
k
(n－1
k－1		)
(P15)
k
∑
i = 0
(n－k+i
i		)
 =
n+1
n－k+1
(n
k		)
(P16)
k
∑
i = 0
(n－k+i
i		)
 =
n－k+2
k－1
k－1
∑
i = 0
(n－k+1+i
i		)
(P17)
n－k
∑
i = 0
(k+i
i		)
 =
n－k+1
k+1
k
∑
i = 0
(n－k+i
i		)
(P18)
k
∑
i = 0
(n－k+i
i		)
 =
k+1
n－k+1
n－k
∑
i = 0
(k+i
i		)
(P19)
(2n
n		)
 =
2n－1
2n
4
(2n－2
n－1		)
3.1.4 二項定理

定理3.8 二項定理

 任意の自然数nについて次が成り立つ。
(3.6)
(X+Y)n =
n
∑
k = 0
(n
k		)
XkYn－k
3.2 冪和
3.2.1 パスカルの冪和公式
(3.7)
Pk(n) ≡
n
∑
i = 1
ik
 = 1k + 2k + ⋯ + nk
(3.8)
Pk(n,a,d) ≡
n
∑
i = 1
aik
 =
n
∑
i = 1
(a + (i－1)d)k

定理3.9 パスカルの冪和公式

 自然数ｋに対して初項ａ、公差ｄの等差数列のｋ次の冪和は次のように表すことができる。
(3.9)
Pk(n,a,d)
=
1
(k+1)d
 lc48 (a+nd)k+1 － ak+1
－
k－1
∑
j=0
(k+1
j		)
dk+1－jPj(n,a,d) rc48
特にa = d = 1の場合、
(3.10)
Pk(n)
=
1
k+1
 lc48 (n+1)k+1 － 1
－
k－1
∑
j=0
(k+1
j		)
Pj(n) rc48

系3.10 冪和多項式の性質

 Pk(n)はｎに関するｋ＋１次の多項式であり、定数項は無く、 最上位係数は
1
k + 1
である。
Published by SANENSYA Co.,Ltd.