Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

2nCnの公式

有限正整数列 (a_i)_{i=1}^m\displaystyle\sum_{i = 1}^m a_i = 2n を満たすとき、

\displaystyle\binom{2n}{n} = \displaystyle \sum_{0 \leq i_j \leq a_j,\ j = 1, \ldots, m \\ \quad i_1 + \ldots + i_m = n} \binom{a_1}{i_1} \binom{a_2}{i_2} \cdots \binom{a_m}{i_m}

が成り立ちます。m = 2, a_1 = a_2 = nのときの公式
\displaystyle\binom{2n}{n} = \displaystyle \sum_{i = 0}^n \binom{n}{i}\binom{n}{n - i} = \sum_{i = 0}^n \binom{n}{i}^2

が有名ではないでしょうか。今日はこれを2通りの方法で証明します。*1

1. 多項式の係数に帰着して考える

 \displaystyle\binom{2n}{n}多項式  (1 + x)^{2n} n 次の項の係数です。一方、

 (1 + x)^{2n} = \displaystyle\prod_{i=1}^m (1 + x)^{a_i}……(☆)

であり、右辺の多項式 n次の項の係数は左辺の多項式 n次の項の係数と一致します。
 (1 + x)^{a_j} = \displaystyle\sum_{i_j = 0}^{a_j} \binom{a_j}{i_j} x^{i_j}

を(☆)の右辺に代入し、 n次の係数を考えることで与式が得られます。

2. もうすこし組み合わせ的に考える

 i = 1, \ldots, mに対して、整数 iが書かれたボールが a_i個あるとします。このとき、「同じ整数が書かれたボールを区別しないとき、これらを一列に並べる場合の数」……(★)は

 \dfrac{(2n)!}{a_1! a_2! \ldots a_m!}

通りあります。

ここで、(★)の数を別の方法で数えることを考えます。
 2n個のボールを並べた列のうち、( j = 1, \ldots, mについて)先頭の n個について、整数 jが書かれたボールを i_j個使っていて、かつ後ろの n個について整数 jが書かれたボールを a_j - i_j個使っているものの場合の数は

 \dfrac{n!}{i_1! i_2! \ldots i_m!} \cdot \dfrac{n!}{(a_1 - i_1)! (a_2 - i_2)! \ldots (a_m - i_m)!}

となります。これを i_1 + i_2 + \ldots i_m = nとなるすべての (i_1, \ldots, i_m)の組に対して和を取ることで

 \dfrac{(2n)!}{a_1! a_2! \ldots a_m!} = \displaystyle\sum_{0 \leq i_j \leq a_{j},\ j = 1, \ldots, m \\ \quad i_1 + \ldots + i_m = n} \dfrac{n!}{i_1! i_2! \ldots i_m!} \cdot \dfrac{n!}{(a_1 - i_1)! (a_2 - i_2)! \ldots (a_m - i_m)!}

が得られます。両辺に \dfrac{a_1!a_2!\ldots a_m!}{(n!)^2}を掛けることにより、与式が得られます。

*1:偶然見かけたLeetCodeの問題を解くときに、副産物で2番目の証明が得られたので紹介しようと思い記事を書きました。