find the sum for each n, k for each n, k  find the sum of $ \sum {|A_{i_1} \cup A_{i_2} \cup ... \cup A_{i_k} | } $ on all ordered sets of $ (A_{i_1}, A_{i_2}, ... ,A_{i_k}) $ where each $ A_{i_j} \subseteq \{1, ..., n\} $
I've found that the number of different terms in sigma is $ 2^{nk} $ and for $ k=1 $ got the answer of $ \sum_1^n i \binom{n}{i}$ which I'm not sure is correct
I just want to know if there's an easier way to solve this or if there's a formula for each n,k
 A: Call $c(n,k)$ the number of ways of writing a set with $n$ elements as (exact) union of $k$ subsets. Then we have
$$
c(n,k)=\sum_{i=0}^n{n\choose i}\sum_{l=0}^i{i\choose l}c(n-i+l,k-1).
$$
Indeed, assume $A_1\cup\ldots\cup A_k=\{1,\ldots,n\}$. First, assume that $A_1$ has $i$ elements, where $i=0,1,2\ldots,n$. Then there exists exactly $n\choose i$ choices for $A_1$. But then, $A_2\cup\cdots\cup A_k$ must contain at least all the remaining elements of $\{1,\ldots,n\}$, moreover, it can contains $l$ elements of $A_1$ as well. So assume that $A_2\cup\cdots\cup A_k$ contains exactly $l$ elements of $A_1$, where $l=0,1,2\ldots,i$. Thus there exists exactly $i\choose l$ choices for $l$ elements of $A_1$, and $c(n-i+l,k-1)$ possible choices for $A_2\cup\cdots\cup A_k$.
An elementary induction reveals that $c(n,k)=(2^k-1)^n$.
Now, let $s(n,k)$ be the value of the sum you want to compute. We can write
\begin{align*}
s(n,k)&=\sum_{i=0}^ni{n\choose i}c(i,k)=\sum_{i=0}^ni{n\choose i}(2^k-1)^i\\
&=n(2^k-1)\sum_{i=0}^n{n-1\choose i-1}(2^k-1)^{i-1}=n(2^k-1)2^{k(n-1)}.
\end{align*}
