二項係数の公式
eq1:
- $\sum_{k=0}^n \binom{n}{k} = 2^n$
- proof
- 二項定理
- $(1 + 1) ^ n = \sum_{k=0}^n \binom{n}{k}$
- $(1 + 1) ^ n = 2^n$
eq2:
- $\sum_{k=0}^n (-1)^k \binom{n}{k} = 0$
- proof
- 二項定理
- $(-1 + 1) ^ n = \sum_{k=0}^n (-1)^k 1^{n-k} \binom{n}{k} = \sum_{k=0}^n (-1)^k \binom{n}{k}$
- $(-1 + 1) ^ n = 0^n = 0$
eq3:
- $\sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n}{2k} = 2^{n-1}$
- proof
- from eq1, eq2
- $(1 + 1) ^ n + (-1 + 1) ^ n = 2^n$
- $(1 + 1) ^ n + (-1 + 1) ^ n = \sum_{k=0}^n \binom{n}{k} + \sum_{k=0}^n (-1)^k \binom{n}{k} = 2 \sum_{i=0}^{\lfloor n/2 \rfloor} \binom{n}{2i}$
- kが奇数の時には打ち消し合うため
eq4: ホッケースティック恒等式
- $\sum_{i=0}^k \binom{n+i}{i} = \binom{n+k+1}{k}$
eq5:
- $\sum_{i=0}^k \sum_{j=0}^l \binom{i+j}{i} = \binom{k+l+2}{k+1}-1$
- パスカルの三角形的解釈
eq6: Vandermondeの恒等式
- $\sum_{i=0}^k \binom{n}{i}\binom{m}{k - i} = \binom{n+m}{k}$
- special case(k=n, m=n)
- $\sum_{i=0}^n \binom{n}{i}^2 = \binom{2n}{n}$
eq6-2 ARC110D
- $\sum_i \binom{i}{A}\binom{N-i-1}{B} = \binom{N}{A+B+1}$
- ボール的解釈
eq6-3
- $\sum_i \binom{A + i}{i}\binom{B + K - i}{K - i} = \binom{A + B + K + 1}{K}$
- eq6-3をeq6-2に帰着
- 重複組合せの畳み込み
eq7:
- $\sum_{i=0}^k \binom{n+1}{i}\binom{m-i}{k - i} = \binom{n+m+1}{k}$
- eq7-proof
-
- $\sum_i \binom{N-i}{i} = F_N$
eq8:
- $r\binom{n}{r} = n\binom{n-1}{r-1}$
- https://mathtrain.jp/nikoukeisu
ref