# Is there a poly-time algorithm for expanding out polynomials

so I've been looking around and haven't seen this before. Basically I'm working with a problem in which I need to expand/FOIL out. Something in the form of $$z = (x+y)(x-y) \implies x^2+xy-xy+y^2$$ but for any input with $n$ number of operations. $$z = (x_1+x_2+x_3+...+x_n)\cdot(x_1+x_2+x_3+...+x_n)\cdot...\cdot(x_1+x_2+...x_n) = ?$$

I tried just doing the basic "by hand" method, but to me that seems like it would be on the scale of $n!$. Is there a better way of doing this? Thank you!

• What happens when $z = (x_1+y_1) \cdot (x_2+y_2) \cdots (x_n+y_n)$? – Yuval Filmus Feb 14 '18 at 17:11
• Try a divide and conquer approach. That should reduce the workload. – Sagnik Feb 14 '18 at 17:27
• Let $a = (x_1 + x_2 +.....+x_n)$. Take $z = a * a * a * a.....* a$, assuming there are $k$ $a$'s. Now solve for the smaller subproblem where you multiply $a * a$ roughly $k/2$ times in the first pass. Keep solving this until you get the result. – Sagnik Feb 14 '18 at 17:36

For the particular polynomial in the question, we have the multinomial theorem. $$(x_1+x_2+\cdots+x_n)^m = \sum_{k_i\geq 0,\, k_1+k_2+\cdots+k_n=m} \binom{m}{k_1,k_2, \cdots,k_n} x_1^{k_1}x_2^{k_2}\cdots x_n^{k_n}$$ where the coefficients are knowns as multinomial coefficients, and can be computed by $$\binom{m}{k_1,k_2,\cdots,k_n} = \frac{m!}{k_1!\,k_2!\cdots k_n!}$$
• the particular polynomial in the question I don't see $n$ and $m$ where $(x_1+y)(x_1−y)$ is $(x_1+\cdots+x_n)^m$. – greybeard Nov 21 '18 at 6:35