二項係数の公式
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}
eq7:
\sum_{i=0}^k \binom{n+1}{i}\binom{m-i}{k - i} = \binom{n+m+1}{k}
\sum_i \binom{N-i}{i} = F_N
eq8:
r\binom{n}{r} = n\binom{n-1}{r-1}
ref
Related Pages
- →僕のatcoderの学び方(〜水色)×僕のatcoderの学び方(〜past上級)×abc187×past過去問練習202012×変形テクニックに名前をつける×頂点数18の制約×辺が10^5の制約×行列の半分×二項定理×足し算の順序の変更×辺が10^5ならダイクストラ使える×典型力×問題変換×問題分割×認知の解像度×概念のハンドル×atcoder失敗リスト×atcoderentrypoint×アルゴリズム実技検定×第五回_アルゴリズム実技検定×最小費用流に帰着×帰着訓練→
- →僕のatcoderの学び方(〜緑)×僕のatcoderの学び方(〜青)×ARC106×気づきの言語化×結晶化×変形テクニックに名前をつける×行列の半分×二項定理×足し算の順序の変更×概念のハンドル×テストできるスニペットライブラリ×unionfind×mod_pでの組み合わせ×educational_dp_contest×動的計画法×atcoder_library_practice_contest×atcoder_library×帰着する力×帰着訓練→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]