Factoring/approximating an apparently simple formula 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$
 A: $\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)$$
A: 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.  
A: 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. 
