1
$\begingroup$

If $E$ is some set $E=\{x_1,x_2,\cdots,x_n,\cdots\}$ and $f:E\times \cdots \times E\to\mathbb{R}$ is a real valued function on $E$, and we have the sum,

$$\sum_{x_1,x_2,\cdots,x_n\in E}f(x_1,x_2,\cdots,x_n)$$

How would the above sum be computed? I'm not sure what it means to sum over multiple elements in a set at the same time.

$\endgroup$
3
  • $\begingroup$ If $f: E \to \mathbb{R}$, images of $f$ look like $f(x)$ for $x \in E$, and something like $f(x_1, ..., x_n)$ has no defined meaning. Given the available information, the correct way to sum the images of $f$ over $E$ would be to write $\sum_{x \in E} f(x)$. The summation you ask about is meaningless and is most probably a typo. $\endgroup$
    – user
    May 18, 2018 at 2:06
  • $\begingroup$ Sorry I meant $f:E\times E \times \cdots \times E \to \mathbb{R}$. I've fixed that now. $\endgroup$ May 18, 2018 at 2:09
  • $\begingroup$ In this case, elements of the set $E^n := E \times ... \times E$ would be tuples of the form $ x:= (x_1, ..., x_n)$, your $f$ would know how to produce a single real number for each such tuple $x$, and the summation would just be $\sum_{x \in E^n} f(x)$ as usual. The notation, as it currently stands, is still incorrect. $\endgroup$
    – user
    May 18, 2018 at 2:17

1 Answer 1

1
$\begingroup$

This notation means that the sum should be taken over all $ n$-subsets $ \{x_1,x_2,\dots,x_n\} $ in $ E $.

For example, $ \sum_{a,b \in E} ab $ is the sum of all products of pairs of elements from $ E $.

If you like, you can rewrite the sum in the question as $$ \frac{1}{n!} \sum_{x_1 \in E} \sum_{x_2 \in E\setminus\{x_1\}} \cdots \sum_{x_n \in E \setminus \{x_1,\dots,x_{n-1}\}} f(x_1,x_2,\dots,x_n). $$ (The $1/n! $ is to prevent counting $ n$-tuples more than once, and we have to play with the sum bounds to prevent adding any $ x_i$s to themselves.)

If you want to take the sum over each ordering of the subsets, then one would just remove the $ 1/n! $ factor - then each distinct ordering of each subset will be run through $ f $ as well. This is probably what you want if $ f $ isn't symmetric in its arguments.

$\endgroup$
3
  • $\begingroup$ If you want to go from tuples to subsets, you would have to factor out $n!$ different permutations, not $n$. Also, the way you've written it, you aren't excluding when $x_i=x_j$ and $i\neq j$, so you will also get subsets of size less than $n$. $\endgroup$
    – Kevin Long
    May 18, 2018 at 2:21
  • $\begingroup$ Usually, when you write $\sum_{x_1,x_2,\dots,x_n\in E} f(\dots)$, repeats are counted more than once. To prevent repeats, assuming $E$ had an order, you would write $\sum_{x_1\le x_2\le \dots \le x_n} f(\dots)$. As Kevin noted, $1/n$ does not correctly get rid of over-counting. $\endgroup$ May 18, 2018 at 3:43
  • $\begingroup$ I've fixed it, not too sure about whether repeats should be counted or not. $\endgroup$
    – user562871
    May 18, 2018 at 4:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .