# Permutation of numbers from multiple sets [May contain duplicate numbers among other sets], resulting in Non-Duplicate Set

We have 3 Data Sets. From each set we will be selecting few numbers. 3 from Set 1, 2 from Set 2, 3 from Set 3. Totally, we will get 8 Numbers from 3 Sets. The resulting sets shouldn't contain any duplicates.

My question is, How can we know whether we can generate the sets, each containing 8 numbers without duplicates or not? If we can generate, then how many combinations can we generate? What formula should we use?

I am adding the images for the better illustration of the problem statement.

Note: I have tried for the Permutations and Combinations, but I am not sure as how to solve this mathematical model. Any suggestions or references to solve this will be highly appreciated. I am not sure about the sections this problem falls under.

• As for knowing whether generating such a set is possible or not, check whether each individual set has a cardinality greater than or equal to your requirement from that set, (for eg, whether set1 has more than or equal to 3 elements) and check wether the union of all the sets has a cardinality greater than or equal to your total requirement (8 in this case). Aug 3 '15 at 18:36
• Hi Aritra, Thanks for pointing me towards 'Cardinality'. Yes, it will surely help me in first level check whether the combination is possible or not. So it forms one level of check for me. :-) Aug 4 '15 at 13:03

Sort all elements according to which sets they occur in, i.e. label them with an element of $\{0,1\}^3$, where each component signifies membership in one of the three sets. The elements you select from the first set can have any of the four labels with first component $1$, and there are $\binom63$ ways of selecting three such labels. Likewise, for choosing two elements of the second set, you need to choose two of the four labels with second component $1$, in $\binom53$ ways, and then another $\binom63$ ways to choose three of the four labels with third component $1$. That gives you $20\cdot10\cdot20=4000$ label combinations, but they're not all different, since the same label may occur in more than one of the three selections. For each combination, add up the three contributions for each label, giving you a count of elements with that label to be selected. Retain only inequivalent combinations (i.e. with different total label counts), and add up the numbers of ways to choose elements with the specified labels (which are just products of binomial coefficients).