# 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

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*}