Combinations with exclusions

Question

Given five objects $A, B, C , D , E$. I'd like to calculate all possible sets of these objects such that

1. Two pairs of objects, $B$ and $C$, and $D$ and $E$, cannot coexist. For example the set $\{ABD\}$ would be valid but the set $\{CDE\}$ would not.
2. Each object appears no more than once in a set, e.g. $\{ACD\}$ is valid but $\{ADD\}$ is not.
3. There can be no empty set.
4. Apart from the above, there is no other limit on the cardinality of a set, e.g. $\{D\}$, $\{AB\}$, $\{ACE\}$. I know there can be no set of cardinality greater than 3, but it would be nice to show this.
5. The objects can be listed in any order, i.e. $\{AB\} = \{BA\}$

Edit My intention is to generalize the process of generating these combinations given any number of elements and restrictions.

Answer 1

From a response to a question, it appears that order does not matter.

It is not clear whether the empty set ("none") is to be considered a valid choice. We will assume that it is allowed. If it is not, subtract $1$ from the answer we will obtain.

With such a small number of objects, a carefully drawn up list may be the best approach.

Another good option is the approach taken by Sp3000. There, permutations were being counted, but the ideas can be readily modified to disregard order. For choices of $0, 1, 2, 3$ objects, the answers become $1$, $5$, $8$, and $4$ for a total of $18$ (or $17$ if we don't allow the empty set).

But you may like the following idea. Line up the $5$ objects in front of us, with $B$ and $C$ close to each other, and also $D$ and $E$, like this: $$A\qquad BC \qquad DE.$$

Stand in front of $A$ and decide whether to include her in the set we are building. There are $2$ choices, yes or no.

Now walk over to the $BC$ group. For every choice we made about $A$, we now have $3$ choices, $B$, $C$, or neither. So far, we have $2\times 3$ distinct possibilities.

Finally, walk over and stand in front of the $DE$ group. For every choice we made earlier, there are again $3$ choices, this time $D$, $E$, or neither.

Thus the total number of possible choices is $2\times 3\times 3$, that is, $18$. Again, if the empty set is not allowed, we have $17$ possibilities only.

Answer 2

Since your options are $A$, one of $\{B, C\}$, and one of $\{D, E\}$, it's easy to see why the cardinality can only be at most 3.

I'm going to tackle this case by case:

No objects

There is only one possibilitiy for the empty set.

One object

We can choose any of the 5 objects, so there are 5 possibilities.

Two objects

If we pick A first, we can choose any of the other four objects to go with it. If we pick any of the other objects first, then there are only three objects that can follow, due to the first restriction (e.g. $BA, BD, BE$ for $B$)

Thus there are $4 + 3 \times 4 = 16$ permutations for two objects.

Three objects

Pick one item from each of the sets $\{A\}, \{B, C\}, \{D, E\}$. There are $1 \times 2 \times 2 = 4$ possible selections that can be made.

For each selection, there are $3! = 6$ ways to permute the objects, giving a total of $4 \times 6 = 24$ permutations for three objects.

Altogether, this is a grand total of $1 + 5 + 16 + 24 = 46$ permutations.

Answer 3

Your question asks for the number of all subsets $S$ of $\{A,B,C,D,E\}$ which are not a superset of $\{B,C\}$ or $\{D,E\}$.

This is a typical application of the principle of inclusion-exclusion.

The total number of subsets of $\{A,B,C,D,E\}$ is $2^5 = 32$. The number of supersets of $\{B,C\}$ in $\{A,B,C,D,E\}$ is $2^3 = 8$ (each of the elements $A,B,C$ may be selected or not). In the same way, the number of supersets of $\{D,E\}$ in $\{A,B,C,D,E\}$ is $8$. The number of common supersets of $\{B,C\}$ and $\{D,E\}$ is 2.

Now the principle of inclusion-exclusion yields the result $$32 - 8 - 8 + 2 = 18.$$