Given a polynomial of degree $n$, i.e: $$p(x) = \prod_{i=1}^n x-i=(x-1)\cdot(x-2)\cdot\ldots\cdot(x-n)$$
What will be the coefficient of each power of $x$?
I figured out the coefficient of $x^{n-k}$ is the sum of the product of all possible combinations of $k$ integers from $1$ to $n$, but I can't find a simple formula or method to compute each of these coefficients efficiently.
Can we use Inverse FFT in this case?
The roots of this polynomial are $\alpha_1 = 1, \alpha_2 = 2, ..., \alpha_n = n$. Let polynomial $P$ to be like this: $P(x) = x^n + a_{n-1}x^{n-1}+...+a_1x + a_0$ (it is clear that the coefficient $a_n = 1$).
By the Vieta's formulas we know that $\sigma_k = (-1)^k \cdot \frac{a_{n-k}}{a_n}$ (for $1 \leq k \leq n$), where $\sigma_k$ is the sum of all $k-$permutations of roots $\alpha_1,...,\alpha_n$. So, since $a_n = 1$ we get that $a_k = (-1)^{n-k}\cdot\sigma_{n-k}$ for $1\leq k \leq n -1$
I think that this is a simpler approach than Inverse FFT (if it's possible to do it that way).