kit84 talks

社会人 / AtCoder 緑 / くBC 水

緑コーダーが「数え上げPDF」の行間に挑む(第 2 回)

前回 の続きです。

前回、成立することを確認した 6 つの公式 について、証明と組み合わせ論的な解釈をしていきます。

が、所詮このブログは誰も読まないので、ざっくり納得できたところで終了します。
肩の力を抜いて、ご覧ください。

6 つの公式

ここで 数え上げPDF の公式(修正版)を再掲しておきます。

頻出公式(修正版)

  • \(\displaystyle\sum_{i=0}^N \binom Ni = 2^N\)

  • \(\displaystyle\sum_{i=0}^{\left\lfloor N/2 \right\rfloor} \binom N{2i} = 2^{N-1} \quad\) \((N\ge 1)\)

  • \(\displaystyle\sum_{i=0}^K \binom{N +i}i = \binom{N+K+1}K\)

  • \(\displaystyle\sum_ {i=0}^K \sum_{j=0}^L \binom{i+j}i = \binom{K+L+2}{K+1} - 1\)

  • \(\displaystyle\sum_{i=0}^K \binom Ni \binom M{K-i} = \binom{N+M}K\)

  • \(\displaystyle\sum_{i=0}^K \binom{N +i}i \binom{M-i}{K-i} = \binom{N+M+1}K \quad\) \((M\ge K)\)

いろいろありますね

証明らしきもの

準備:超重要公式

本題に入る前に、次の等式を納得しておきます。

超重要公式!! \[\binom{N-1}{K -1} + \binom{N-1}{K} = \binom NK \qquad (N,K\ge 1)\]

この式は、めちゃくちゃ重要です。

超重要公式

もう一度言います。この式は、超←重要です。

パスカルの三角形の生成にも、この式が漸化式として使われます。
いつもお世話になっている解説に記載がある通り、証明自体は簡単です。(式変形するだけ)

さて、この式の意味するところですが、次のように考えることができます。

番号が書かれた \(N\) 本のクジがあり、同時に \(K\) 本を取り出すことを考えます。
この全体のパターン数は、\(\displaystyle \binom NK\) です。 \(\cdots\)(右辺)

この \(N\) 本の中に、当たりクジが「 \(1\) 本だけ」入っているとしましょう。
すると、\(K\) 本を引いたとき

  • 当たる(当たりを含む)パターン数は \(\displaystyle \ \binom 11 \times \binom{N-1}{K -1}\)

  • 外れる(当たりを含まない)パターン数は \(\displaystyle \ \binom 10 \times \binom{N-1}K\)

です。 これらを足すと(当たる \(+\) 外れる)、全体のパターン数に一致します。 \(\cdots\)(左辺)

以上により、超重要公式が成り立つことが分かります。

公式 1

公式 1 \[\displaystyle\sum_{i=0}^N \binom Ni = 2^N\]

\(N\) 行目の合計が \(2^N\) になるやつです。

式をじーっと見てみましょう。

じー…

ところで、
番号が書かれた \(N\) 個のボールがあります。
あなたは、その中から同時に \(i\) 個を取り出します。
このパターン数は \(\displaystyle\binom Ni\) です。

ここで、\(i\) が \(0\le i\le N\) のすべての整数値を動いたときの合計を考えます。 \[\binom N0 + \binom N1 + \binom N2 + \cdots + \binom NN\] こういう事です。 \(\cdots\)(左辺)

\(i\) に関して、考えられる全てのパターンを合計してしまいました。
これは即ち、\(N\) 個のボールから「いくつか(\(0\) 個以上)」を選ぶパターンの数です。

逆に考えましょう。

\(N\) 個のボールそれぞれに対して、そのボールを「選ぶ」か「選ばない」かの \(2\) 択を考えます。
この「 \(2\) 択を \(N\) 個セットにしたもの」が、\(1\) つのパターンです。

つまり、パターンの総数は \(2^N\) ですね。 \(\cdots\)(右辺)

という事で、公式 1 が導かれました。

公式 1 の応用 \[\sum_{i=0}^N \sum_{j=0}^i \binom ij = 2^{N+1} -1\]

応用として紹介した、「\(N\) 行目より上の三角形全体の合計」も証明しておきましょう。

公式 1 より、 \[\begin{eqnarray*} (左辺) &=& \sum_{i=0}^N 2^i \cr &=& \,2^0 \!+ 2^1 \!+ 2^2 \!+ \cdots + 2^N \end{eqnarray*}\] であり、これは等比級数です。

あとはこういう議論をすることにより、右辺と等しいことが分かります。
(筆者は、\(2\) 進数で \(\underbrace{111...1}_{(N+1)\text{個}}\) と表される数をイメージしました)

公式 2

公式 2 \[\sum_{i=0}^{\left\lfloor N/2 \right\rfloor} \binom N{2i} = 2^{N-1} \qquad (N\ge 1)\]

\(N\) 行目の偶数番目の数を拾ってきて合計すると、 \(2^{N-1}\) となるやつです。
\((N-1)\) 行目の合計と等しくなる、と見てもよいでしょう。

ここで、あの 超重要公式 の出番です。

公式 2-1 公式 2-2

おお… 見えてきました…
(三角の領域外は \(0\) だと思ってください)

なぜ、あんなに飛び飛びの項の合計が、\(1\) つの式にまとまるのか。
実は、\(1\) つ上の行を合計するのと同じだったのです…

公式 3

公式 3 \[\sum_{i=0}^K \binom{N +i}i = \binom{N+K+1}K\]

次は、ホッケースティック恒等式です。

ここでも、なんと 超重要公式 が役に立ちます。

公式 3-1

数学的帰納法ですね。
(全部そうと言えばそう)

ちゃんと説明すると、\(0\) から \((K -1)\) までで成立すると仮定したとき、そこに 超重要公式 を適用することで \(K\) でも成立することが導けます。

公式 3 の変形 \[\sum_{i=0}^K \binom{N +i}N = \binom{N+K+1}{N+1}\]

公式 3-2

同じ意味の上記式は覚えやすいですね。
ここまで読んだあなたは、yukicoder の No.1126 SUM を瞬殺できるでしょう。
(とはいえ、階乗や乗法逆元の実装は、別途習得しておく必要があります)

公式 4

公式 4 \[\sum_ {i=0}^K \sum_{j=0}^L \binom{i+j}i = \binom{K+L+2}{K+1} - 1\]

これは、公式 3 を繰り返し適用することで導出できます。

公式 4

たとえば、縦の \(1\) 列分をそれぞれ合計したものが右斜め下の黄色枠になる(公式 3 の変形)ので、最後にこの黄色枠を合計すればよいです。
しかし、最も左の列には黄色枠がないので、そのまま 公式 3 を使って黄色枠の合計を求めることができません。

ここでテクニックで、いったん 公式 3 を使ってから、あとで多すぎた分を引くことを考えます。
すると、「多すぎる分」は常に \(1\) だと読み取れる( \(\because\binom L0 = 1\) )ので、公式 4 が導けました。

いったんここまで

すみません
長くなってきたので、続きは次回です。

次回、完結編ーーー