Factoring/approximating an apparently simple formula

Question

Does anyone know if the following formula can be factorized or approximated:

$a^3 + b^3 + c^3 + a^2b + ab^2 + a^2c + ac^2 + b^2c + bc^2 + abc$

It looks a lot like $(a + b + c)^3$, except for the combinatorial factors.

Of course, the expression can be shortened as $\sum\limits_{x + y + z = 3} a^xb^yc^z$ but in terms of computational cost it does not help. This is a special case, I will have to use similar expressions with many more terms, but I believe that if someone could show me how to factorize/approximate this one, I can adapt it to the following more general case:

$\sum\limits_{|\vec{\alpha}|=n}\prod\limits_{j=1}^{n}a_j^{\alpha_{j}}$ with $\vec{\alpha}$ an n-dimensional multi-index ($\vec{\alpha} = \{\alpha_1,...,\alpha_n\}$, with $\alpha_i$ non-negative integers.). (sorry if the mathematical notation is wrong).

Is there a way to approximate the result? Probably it can not be factorized nicely, but surely there is a way to approximate it with something less resource-consuming.

Thank you!

edit: If it helps, $0< a < b < c \leq 1$, and $0 < a_1 < ... < a_n < 1$

Answer 1

$\sum_{|\alpha|=n} \prod_{j=1}^k a_j^{\alpha_j} = S(n,k)$ where $S(n,0) = 0$ and $$S(n,k+1) = S(n,k) + a_{k+1}^n + \sum_{p=1}^{n-1} a_{k+1}^p S(n-p,k)$$

Answer 2

For the order one case the sum will be:

$$\sum a_j $$

For the order two case the sum will be:

$$\frac12 \left(\sum a_j \right)^2 + \frac12 \left(\sum a_j^2 \right) $$

For the order three case the sum will be:

$$\frac16 \left(\sum a_j \right)^3 + \frac12 \left(\sum a_j \right)\left(\sum a_j^2 \right) + \frac13 \left(\sum a_j^3 \right)$$

For the order four case the sum will be

$$\frac1{24} \left(\sum a_j \right)^4 + \frac14 \left(\sum a_j \right)^2\left(\sum a_j^2 \right) + \frac18 \left(\sum a_j^2 \right)^2 + \frac13 \left(\sum a_j \right)\left(\sum a_j^3 \right)+ \frac14 \left(\sum a_j^4 \right)$$

and there will be similar expressions for higher orders.

Answer 3

Another approach, similar to Robert Israel's, is also based on the quantity $$S(n,k)=\sum_{\begin{eqnarray}(c1,c_2,\ldots,c_k)\in\mathbb{N}_0^k\\ c_1+c_2+\ldots+c_k = n\end{eqnarray}}\ \prod_{j=1}^k a_j^{c_j}$$ which corresponds to complete homogeneous symmetric polynomial of degree $n$ in variables $a_1,a_2,\ldots,a_k$. The recurrence is different, though: $$\begin{eqnarray} S(0,k) & = & 1\\ S(n+1,0) & = & 0 \\ S(n+1,k+1) & = & S(n+1,k) + a_{k+1}\cdot S(n,k+1) \end{eqnarray}$$

This permits calculation of $S(n,k)$ in $O(nk)$ time and using $O(k)$ memory:

S[0] = 0
for(int k=1; k<=K; k++) S[k] = 1
for(int n=1; n<=N; n++) for(int k=1; k<=K; k++) S[k] = S[k-1] + a[k]*S[k]
return S[K]

If $n$ was considerably bigger than $k$, one could compute the result using matrix powers. Let $$A = \left(\begin{array}{cccc} a_1 & a_1 & \ldots & a_1 & a_1 \\ 0 & a_2 & \ldots & a_2 & a_2 \\ \vdots & & & & \vdots \\ 0 & 0 & \ldots & a_{k-1} & a_{k-1} \\ 0 & 0 & \ldots & 0 & a_k \\ \end{array}\right)$$

Then, $$(1,1,1)\times A^n = \left(S(n,1),S(n,2),\ldots,S(n,k)\right)$$ (the matrix $A$ implements one iteration of the recurrence). Computing $n$-th power of matrix by repeated squaring can be done in $O(\log n)$ steps, with each step consisting of one matrix multiplication.