I have a set S of n elements, from which I will choose combinations of m elements.
Normally, this is fairly basic. However, certain elements within S are mutually exclusive. This can be in pairs, or larger subsets, of which only 1 can at most exist in the final combination.
Given n and m, and the sizes of all mutually exclusive subsets in S; how can I best determine the number of possible combinations?
If no clean way exists, what is the best way to find a decent lower- and upper bound?
Suppose $S=\{1,2,3,4,5,6,7,8\}$, and you are choosing $5$ of those, but $A=\{2,3\}$ and $B=\{4,5,6\}$ are mutually exclusive subsets (you can only have at most $1$ from each.)
In this example it so happens to be barely possible to satisfy the requirements. You must take exactly one of $\{2,3\}$ and one of ${4,5,6}$ and all of $C = \{1,7,8\}$ so there are $2\cdot 3 = 6$ ways.
If instead we needed to choose three items, then we have a branching tree of possibilities, depending on whether a mutually exclusive set is sampled from or not. We might take from neither $A$ nor $B$, from $A$, from $B$, or from both. All four cases must be examined.
In the first case, there is only one choice: $\{1,7,8\}$ In the second, we choose $1$ from $A$, and two from $C$, for $6$ more ways. In the third, we choose $1$ from $B$ and two from $C$, for $9$ ways. In the fourth case, we choose $1$ from $A$ and one from $B$ and one from $C$, for $2\cdot 3 \cdot 3 = 18$ ways.
Altogether, that is $34$ ways.
There does not seem to be any easy formula for expressing this in general.
