[组合] 等幂和形韦达系数求证

tommywong

$\displaystyle\prod_{r=1}^n (x-x_r)=\sum_{r=0}^n a_r x^r=0,s_m=\sum_{r=1}^n x_r^m$

$\displaystyle a_{n-m}=\sum_{r_i=0}^{\lfloor \frac{m}{i} \rfloor} \prod_{i=1}^m \frac{(-s_i)^{r_i}}{i^{r_i} r_i!},\sum_{i=0}^m ir_i=m$

$\displaystyle a_{n-1}=(-s_1)$
$\displaystyle a_{n-2}=\frac{1}{2} (-s_1)^2+\frac{1}{2} (-s_2)$
$\displaystyle a_{n-3}=\frac{1}{6} (-s_1)^3+\frac{1}{2} (-s_1)(-s_2)+\frac{1}{3} (-s_3)$

其妙

回复 1# tommywong
牛顿公式吧，

tommywong

现在推广到含系数的等幂和，如$k_1 x_1^3+k_2 x_2^3=(k_1 x_1+k_2 x_2)(x_1+x_2)^2-(k_1+k_2)(x_1+x_2)(x_1 x_2)-(k_1 x_1+k_2 x_2)(x_1 x_2)$

$\displaystyle\sum_{i=1}^n k_i x_i^s=\sum_{r=1}^{s-1} (-1)^{r-1} \sum_{i=1}^n k_i x_i^{s-r} \sum_{i_1 \neq i_2 \neq ... \neq i_r} x_{i_1}x_{i_2}...x_{i_r}+(-1)^{s-1} \sum_{i_1 \neq i_2 \neq ... \neq i_s} x_{i_1}x_{i_2}...x_{i_s} (k_{i_1}+k_{i_2}+...+k_{i_s})$

$\displaystyle\sum_{i_1 \neq i_2 \neq ... \neq i_s} x_{i_1}x_{i_2}...x_{i_s} (k_{i_1}+k_{i_2}+...+k_{i_s})=\sum_{r=1}^s (-1)^{r-1} \sum_{i=1}^n k_i x_i^r \sum_{i_1 \neq i_2 \neq ... \neq i_{s-r}} x_{i_1}x_{i_2}...x_{i_{s-r}}$

tommywong

$\displaystyle(\sum_{i=1}^n k_i x_i^r)\sum_{i_1 \neq i_2 \neq ... \neq i_{s-r}} x_{i_1}x_{i_2}...x_{i_{s-r}}
=\sum_{i_1 \neq i_2 \neq ... \neq i_{s-r}} k_{i_1}x_{i_1}^{r+1}x_{i_2}...x_{i_{s-r}}
+\sum_{i_1 \neq i_2 \neq ... \neq i_{s-r}} k_{i_1}x_{i_1}^{r}x_{i_2}...x_{i_{s-r+1}}$

$\displaystyle\sum_{i_1 \neq i_2 \neq ... \neq i_{s-1}} k_{i_1}x_{i_1}^{2}x_{i_2}...x_{i_{s-1}}+\sum_{i_1 \neq i_2 \neq ... \neq i_{s}} k_{i_1}x_{i_1}^{1}x_{i_2}...x_{i_{s}}-\sum_{i_1 \neq i_2 \neq ... \neq i_{s-2}} k_{i_1}x_{i_1}^{3}x_{i_2}...x_{i_{s-2}}-\sum_{i_1 \neq i_2 \neq ... \neq i_{s-1}} k_{i_1}x_{i_1}^{2}x_{i_2}...x_{i_{s-1}}+...$

$\displaystyle(-1)^{s-1}\sum_{i_1} k_{i_1}x_{i_1}^{s}+\sum_{i_1 \neq i_2 \neq ... \neq i_{s}} k_{i_1}x_{i_1}^{1}x_{i_2}...x_{i_{s}}=\sum_{r=1}^{s-1} (-1)^r (\sum_{i=1}^n k_i x_i^r)\sum_{i_1 \neq i_2 \neq ... \neq i_{s-r}} x_{i_1}x_{i_2}...x_{i_{s-r}}$

tommywong

证明$\displaystyle s_m=\sum_{r_i=0}^{\lfloor \frac{m}{i} \rfloor} \frac{m(r_1+r_2+...+r_n -1)!}{r_1!r_2!...r_n!} \prod_{i=1}^n (-a_{n-i})^{r_i},\sum_{i=1}^n ir_i=m$：

代换$t_i=-a_{n-i}$，此时递推关系为：

$s_1=t_1$

$s_2=t_1s_1+2t_2$

$s_3=t_1s_2+t_2s_1+3t_3$

$s_m=\displaystyle \sum_{k=1}^{m-1} t_ks_{m-k} +mt_m$

设$\displaystyle s_m=\sum_{r_i=0}^{\lfloor \frac{m}{i} \rfloor} f(m,r_1,r_2,...,r_n) \prod_{i=1}^n t_i^{r_i},\sum_{i=1}^n ir_i=m$

同时有$f(m,r_1,...,r_n)=f(m-1,r_1-1,...,r_n)+...+f(m-n,r_1,...,r_n-1)$

$\displaystyle \frac{(m-1)(r_1+...+r_n-2)!}{(r_1-1)!...r_n!}+...+\frac{(m-n)(r_1+...+r_n-2)!}{r_1!...(r_n-1)!}=\frac{[r_1(m-1)+...+r_n(m-n)](r_1+...+r_n-2)!}{r_1!...r_n!}=\frac{[m(r_1+...+r_n)-m](r_1+...+r_n-2)!}{r_1!...r_n!}=\frac{m(r_1+...+r_n-1)!}{r_1!...r_n!}$

$s_{m-1},...,s_{m-n}$成立时得出$s_m$成立

现在剩下等幂和形韦达系数

tommywong

代换$b_i=-s_i$

$a_{n-1}=b_1$

$2a_{n-2}=b_1a_1+b_2$

$3a_{n-3}=b_1a_2+b_2a_1+b_3$

$ma_{n-m}=\displaystyle \sum_{k=1}^m b_ka_{m-k}$

$mf(r_1,...,r_m)=f(r_1-1,...,r_m)+...+f(r_1,...,r_m-1)$

$\displaystyle \prod \frac{r_1}{i^{r_i} r_i!}+...+\prod \frac{mr_m}{i^{r_i} r_i!}=m\prod \frac{1}{i^{r_i} r_i!}$

等幂和形韦达系数得证