Modifying generating functions to work for cases with distinct objects

Question

A committee is made of three people. If there are two men and three woman to choose from, how many committees have one man and two women?

Since there is exactly two distinct kinds of people, we must use two variable generating functions,

So the generating function for men is,

$$ M= \binom{2}{0} 1 + \binom{2}{1} x + \binom{2}{2} x^2 = (1+x)^2 $$

and,

the generation function for women is

$$ W= \binom{3}{0} 1 + \binom{3}{1} y + \binom{3}{2} y^2 + \binom {3}{3}y^3 = (1+y)^3$$

So, we need coefficient $ xy^2$ in the product $ MW$ however I'm getting the wrong answer. How would I change the method to work for this scenario?

Note: I know the regular method of doing this, I am just trying to generalize this generalizing function technique to more complicated problems. So it's the technique I want the discussion to be around not particularly the direct answer to the question

Edit: I now realized that this are the binomial expansion of $ (1+y)^3$ and $ (1+x)^2$. However, I wish to ask, how would I directly infer this? that these are the expansions?

Answer 1

While it seems this question has been answered in the comments, I'll try to add something with an official answer.

If you have 2 men and 3 women to choose from, then you can list out all of the possible committees (with no restriction on how many members there are) with the generating function

$$(1+m)^2 (1+w)^3 .$$

This is because $(1+x)^n = \sum \binom{n}{i} x^i$, and so the coefficients count the number of ways to choose $i$ people from a group of size $n$. Then multiplying $(1+x)^n(1+y)^m$ gives $\sum_{i,j} \binom{n}{i} \binom{m}{j} x^i y^j$, which counts the number of ways to choose $i$ from the first group and $j$ from the second.

Thus, in the generating function above, if you want the number of groups with 1 man and 2 women, you want the coefficient of $m^1 w^2$, which is $\binom{2}{1} \binom{3}{2}$, the correct answer.

To answer the question in your edit, how could someone have come up with this approach? In general, if you have generating functions $F(x) = \sum f_i x^i$ and $G(y) = \sum g_j y^j$ (note the variables are different!) the product $FG(x,y) = \sum_{i,j} f_i g_j x^i y^j$. This counts the number of ways to do have $i$ things from $F$ counted, and $j$ things from $G$ counted. Which is exactly what you want for this problem. All you need to realize afterwards is that $F$ and $G$ need to count the number of ways to choose some number of people from a group, but this is exactly the binomial formula.

This method is nice because it generalizes to a host of more complicated problems, which is what you were getting at in asking this at all. It's also entirely automatic. You could plug this product of polynomials into sage, and know the answer to a slew of related problems almost instantly.

To whet your appetite, here is a not-so-obvious generalization of this technique:

Say you have a group $G$ acting on a set of objects $X$, and you want to compute the number of different objects up to $G$-symmetry. That is, you want to know $|X/G|$. A technique known as Pólya-Redfield Counting lets you solve this problem in huge generality. The underlying idea, though, is exactly what you're doing here.

---

I hope this helps ^_^

Answer 2

The fundamental principle is that when you multiply 'polynomial factors' you are basically asking a series of yes or no question.

For example (1+y)(1+y)(1+y) is like placing the three women in a line and asking yes or no to the question "Will I invite this woman to the committee? " for woman in the line. As an example of directly interpreting the polynomial multiplication from this idea, Consider multiplying the 'y' from first factor into the one of second factor and then onto that multiplying 'y' from the third factor. In plain English, this means to say "choose the first woman and don't choose the second woman and choose the third one" . So this decision making chain can be simply expressed as $ (1+y)^3$ , if we expand this , the coefficient of $ y^2$ is the ways we could have decided to take two women's. This principle similarly applies for the men case.

refer this stack for more details