范德蒙德卷积的 GF 推导

· · 算法·理论

设 F (x) = \sum _ {i = 0} \binom a i x ^ i = (1 + x) ^ a，G (x) = \sum _ {i = 0} \binom b i x ^ i = (1 + x) ^ b，则

F (x) G (x) = (1 + x) ^ a (1 + x) ^ b = (1 + x) ^ {a + b} = \sum _ {i = 0} \binom {a + b} i x ^ i

故 \sum \binom a i \binom b {n - i} = [x ^ n] F (x) G (x) = \binom {a + b} i