Cofficient of x in a product

Question

How can I efficiently find the coefficient of $x^m$ in the following product - $\prod\limits_{i=1}^{n-1}(1 - p_i + p_ix)$

Answer 1

Write $$\prod_{i=1}^{n-1}{(1-p_i+p_ix)}=\prod_{j=1}^{n-1}{(1-p_i)}\prod_{i=1}^{n-1}{\left(1+\frac{p_ix}{1-p_i}\right)}$$ The coefficient of $x^m$ is $$\left(\prod_{j=1}^{n-1}{(1-p_i)}\right)e_m\left(\frac{p_1}{1-p_1},\frac{p_2}{1-p_2},\ldots,\frac{p_{n-1}}{1-p_{n-1}}\right)$$ where $e_m$ is the $m$th elementary symmetric polynomial in $n-1$ variables.

The elementary symmetric polynomial can be computed efficiently using the recurrence $$e_k(x_1,x_2,\ldots,x_p)=x_pe_{k-1}(x_1,x_2,\ldots,x_{p-1})+e_k(x_1,x_2,\ldots,x_{p-1})$$ with the starting condition $e_0=1$ and $e_k(x_1,x_2,\ldots,x_p)=0$ if $p<k$.