How do you find the number of combinations of 3 elements chosen from multiple sets when you can't take more than element from each set?

So, for example, I have groups {1,2}, {3}, {4, 5}, {6,7,8,9}.

Now, I want to find the number of ways to choose N elements(specifically 3 in my case), from these sets, when I can only choose one element from each set.

Thanks.

I used the generating functions approach

For the 1st set - (1 + 2x) [Choose none or one of the {1,2}]
For the 2nd set - (1 + x)  [Choose none or only {3}]
For the 3rd set - (1 + 2x) [Choose none or one of the {4,5}]
For the 4th set - (1 + 4x) [Choose none or one of the {6,7,8,9}]


The solution is the coefficient of $x^3$ in the expansion of

$$(1 + 2x)(1 + x)(1 + 2x)(1 + 4x) = (1 + 9 x + 28 x^2 + 36 x^3 + 16 x^4)$$

Therefore 36 is the required solution

If you have $s$ sets and the number of elements in each are $n_1,n_2,\ldots,n_s$, and if no specific element occurs in more than one of the sets, then the number of choices will be the sum of all products of $N$ different numbers $n_k$, that is, $$\sum_{1\le k_1<\cdots<k_N\le s}n_{k_1}\cdots n_{k_N}\ .$$ If you have some specific information about the numbers $n_k$ (for example, they are all equal) then this could be simplified. The answer for the case you propose is $$(2\times1\times2)+(2\times1\times4)+(2\times2\times4)+(1\times2\times4)=36\ .$$

• Is there no faster way to do this? Although for 4 sets it's manageable, finding the answer would seem to get out of hand fairly quickly when the sets increase. Commented Jun 19, 2014 at 1:41
• If the numbers of elements in the various sets are "random" then I rather doubt that there would be anything faster than this. But maybe somebody will have some ideas. . . Commented Jun 19, 2014 at 3:25
• @DavidWell I can guarantee they're all distinct. But I think I do have a solution for choosing 3. It would be the total permutations of all the elements of the set(N*(N-1)*(N-2)), minus the sum of each set(|S|) multiplied by (|S|-1)*(|S|-2)*(Total elements-|S|)*3 (which is the way to choose 2 elements in the same set, and one element outside that set), minus |S|*|S-1|*|S-2|(which is the way to choose 3 elements from the same set). Sorry if that was a bit confusing, kinda hard to write things clearly without latex. :( Commented Jun 19, 2014 at 4:26