Skip to content →

二項係数 公式集

  • \(\sum_{i=0}^n {n \choose i} = 2^n\)
  • \(\sum_{i=0}^{\lfloor n/2 \rfloor} {n \choose 2i} = 2^{n-1}\)
    • パスカルの三角形
    • \(((1+1)^{n}+(1-1)^{n}) / 2\)
  • \(\sum_{k=0}^{n-1} {2n \choose k} = 2^{2n-1}-\frac{1}{2}{2n \choose n}\)
  • \(\sum_{k=0}^{n} k{2n \choose k} = n2^{2n-1}\)
    • \(k{2n \choose k} = 2n {2n-1 \choose k-1}\) を使う。
  • \(\sum_{k=0}^{n} k(k-1){2n \choose k} = n(2n-1)\left(2^{2n-2}-{2n-2 \choose n-1}\right)\)
    • \(\sum_{k=0}^{n} k{2n \choose k}\) と同様。
  • \(\sum_{k=0}^{l} {n+k \choose k} = {n+l+1 \choose l}\)
    • 経路数
    • \(1/(1-x)^{n+1}, 1/(1-x)\) の畳み込み
  • \(\sum_{i=0}^{l} \sum_{j=0}^{m} {i+j \choose j} = {l+m+2 \choose l+1}-1\)
    • 経路数。最後の 「, 」字部分を取り除くと、(0, 0) → (0, 0) だけ、(0, 0) → (l+1, 0) → (l+1, m+1) と(0, 0) → (0, m+1) → (l+1, m+1) でダブルカウントされているので取り除く。
    • 母関数の畳み込み
  • \(\sum_{i=0}^{k} {n+i \choose i} {m-i \choose k-i} ={n+m \choose k}\)
    • 経路数
  • \(\sum_{i=1}^{n-1} \left(\!\!{i \choose a}\!\!\right)\left(\!\!{n-i \choose b}\!\!\right) = \left(\!\!{n – 1\choose a+b+1}\!\!\right)\)
    • 経路数, yuki1989
  • \(\sum a_i = N\) となる非負整数列 \(a\) に対して、
    $$\sum_{\sum i_k=N, i_k \in \mathbb{Z_{\geq 0}}}D^{i_1}x^{a_1}D^{i_2}x^{a_2} \cdots D^{i_w}x^{a_w}
    = \prod \frac{\left(a_{k+1}+\sum_{i=1}^{k-1}(a_i+1)\right)!}{\left(\sum_{i=1}^{k-1} (a_i+1)\right)!}$$
    が成り立つ(exawizards2019D)。式変形で示せるが大変。ボールを一列に並べる方法と解釈するのが早い。
  • \(\sum_{i+j=c} {a \choose i} {b \choose j} = {a + b \choose c}\)。\(a, b\) が負でも成り立つことに注意。
    • 次はABC259Hの式変形。\(y\) が昇順に並んでいるとする。
      \begin{align}
      &\sum_{x_i \geq x_j, y_i \geq y_j} {x_i+y_i-x_j-y_j \choose x_i – x_j} \\
      = &\sum_{k_i + k_j = x_i-x_j, k_i \geq 0, k_j \geq 0, i \geq j} {x_i+y_i \choose k_i}{-x_j-y_j \choose k_j} \\
      = &\sum_{x_i – k_i = x_j + k_j, k_i \geq 0, k_j \geq 0, i \geq j} {x_i+y_i \choose k_i}{-x_j-y_j \choose k_j} \\
      = &\sum_{i=1}^M \sum_{k_i=0}^N {x_i+y_i \choose k_i} \sum_{1 \leq j \leq i, x_i-k_i = x_j + k_j} {-x_j-y_j \choose k_j}\\
      \end{align}
      \(\sum_{1 \leq j \leq i, x_i-k_i = x_j + k_j} {-x_j-y_j \choose k_j}\) は inline にメモ化することで \(O(1)\) で計算できる。

変数を減らす公式

  • $${2n \choose n} = (-4)^n{-\frac{1}{2} \choose n}$$
  • $$i{n+i \choose i}=(n+1){n+i \choose i-1}$$
    • n個の赤玉, i個の青玉, 1個の緑玉を並べる方法
  • $$k { n \choose k} = n{n – 1 \choose k – 1}$$

Published in データ構造

Comments

コメントを残す

メールアドレスが公開されることはありません。

CAPTCHA