0

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?

HallaSurvivor
  • 38,115
  • 4
  • 46
  • 87
tryst with freedom
  • 11,538
  • 1
    This is serious overkill for this problem, but you might look at something like $(1+x)^2(1+y)^3$. – lulu Jul 19 '20 at 20:28
  • why that specifical product? – tryst with freedom Jul 19 '20 at 20:32
  • You get one copy of $(1+x)$ for each man and one copy of $(1+y)$ for each woman. – lulu Jul 19 '20 at 20:36
  • @PeterForeman I am trying to generalize the generating function for more complicated problems – tryst with freedom Jul 19 '20 at 20:36
  • @lulu why is my way of writing it wrong? – tryst with freedom Jul 19 '20 at 20:37
  • I don't understand your method. And, I should stress, this is not a problem that lends itself to generating functions. It is much, much more natural to populate the male sector and female sector separately and then multiply. – lulu Jul 19 '20 at 20:38
  • In your method, what might $y^2$ mean? It's not like a dice throw where the $2$ means that exactly two women are chose...you need to keep track of the various ways to get two women. – lulu Jul 19 '20 at 20:40
  • I know how to do it in the easy way as PeterForeman had previously stated. I agree, it's not a direct application and that is why I told modification of generating function method. In my method y^2 means 'two women' . More generally y^k means k number of women – tryst with freedom Jul 19 '20 at 20:42
  • Right, that doesn't make sense since there is nothing in your expression that tells me how many ways there are to choose two (or $k$) women. Note that in $(1+y)^3=1+3y+3y^2+y^3$ there is $1$ way to choose $0$ women, $3$ ways to choose $1$, $3$ ways to choose $2$ and $1$ way to choose $3$. The algebra correctly keeps the count for you. – lulu Jul 19 '20 at 20:43
  • good point, I think I found a small modification to account for that – tryst with freedom Jul 19 '20 at 20:44
  • oh wait it ended up in samething you wrote – tryst with freedom Jul 19 '20 at 20:45
  • Let us continue this discussion in chat. – tryst with freedom Jul 19 '20 at 20:48
  • Right. $(1+y)^k$ encodes the binomial symbols as coefficients. In other words, and unsurprisingly, this method secretly coincides with the other. – lulu Jul 19 '20 at 20:48
  • You might be interested in Chapter 10.4 of the book "Foundations of combinatorics with applications" - it shows the basics of compositioning generating functions when seen directly as an interpretation of combinatorial construction. There is a free online version of the chapter here: http://www.math.ucsd.edu/~ebender/CombText/ – Sudix Jul 21 '20 at 04:42

2 Answers2

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 ^_^

HallaSurvivor
  • 38,115
  • 4
  • 46
  • 87
1

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

tryst with freedom
  • 11,538