Q:

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.

A:

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

