组合式子

记录一下遇到过的组合式子

\(\binom n m=\binom{n-1}{m-1}+\binom{n-1}m\)

\(\sum\limits_{i=0}^n a^i b^{n-i}\binom ni=(a+b)^n\)

对任意正整数 \(x\)，\(\sum\limits_{i=1}^{n}\binom i x=\binom {n+1}{x+1}\)。from CF1548C

\(k\times \binom nk=n\times \binom {n-1}{k-1}\) from P6620

\(j^i\binom nj=\sum\limits_{k=1}^i S(i,k)\times n^{\underline{k}}\times\binom{n-k}{j-k}\)。\(S(i,k)\) 是第一类斯特林数，递推式为 \(S(i,k)=S(i-1,k-1)+i\times S(i-1,k)\) from P6620