0
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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}$ $\endgroup$ – asdf Jun 25 '18 at 8:32
  • $\begingroup$ I meant simplify :) $\endgroup$ – prat Jun 25 '18 at 8:33
  • $\begingroup$ Welcome to MSE. I suggest that you don't use the symbol $*$ for multiplication. Use $\times$ instead. $\endgroup$ – José Carlos Santos Jun 25 '18 at 8:33
  • $\begingroup$ @asdf, I remember this can be converted into some combinatorics expression, but can't recall that expression. $\endgroup$ – prat Jun 25 '18 at 8:41
  • 1
    $\begingroup$ 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. $\endgroup$ – joriki Jun 25 '18 at 8:53
1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.