一些计数

一些计数

by AmanoKumiko

组合数消去乘积

\[\sum_{i=0}^n \binom{a}{i}*\binom{b}{n-i}=\binom{a+b}{n}\\ \sum_{i=0}^n\binom{i}{a}*\binom{n-i}{b}=\binom{n+1}{a+b+1} \]

在平面上从原点走\(N\)步到达\((x,y)\)的方案数

令\(k=\frac{N-x-y}{2}\)

可以发现正方向上走了\(x+y+k\)步

那么答案为

\[\sum_{i=0}^k\binom{N}{x+y+k}\binom{x+y+k}{y+i}\binom{k}{k-i}\\ \binom{N}{x+y+k}\sum_{i=0}^k\binom{x+y+k}{y+i}\binom{k}{k-i}\\ \binom{N}{x+y+k}\binom{N}{y+k} \]

普通多项式与下降幂多项式的转换

1.系数表式法

\[\sum_{i=0}^na_ix^i=\sum_{i=0}^na_i\sum_{j=0}^ix^{\underline j}S(i,j)\\ \sum_{i=0}^na_ix^i=\sum_{j=0}^nx^{\underline j}\sum_{i=j}^nS(i,j)a_i \]

2.点值表示法

\[a_i=\sum_{j=0}^nb_ji^{\underline j}\\ a_i=\sum_{j=0}^nb_j\frac{i!}{(i-j)!}\\ \frac{a_i}{i!}=\sum_{j=0}^n\frac{b_j}{(i-j)!}\\ EXP(A)=B*e^x \]