ホッケースティック恒等式

右|サムネイル|300x300ピクセル|パスカルの三角形の最初の7列。ホッケースティックの恒等式は、の場合にという形で表現される。ホッケースティック恒等式（ホッケースティックこうとうしき、）とは、2つの整数に関して成立する、組み合わせ論における次の恒等式のことである:

「ホッケースティックの恒等式」という名前は、パスカルの三角形上で恒等式に出現する項がホッケースティックのように並んでいることに由来する。英語ではホッケースティックの代わりに同様の形状のもので代用されることもあり、例えばChirstmas stocking identityなどとも呼ばれる。

式としての表現総和を表すシグマ記号を用いれば、この恒等式を

と書ける。また、ダミー変数をへと変更した上で、二項係数の性質を利用すれば、この恒等式を次のようにも表せることがわかる:

証明

代数学または数学的帰納法による証明これらの手法は以下に示すパスカルの法則を利用する:

帰納法による証明ホッケースティック恒等式はに関する数学的帰納法によって証明できる。

まず、の時に恒等式が成立することを示す:

により、の時に成立していることが示される。次に、あるに対して

と、所与の式が成立していると仮定する。すると、所与の式でとおいた場合に

が示される。ただし最後の変形にパスカルの法則を用いた。以上2ステップより、数学的帰納法からホッケースティック恒等式が示される。

代数学的証明パスカルの法則から導かれる式を利用して、畳み込み級数を利用する形に帰着させることで証明できる:

組み合わせ論による証明

証明1 個の区別不能な玉を個の識別可能な袋に入れる状況を考える。多重集合の議論により、このような状況で袋に分配する方法は

通りだけある。ここで、個ある袋の中から特定の1つに着目すると、分配の結果その袋の中には玉が個だけ入ることになる。今、その袋に個だけ玉を入れるような分配法をそれぞれのについて数え上げ、それを全てのについて和をとれば、全ての分配方法の数に一致する。

注目している袋に個だけ玉を入れ、残りを分配する方法は通りだけある。これでによる証明が適用できるので、

が成立する。あとは、なる変数変換のもとで

が得られ、証明が完了する。

証明2 個の要素からなる集合から、個の要素を持つ部分集合を構成することを考える。そのような部分集合は

通りだけある。ここで、個の要素のうち任意の個に、の番号を割り振る。今、番号が割り振られていない要素は個しかないため、個の要素からなる部分集合には番号が割り振られている要素が必ず含まれる。部分集合に含まれる番号の割り振られた要素のうち、最小の番号をとするならば、部分集合の構築手法はの数値による場合分けで背反かつ網羅的に分割できる。最小の番号がとなるような部分集合を構成するとき、は必ず部分集合に含まれ、かつ残りの個の要素はを除いた個の要素から選択される。よって、そのような選択方法は

通りある。あとはを利用することで、

が示され、証明が完了する。

母関数による証明とし、を展開した時のの係数を考える。まず、等比級数の公式により、以下が成立する:

さらに、二項定理により

が任意の自然数に対して成立する。よって、特にの係数はで与えられる。

今、を展開した際のの係数に関して、に素朴に二項定理を適用すると、

という表示が得られる。同様に、のの係数を考えると、これはにおけるの係数に一致するので、

となる。等比級数の公式によりこれらは一致するので、

が得られ、証明が完了する。

ホッケースティック恒等式

Źródło i licencja