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

| cite | improve this answer | |

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.