目次

• ヴァンデルモンドの畳み込みとは？
• 公式の導出
• 基本的な例題
• 応用問題に挑戦
• 試験での使い方と注意点

ヴァンデルモンドの畳み込みとは？

ヴァンデルモンドの畳み込み（Vandermonde’s Convolution）は、二項係数に関する重要な恒等式の一つです。具体的には次のような等式です。

\[ \sum_{k=0}^{r} \binom{m}{k} \binom{n}{r-k} = \binom{m+n}{r} \]

この等式は、ふたつの異なるグループから合計 \( r \) 個を選ぶ組合せを、段階的に考えた結果として得られます。

この公式の意味を理解するために、まず二項係数の意味を再確認しましょう。

\[ \binom{n}{k} = \text{「n個のものからk個を選ぶ方法の数」} \]

ヴァンデルモンドの畳み込みは、「分けて選ぶ」→「まとめて選ぶ」という考え方を使った変形です。

公式の導出

この公式の導出には、組合せの基本的な考え方を使います。

例：赤玉 \( m \) 個と青玉 \( n \) 個から合計 \( r \) 個を選ぶ

赤玉 \( m \) 個と青玉 \( n \) 個があります。これらから合計 \( r \) 個を選ぶとします。

このとき、赤玉を \( k \) 個選び、青玉を \( r – k \) 個選ぶと考えると、それぞれの選び方は次のように表せます。

\[ \binom{m}{k} \cdot \binom{n}{r – k} \]

このような選び方は \( k = 0 \) から \( r \) まで全て考えられるため、合計の方法は以下のようになります。

\[ \sum_{k=0}^{r} \binom{m}{k} \binom{n}{r-k} \]

一方、赤玉と青玉を区別せず、合計 \( m + n \) 個の玉から \( r \) 個を選ぶと考えると、これは単に次のようになります。

\[ \binom{m+n}{r} \]

したがって、この両者は同じ数であるべきなので、ヴァンデルモンドの畳み込みの公式が成り立ちます。

基本的な例題

例題1：具体的な計算

次の式を計算しなさい。

\[ \sum_{k=0}^{2} \binom{3}{k} \binom{4}{2 – k} \]

この式を展開すると：

\[ \binom{3}{0} \binom{4}{2} + \binom{3}{1} \binom{4}{1} + \binom{3}{2} \binom{4}{0} = 1 \cdot 6 + 3 \cdot 4 + 3 \cdot 1 = 6 + 12 + 3 = 21 \]

一方、ヴァンデルモンドの畳み込みを使えば：

\[ \binom{3 + 4}{2} = \binom{7}{2} = 21 \]

確かに一致しています。

例題2：文字を含む式

\[ \sum_{k=0}^{r} \binom{n}{k} \binom{n}{r – k} = \binom{2n}{r} \]

これは、両方のグループが同じサイズ \( n \) の場合の特殊な形です。

応用問題に挑戦

応用例1：多項係数との関係

三つのグループに分けて選ぶ場合はどうなるでしょうか？

三項係数を使った場合、以下のように拡張できます。

\[ \sum_{i+j = r} \binom{m}{i} \binom{n}{j} \binom{l}{r – i – j} = \binom{m+n+l}{r} \]

このようにヴァンデルモンドの考え方は、さらに多項係数にも発展できます。

応用例2：パス数え上げ問題

例えば、格子点上の経路の数を数えるときにも、ヴァンデルモンドの畳み込みは使われます。

右に \( m \) 歩、上に \( n \) 歩の移動で到達できる格子点の数は \(\binom{m+n}{m}\) ですが、その経路を途中で折り返すように分けて考えることで、ヴァンデルモンドの考え方が応用されます。

試験での使い方と注意点

試験では以下の点に注意しましょう：

• 和の中に二項係数が2つあれば、ヴァンデルモンドの畳み込みを疑う。
• 式を素直に展開して確認するクセをつける。
• 公式を覚えるだけでなく「なぜ成り立つか」を説明できるようにする。

頻出ポイント

センター試験や共通テスト、国公立二次試験の整数問題、数列や組合せの融合問題で出題されることがあります。

まとめ

ヴァンデルモンドの畳み込みは、単なる公式にとどまらず、組合せ論の考え方を深く理解するための鍵となる重要な道具です。定理の意味を理解し、様々な場面に応用できるようになれば、数学の問題に対する見通しが大きく広がります。