[莫名其妙的]二项式反演

\text{第一反演公式}

\text{设}n\in \mathbb{N}_+\,\,,\text{多项式序列}\left\{ p_n \right\} ,\left\{ q_n \right\} \text{有如下关系:}

p_n\left( x \right) =\sum_{k=0}^n{\alpha _{nk}q_k\left( x \right) \,\,},\,\,q_n\left( x \right) =\sum_{k=0}^n{\beta _{nk}p_k\left( x \right)}

\text{且}A=\left( \alpha _{ij} \right) ,B=\left( \beta _{ij} \right) \text{为非奇异矩阵},\,\text{则有}

v_n=\sum_{k=0}^n{\alpha _{nk}u_k}\Leftrightarrow u_n=\sum_{k=0}^n{\beta _{nk}v_k}

 

 

Proof.

\text{令}p=\left( p_0,p_1,\cdots ,p_n \right) ^T,q=\left( q_0,q_1,\cdots ,q_n \right) ^T

u=\left( u_0,u_1,\cdots ,u_n \right) ^T,v=\left( v_0,v_1,\cdots ,v_n \right) ^T

\text{则可将原式表示为}

p=Aq\,\,,\,\,q=Bp

\therefore p=Aq=ABp.

\because p\text{是线性空间}R\left[ x \right] \text{的一组基}

\therefore AB=I,\,\,A^{-1}=B

\therefore v=Au\Leftrightarrow u=A^{-1}v=Bv\,\,\,\,\blacksquare

 

 

\text{二项式反演}

\text{设}\left\{ a_n \right\} \text{和}\left\{ b_n \right\} \text{是两个数列}

a_n=\sum_{k=0}^n{\left( \begin{array}{c}n\\k\end{array} \right) b_k}\Leftrightarrow b_n=\sum_{k=0}^n{\left( -1 \right) ^{n-k}\left( \begin{array}{c}n\\k\end{array} \right) a_k}

 

 

Proof.

x^n=\left( 1+x-1 \right) ^n=\sum_{k=0}^n{\left( \begin{array}{c}n\\k\end{array} \right) \left( x-1 \right) ^k}

\left( x-1 \right) ^n=\sum_{k=0}^n{\left( -1 \right) ^{n-k}\left( \begin{array}{c}n\\k\end{array} \right) x^k}

\text{由第一反演公式可得证}