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

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?

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|$$