◆東京都 サボテン さんからの解答。
1)j=1の場合
a(i,1)=a(i-1,1)よりa(i,1)=a(i-1,1)・・・=a(1,1)=1
よってa(i,1)=a(1,i)=1
2)i≧2かつj≧2の場合
| a(i,j)＝ | j Σ k=1 |
a(i-1,k) ＝ | j-1 Σ k=1 |
a(i-1,k)+a(i-1,j) |
一方
| a(i,j-1)＝ | j-1 Σ k=1 |
a(i-1,k) |
これより
a(i,j)=a(i,j-1)+a(i-1,j)・・・（１）
以下帰納法を用いる。
i＜m又はj＜nで、a(i,j)=a(j,i)が成り立つとする。
このとき（１）よりa(m,n)=a(n,m)
1)と合わせてi=n,j=mでも成り立つ事が示せた。
以上で証明終
◆長崎県 Dr.Berserker さんからの解答。
とりあえず、二つ目の式を以下のように分割する。
a(i,j)
| ＝ | j Σ k=1 |
a(i-1,k) |
| ＝ | j-1 Σ k=1 |
a(i-1,k) + a(i-1,j) |
| ＝a(i,j-1) + a(i-1,j) |
ここで、a(i,j) = combination(i+j-2,j-1) (*)とおけば、(←組み合わせの数)
上式は、
combination(x,y) = combination(x-1,y) + combination(x,y-1)
と置き換えられるから、これはパスカルの三角形を並べ替えたものに他ならない。
従って、combination(x,y) = combination(y,x)であるから、
a(i,j) = a(j,i)が言える。
＃(*)式は、パスカルの三角形が出てきたんで、改めて証明する必要はないと思うのですが・・・。
◆出題者のコメント
ありがとうございました。正解です。
確かに、パスカルの三角形そのものなんですが・・・
| a(i,j)=a(j,i)= | (i+j-2)! (i-1)!*(j-1)! |
=i+j-2Ci-1=i+j-2Cj-1 |