• \(\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} = \frac{\left( \sum (a_i+1) -1\right)!}{\prod_{k=2}^w\left(\sum_{i=1}^{k-1} (a_i+1)\right)}$$
  が成り立つ（exawizards2019D）。ボールを一列に並べる方法と解釈する。\begin{align}\sum_{i=0}^{a_2} \frac{a_2!}{i!}(a_1+i)! &= a_1!a_2!\sum_{i=0}^{a_2} {a_1+i \choose i}\\&= \frac{(a_1+a_2+1)!}{a_1+1} \\
  \sum_{i=0}^{a_3} \frac{a_3!}{i!}\frac{(a_2+i)!}{j!}(a_1+j)! &= \sum_{i=0}^{a_3} \frac{a_3!}{i!}\frac{(a_1+a_2+i+1)!}{(a_1+1)} \\
  &= \frac{(a_1+a_2+a_3+2)!}{(a_1+1)(a_1+a_2+2)} \\ \end{align}
• \(\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)\) で計算できる。
• \begin{eqnarray}
  f(a,b)= \begin{cases}
  f(a-1,b)+f(a,b-1) &&(\text{if $a \leq N$ and $b \leq M$})\\
  0 && (\text{otherwise})
  \end{cases}
  \end{eqnarray}

  \begin{align}
  &\sum_{a+b=n} f(a,b) \max(a,b)\\
  =&\sum_{a+b=n+1} f(a,b) \max(a,b)\\
  =&\sum_{a+b=n+1} (f(a-1,b)+f(a,b-1)) \max(a,b)
  \end{align}

  \begin{align}
  &\sum_{a+b=n+1} f(a-1,b)\max(a,b)\\
  =&\sum_{a+b=n} f(a,b)\max(a+1,b)\\
  =&\sum_{a+b=n} f(a,b)\max(a,b)+\sum_{a+b=n,\\ a \geq b} f(a,b)
  \end{align} (AGC)

変数を減らす公式

• $${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個の緑玉を並べる方法
• $$ { n \choose k} = \frac{n}{k}{n-1 \choose k-1}$$

\begin{align}
y &= \sum_{i \geq 0}{k+2i \choose i}x^i \\
&= \operatorname{diag} \frac{1}{1-x-y} \left(\frac{1}{1-y}\right)^k\\
&=[s^0] \frac{1}{1-x/s-s}\left(\frac{1}{1-s}\right)^k\\
&=[s^0] \frac{1}{\beta-\alpha}\left(\frac{\alpha}{s-\alpha}-\frac{\beta}{s-\beta}\right) \left(\frac{1}{1-s}\right)^k \\
&= [s^0] \frac{1}{\beta-\alpha}\left(\frac{\alpha/s}{1-\alpha/s}+\frac{1}{1-s/\beta}\right)\left(\frac{1}{1-s}\right)^k \\
&= [s^0] \frac{1}{\sqrt{1-4x}}\left(\sum_{n \geq 1} \alpha^n s^{-n} +\sum_{n \geq 0} \beta^{-n}s^n \right) \sum_{n \geq 0} {n + k-1 \choose n}s^n \\
&= \frac{1}{\sqrt{1-4x}} \sum_{n \geq 0} {n + k-1 \choose n}\alpha^n \\
&= \frac{1}{\sqrt{1-4x}} \frac{1}{(1-\alpha)^k}\\
&= \frac{1}{\sqrt{1-4x}} \left(\frac{2}{1+\sqrt{1-4x}}\right)^k
\end{align}

$$\frac{1}{{a + b \choose a}} = \frac{1}{{a + b + 1 \choose a}} + \frac{a}{a + 1}\frac{1}{{a + b + 1 \choose a + 1}}$$

黒のボール \(a\) 個、白のボール \(b\) 個、緑のボール \(1\) 個が入った袋から、ボールを順番に取り出す。任意の黒のボールが任意の白のボールより先に出る確率を計算している。

$$\frac{n}{k}{n-1 \choose k-1} = {n \choose k}$$
最初に n 個の中から一つ選んで赤色で塗り、残りの n-1個から k-1個選んでいる。k個のどれを赤で塗るかがk通りあるので、kで割っている。