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!

  • $\begingroup$ What happens when $z = (x_1+y_1) \cdot (x_2+y_2) \cdots (x_n+y_n)$? $\endgroup$ – Yuval Filmus Feb 14 '18 at 17:11
  • $\begingroup$ Try a divide and conquer approach. That should reduce the workload. $\endgroup$ – Sagnik Feb 14 '18 at 17:27
  • $\begingroup$ 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. $\endgroup$ – 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!}$$

For most of general products of multivariable polynomials, there is no such closed formula for their expansion.

| cite | improve this answer | |
  • $\begingroup$ 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$. $\endgroup$ – greybeard Nov 21 '18 at 6:35
  • $\begingroup$ @greybeard Check the formula right above "I tried just doing the basic". $\endgroup$ – John L. Nov 21 '18 at 11:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.