2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.