What does $\sum_{(a_1,a_2,...,a_n)\in\{1,x\}^n} a_1a_2\cdot\cdot\cdot a_n$ mean? In my textbook, I have this summation, but I can't understand what it means:
$$\sum_{(a_1,a_2,...,a_n)\in\{1,x\}^n} a_1a_2\cdot\cdot\cdot a_n$$
For example, if $n = 3$, what would this summation expand as?
Thanks
 A: It just means each $a_i \in \{1,x\}$.  With $n=3$ the sum is $$(1\cdot 1 \cdot 1) + (1\cdot 1 \cdot x) + (1\cdot x \cdot 1) + (1\cdot x \cdot x) + (x\cdot 1 \cdot 1) + (x\cdot 1 \cdot x) + (x\cdot x \cdot 1) + (x\cdot x \cdot x)$$ $$= 1 + 3x + 3x^2 + x^3.$$
A: Note that if $A$ and $B$ are sets then
$$A\times B=\{(a,b):a\in A,b\in B\}$$
so 
$$A^2=A\times A=\{(a,b):a,b\in A\}$$
And $$A^{n}=A\times A^{n-1}$$
So $$A^3=\{(a,b,c):a,b,c\in A\}$$
Hence if $A=\{1,x\}$ then 
$$\{1,x\}^3=\{(a,b,c):a,b,c\in\{1,x\}\}$$
$$\begin{align}
=\{&(1,x,x),(x,1,x),(x,x,1)\\
&(1,1,x),(1,x,1),(x,1,1)\\
&(1,1,1),(x,x,x)\}
\end{align}$$
And in general, $\{1,x\}^n$ is going to have $2^n$ points. The sum in question is a sum over all those points:
$$S_n=\sum_{(a_1,...,a_n)\in\{1,x\}^n}a_1\cdots a_n$$
Which will be a sum of $2^n$ terms. 
Let $P^{(n)}_j$ be the set of all points $(a_1,a_2,...,a_n)$ such that there are $j$ entries $a_k$ that are $x$, and there are $n-j$ entries $a_i$ that are $1$. We see that there is ${n\choose 0}=1$ point in $P^{(n)}_0$ and ${n\choose n}=1$ point in $P^{(n)}_n$. Then we see that there are ${n\choose 1}=n$ points in $P_1^{(n)}$ and ${n\choose n-1}=n$ points in $P_{n-1}^{(n)}$. So in general $$\left|P_{j}^{(n)}\right|={n\choose j}=\frac{n!}{j!(n-j)!}$$
Then we define the function $$q(a_1,a_2,...,a_n)=a_1a_2\cdots a_n$$
And see that, since points in $P^{(n)}_j$ by definition have $j$ entries equal to $x$, 
$$\mathbf{a}\in P_{j}^{(n)}\Rightarrow q(\mathbf{a})=x^j$$
So of course 
$$S_n=\sum_{j=0}^{n}\left|P_{j}^{(n)}\right|q\left(\mathbf{a}\in P_{j}^{(n)}\right)\\
=\sum_{j=0}^{n}{n\choose j}x^j=(1+x)^n$$
The final step coming from the Binomial theorem:
$$(x+y)^n=\sum_{j=0}^{n}{n\choose j}x^jy^{n-j}$$
A: Every $a_i$ is either $1$ or $x$, and you're taking the sum over all possibilities. For example, for $n=3$ you have $2^3$ terms (in order?): $$\begin{align}&1\cdot 1 \cdot 1+ 1\cdot x \cdot 1 + 1\cdot 1\cdot x + 1\cdot x\cdot x \\ &+x\cdot 1 \cdot 1+ x\cdot x \cdot 1 + x\cdot 1\cdot x + x\cdot x\cdot x. \end{align}$$
A: $\{1,x\}^n$ is the Cartesian self product of the set to the $n$-th degree.  $$\begin{align}\{1,x\}^n &= \overbrace{\{1,x\}\times\{1,x\}\times\cdots\times\{1,x\}}^{\text{$n$ factors}}\\[2ex]&=\{\underbrace{(1,1,\ldots,1, 1)}_{\text{$n$ terms}},(1,1,\ldots, 1,x),\ldots,(x,x,\ldots, x,1),(x,x,\ldots,x,x)\}\end{align}$$
So...

$$\sum\limits_{(a_1,\ldots,a_n)\in\{1,x\}^n} a_1a_2\cdots a_n$$
This is the sum, for all possible selections, of the product of $n$ factors each selected independently from the set $\{1,x\}$.
It is clearly equal to $(1+x)^n$
$$\begin{align}\sum\limits_{(a_1,\ldots,a_n)\in\{1,x\}^n} a_1a_2\cdots a_n&=(1+x)\sum_{(a_1,\ldots,a_{n-1})\in\{1,x\}^{n-1}}a_1a_2\cdots a_{n-1}
\\[2ex]&=(1+x)^n\end{align}$$
