Sum of terms in a multinomial expansion? (that is all coefficients are equal to one)

Question

How to sum the series $a^3+b^3+c^3+a^2b+a^2c+b^2a+b^2c+c^2a+c^2b+abc$?

And in general for any multinomial expansion.

Answer 1

Hope this is want you are looking for: $$\sum_{\substack{0\leq i,j,k\leq 3\\i+j+k =3}}a^ib^jc^k = [x^3]\left(\frac{1}{1-ax}\cdot\frac{1}{1-bx}\cdot\frac{1}{1-cx}\right)\tag{1}$$ hence in order to find your sum you may differentiate $f(x)=\frac{1}{(1-ax)(1-bx)(1-cx)}$ three times, evaluate in zero and divide by $3!=6$: $$ \sum_{\substack{0\leq i,j,k\leq 3\\i+j+k =3}}a^ib^jc^k = \lim_{\varepsilon \to 0}\frac{f(3\varepsilon)-3f(2\varepsilon)+3f(\varepsilon)-f(0)}{6\varepsilon^3}\tag{2} $$ If you know in advance that $a,b,c\in\mathbb{Z}$, to compute your sum you just have to take a small $\varepsilon$ and approximate the RHS of $(2)$ to the closest integer.

Answer 2

This specific one can be simplified to

$(a+b+c)^3 - 2(a^2b+a^2c+b^2a+b^2c+c^2a+c^2b) - 5abc = (a+b+c)^3 - 2(a+b)(b+c)(c+a) - abc$

I picked this specific factorization because after calculating $a+b+c$, the sums $a+b$, $a+c$, and $b+c$ all come quickly. However, I do not know of a generalized "fastest" algorithm to generate the minimum number of computations.

There are definitely algorithms to do this, though as far as I know they do not reduce this completely in every case. Restricting the coefficients to one actually hurts rather than helps in this case, since the symmetric expressions easiest to produce generally have coefficients. This comes from the fact that taking any elementary symmetric polynomial to a power generates coefficients.