How to find number of combinations of choosing one from k subsets

Question

Consider we have set S:

S = {1,2,3,4,5,6}

and 3 (say k) subsets of S:

S_1 = {1,2,3}

S_2 = {2,3,4,5}

S_3 = {1,3,6}

What is the total number of cases choosing one element from each subsets?

Same element cannot picked from different subset, and the order is not considered.

For example,

S_1 = {2}, S_2 = {3}, S_3 = {6}

and

S_1 = {3}, S_2 = {2}, S_3 = {6}

considered as same. And

S_1 = {3}, S_2 = {3}, S_3 = {1}

is invalid since S_1 and S_2 choose the same element.

How can I formulate this?

Answer 1

You can solve this problem with the inclusion exclusion principle.

Assume you have two subsets $S_1, S_2$, then the number of ways to choose two elements is the number of ways to choose a number from $S_1$ multiplied by the number of ways of choosing an element from $S_2$ minus the number of ways of choosing the same number from $S_1$ and $S_2$.

Now given three sets $S_1, S_2, S_3$, the number of ways of choosing one element from each such that all elements are different is $$|S_1||S_2||S_3| - |S_1 \cap S_2| |S_3| - |S_1 \cap S_3||S-2| - |S_2 \cap S_3| |S_1| + |S_1 \cap S_2 \cap S_3|.$$

Now given a family of $k$ subsets, you can use the inclusion-exclusion principle to prove that the count can be given by the formula $$ \prod\limits_{i \in [k]}|S_i| + \sum\limits_{I \subseteq [k], |I|\geq 2}(-1)^{|I|} \left|\bigcap\limits_{i \in I}S_i\right|\prod\limits_{i \notin I}|S_i| $$