Simplifying Sum of Subsets

222 Views Asked by At

Given sets $A$ and $R$ such that $R \subseteq A$ and a number $x \leq |A|$, I am trying to simplify the following sum:

$$\begin{equation*} \sum_{R \subseteq W \subseteq A : |W| = x} \Big( \sum_{Y \subseteq W} f(Y) \Big) \end{equation*}$$

For some function $f$ that isn't important in this context. The type of thing I am looking for is like this: I know that without the set $R$, that the sum can be simplified as follows:

$$\begin{equation*} \sum_{W \subseteq A : |W| = x} \Big( \sum_{Y \subseteq W} f \Big) = \sum_{Y \subseteq A : |Y| \leq x}\binom{|A| - |Y|}{x - |Y|}f(Y) \end{equation*}$$

Is there a similar simplification that can be done for the first sum containing $R$?

1

There are 1 best solutions below

1
On BEST ANSWER

The occurrence of $\binom{|A| - |Y|}{x - |Y|}$ in your formula is because you're counting, for a given $Y$, how many $W$s give rise to it - that is, how many sets $W$ there are satisfying $Y\subseteq W\subseteq A$. You can add any $x-|Y|$ elements from the remaining $|A|-|Y|$ elements of $A$ to construct the $W$s.

In this case, you need to count how many sets $W$ there are satisfying both $R\subseteq W$ and $Y\subseteq W\subseteq A$. The answer will depend on how large the intersection $R\cap Y$ is. Specifically, you are forced to add $|R\setminus Y|$ elements to $Y$ just to get it to qualify; then you have the freedom to add any $x-|Y|-|R\setminus Y|$ elements from the remaining $|A|-|Y|-|R\setminus Y|$ elements of $A$ to construct the $W$s. Since $|Y|+|R\setminus Y| = |Y\cup R|$, this yields $$ \sum_{\substack{R \subseteq W \subseteq A \\|W| = x}} \Big( \sum_{Y \subseteq W} f(Y) \Big) = \sum_{\substack{Y\subseteq A \\ |Y| \le x}} \binom{A-|Y\cup R|}{x-|Y\cup R|} f(Y). $$