m≦nを自然数として、二項係数の積
C[n+i,n]*C[i,m]
の i=m から n までの和が
C[2n+1,n+m+1]*C[n+m,m]
になりそうと予測したのですが、
これは正しいですか、またどのように示せますか。
「畳み込み」とかが使えそうでイマイチうまくいかないです。
|
No.85522 - 2023/06/03(Sat) 19:53:11
| ☆ Re: 二項係数の積の和/高校3年 / m | | | 正しい．
計算すれば m≦n に対して
C[n+i, n] * C[i, m] = C[n+i, n+m] * C[n+m, m]
がわかる．（興味があるなら多項係数とか：
n+i 人を n 人，m 人，i-m 人の 3 グループにに分ける方法として，
最初に n 人選んで残りから m 人選ぶ方法と，
最初に n+m 人を選んでその中からさらに m 人選ぶ方法がある．
これらの選び方の総数は一致するはずで，上の等式はその通りになってる．）
よって
Σ[i=m, ..., n] C[n+i, n+m] = C[2n+1, n+m+1]
を示せばよい．帰納法で示せると思う．今回は直接変形してみる．
C[p, p] = 1 なので
左辺 = 1 + {C[n+m+1, n+m] + C[n+m+2, n+m] + ... + C[2n, n+m]}
= C[n+m+1, n+m+1] + {C[n+m+1, n+m] + C[n+m+2, n+m] + ... + C[2n, n+m]}
= {C[n+m+1, n+m+1] + C[n+m+1, n+m]} + {C[n+m+2, n+m] + ... + C[2n, n+m]}
（公式 C[p, q+1] + C[p, q] = C[p+1, q+1] より）
左辺 = C[n+m+2, n+m+1] + {C[n+m+2, n+m] + ... + C[2n, n+m]}
繰り返して
左辺 = C[2n+1, n+m+1]
を得る．
|
No.85524 - 2023/06/04(Sun) 10:53:56 |
| ☆ Re: 二項係数の積の和/高校3年 / ncr | | | mさま。ありがとうございます。
とても勉強になりました。
>C[n+i, n] * C[i, m] = C[n+i, n+m] * C[n+m, m]
の変形が大きなポイントでした。
ありがとうございました。
|
No.85525 - 2023/06/04(Sun) 15:01:50 |
|
