2nCnの公式
有限正整数列 が を満たすとき、
が成り立ちます。のときの公式
が有名ではないでしょうか。今日はこれを2通りの方法で証明します。*1
1. 多項式の係数に帰着して考える
は多項式 の 次の項の係数です。一方、
であり、右辺の多項式の次の項の係数は左辺の多項式の次の項の係数と一致します。
を(☆)の右辺に代入し、次の係数を考えることで与式が得られます。
2. もうすこし組み合わせ的に考える
に対して、整数が書かれたボールが個あるとします。このとき、「同じ整数が書かれたボールを区別しないとき、これらを一列に並べる場合の数」……(★)は
通りあります。
ここで、(★)の数を別の方法で数えることを考えます。
個のボールを並べた列のうち、(について)先頭の個について、整数が書かれたボールを個使っていて、かつ後ろの個について整数が書かれたボールを個使っているものの場合の数は
となります。これをとなるすべてのの組に対して和を取ることで
が得られます。両辺にを掛けることにより、与式が得られます。
*1:偶然見かけたLeetCodeの問題を解くときに、副産物で2番目の証明が得られたので紹介しようと思い記事を書きました。