# How to simplify the following mathematical expression?

While solving one of the algorithmic problems, I came around with one mathematical expression, I tried solving it but not able to compress it into a smaller expression which can be calculated easily.

Suppose there are n numbers $(a_1,a_2{\ldots} a_n)$:

$$n*(a_1*a_2 \ldots a_n)+(n-1)*(a_1*a_3 \ldots a_n + a_1*a_2*a_4 \ldots a_n + a_1*a_2*a_3*a_5 \ldots a_n+ \ldots a_2*a_3*a_4 \ldots a_n) + (n-2)*(a_1*a_4 \ldots a_n + a_1*a_2*a_5 \ldots a_n + \ldots a_3*a_4 \ldots a_n) + \ldots 1*(a_1+a_2+a_3 \ldots a_n)$$

This seems like the well-known expression, but I am not able to find its compressed version.

To make the mathematical expression more clear, let's take n=4

$$4*(a_1*a_2*a_3*a_4)+ 3*(a_1*a_2*a_3 + a_1*a_3*a_4 + a_1*a_2*a_4 + a_2*a_3*a_4)+ 2*(a_1*a_2 + a_1*a_3 + a_1*a_4 + a_2*a_3 +a_2*a_4 + a_3*a_4)+ 1*(a_1+a_2+a_3+a_4)$$

Let me know if the mathematical expression is not clear.

• What do you mean by "solve" an expression? This can be written as $\sum _{k=1}^n \sum_{i_1<i_2...<i_k}ka_{i_1}a_{i_2}...a_{i_k}$ – asdf Jun 25 '18 at 8:32
• I meant simplify :) – prat Jun 25 '18 at 8:33
• Welcome to MSE. I suggest that you don't use the symbol $*$ for multiplication. Use $\times$ instead. – José Carlos Santos Jun 25 '18 at 8:33
• @asdf, I remember this can be converted into some combinatorics expression, but can't recall that expression. – prat Jun 25 '18 at 8:41
• This seems to be a new version of a question that you posted earlier (and apparently now deleted), which had a considerable comment history under it. Please don't do that. – joriki Jun 25 '18 at 8:53

## 1 Answer

The expression probably can't be simplified beyond $$\sum_{s \subseteq S} |s| \prod_{x \in s}x$$

However, the calculation can be streamlined considerably.

If we define $f(S)$ as the expression above, we can calculate the extension by $y \not\in S$ as $$\begin{eqnarray} f(S \cup \{y\}) &=& \sum_{s \subseteq S \cup \{y\}} |s| \prod_{x \in s}x \\ &=& \sum_{s \subseteq S} |s| \prod_{x \in s}x + \sum_{s \subseteq S} (|s|+1) y \prod_{x \in s}x \\ &=& f(S) + y\left(\sum_{s \subseteq S} |s| \prod_{x \in s}x + \sum_{s \subseteq S} \prod_{x \in s}x\right) \\ &=& f(S)(1 + y) + y\sum_{s \subseteq S} \prod_{x \in s}x \\ \end{eqnarray}$$

If we now define $g(S) = \sum_{s \subseteq S} \prod_{x \in s}x$ then similarly $$\begin{eqnarray} g(S \cup \{y\}) &=& \sum_{s \subseteq S \cup \{y\}} \prod_{x \in s}x \\ &=& \sum_{s \subseteq S} \prod_{x \in s}x + \sum_{s \subseteq S} y \prod_{x \in s}x \\ &=& g(S)(1 + y)\end{eqnarray}$$

So we have $f(S \cup \{y\}) = f(S)(1 + y) + yg(S)$ and $g(S \cup \{y\}) = g(S)(1 + y)$, allowing an easy calculation starting from $f(\emptyset) = 0$ and $g(\emptyset) = 1$.