number of combinations of selecting 1 element each from 3 sets..

Question

Suppose we have 3 sets A=(a1,a2,...) B=(b1,b2,....) and C=(c1,c2,...) which may contain common elements that is element present in set A may present in set B or in Set C, element in set B may be there in Set C. I have to find number of ways of of selecting 1 element from each set such that no two elements in the selected set are same.

now suppose number of ways of doing this for only two set A and B is x and for B and C is y how can i use these results to get the final answer.

number of ways of doing this for only two sets A and B means we only have two sets A and B and we have to find number of ways of selecting 1 element from both set such that they are different.

Answer 1

I have tried to solve this problem for a different case: three sets, three different elements, but you may choose more than one element from the same set (so not one element form each set).

I would subdivide this problem in three parts:

• Count the number of combinations if the three elements are chosen from the red region (the three elements belong to one and only one of the sets A, B or C)
• Count the number of combinations if the three elements are chosen from the yellow region (the three elements belong to just two sets)
• Count the number of combinations if the three elements are chosen from the green region.

Let the number of elements in a set $S$ be written as $n_S$:

• The number of different elements in the red region is $n_R$
• The number of different elements in the yellow region is $n_Y$
• The number of different elements in the green region is $n_G$

Then the number of combinations is $$\dbinom{n_R}{3}+\dbinom{n_Y}{3}+\dbinom{n_G}{3}$$

If the order of the three elements matters, you must multiply this number by 6 (i.e. the number of permutations of three objects).

If you add the requirement that you select one element from each set, you can discard the yellow and green region. Assume that the number of elements that belong only to A is $\bar{n_A}$ (so the red part of set A), etc. We have to choose one element from each of those three sets, so we have $\bar{n_A}\bar{n_B}\bar{n_C}$ combinations.

Answer 2

Problem seems related to this one

Trying to find Generalization of Product rule when selections are dependent

If you apply directly inclusion exclusion, it won't work.