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}\)
    • 経路数
  • \(i{n+i \choose i}=(n+1){n+i \choose i-1}\)
    • n個の赤玉, i個の青玉, 1個の緑玉を並べる方法

Published in データ構造

Comments

コメントを残す

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

CAPTCHA