Let $P$ be a set of $n$ elements and $Q$ be a subset of $P$ having $m < n$ elements.
How many subsets of $P$ containing $k$ elements are there, such that no two elements of $Q$ appear together?
For example, if
$P = \{1,2,3,4,5,6,7\}$, and
$Q = \{1,2,4,7\}$,
then {2,3,5,6} is a valid subset of size $4$, but these are invalid ones:
- {1,2,5,6}, because 1 and 2 cannot appear together;
- {1,2,6,7}, because both 1 and 2, and 1 and 7 cannot appear together.
- {1,2,4,7}, because 1,2; 1,4; 1,7; 2,4; 2,7 and 4,7 cannot appear together.
My thoughts:
I can make $\binom{n}{k}$ subsets of $P$. Then I have to subtract all invalid ones. I can pick one "bad" pair from $Q$ and count how many subsets of size $k$ contains that pair: $\binom{m}{2}\binom{n-2}{k-2}$.
I'd end up with: $\binom{n}{k} - \binom{m}{2}\binom{n-2}{k-2}$.
But this is excluding too much! For instance, both $\{1,2,4,7\}$ and $\{1,2,4,5\}$ are being counted multiple times. Now I should add back all the subsets with two pairs, and then subtract again all subsets with three pairs and so on.
But this is where I am stuck: how can I count the combinations having $p>1$ "bad" pairs?
This is a generalization of this question.
Easier to consider that there are two mutually exclusive cases, depending on whether $(0)$ or $(1)$ element is taken from $Q$.
So, the enumeration is
$$\binom{n-m}{k} + \left[\binom{n-m}{k-1} \times \binom{m}{1}\right].$$