Expansion of $(a+b+c+d+e+....)^n$, but with all coefficients equal to 1.

Question

I'm looking for a formula to calculate the sum of $(a+b+c+d+...)^n$ but with coefficients equal to 1. For example in $(a+b+c)^2$. I want the sum of $a^2 + b^2 + c^2 + ab + bc + ca$. And for $(a+b+c+d)^3$, I want the sum of $a^3 + b^3 + c^3 + a^2b + a^2c + b^2a + b^2c + c^2a + c^2b + abc$. Similarly, I want the sum of expansion of $(a+b+c+d+e+....)^n$ with coefficient equal to 1. I tried to find the pattern by expanding the $(a+b+c)^2$. And I found that its formula is $a^2 + b^2 + c^2$ + $\frac{((a+b+c)^2 - a^2-b^2-c^2)}{2}$. This works for the power of 2. But fails on other powers. Any help will be really appreciated.

Answer 1

For any $k$ variables $x_1, \ldots, x_k$, let $P_n(x_1,\ldots,x_k)$ be the sum of all monomials over them for degree $n$.

$$P_n(x_1,\ldots,x_k) \stackrel{def}{=} \sum_{\sum_{j=1}^{k} e_j = n} \prod_{j=1}^k x_j^{e_j}, \quad\text{where}\quad e_1,\ldots,e_k \in \mathbb{N}$$

Multiply by $s^n$ and sum over $n$, we find

$$\begin{align} P(s) \stackrel{def}{=} \sum_{n=0}^\infty s^n P_n(\cdots) &= \sum_{n=0}^\infty \sum_{\sum_{j=1}^{k} e_j = n} \prod_{j=1}^k (sx_j)^{e_j}\\ &= \sum_{e_1=0}^\infty\cdots\sum_{e_k=0}^\infty \prod_{j=1}^k (sx_j)^{e_j} = \prod_{j=1}^k \sum_{e_j=0}^\infty (sx_j)^{e_j}\\ &= \prod_{j=1}^k \frac{1}{1 - s x_j}\end{align}$$

Apply partial fraction decomposition to RHS, we obtain

$$P(s) = \sum_{j=1}^k \frac{1}{1-sx_j} \prod_{\ell=1,\ne j}^k \frac{1}{1 - \frac{x_\ell}{x_j}} = \sum_{j=1}^k \frac{x_j^{k-1}}{1-s x_j}\prod_{\ell=1,\ne j}^k \frac1{x_j - x_\ell}$$ Expand both sides and compare coefficients of $s^n$, we can represent $P_n$ as a sum of $k$ rational functions.

$$P_n(x_1,\ldots,x_k) = \sum_{j=1}^k x_j^{n+k-1}\prod_{\ell=1,\ne j}^k \frac{1}{x_j - x_\ell}$$