How to solve $a+b+c=6; 2\le a\le 5, 2\le b\le 4, 1\le c\le 2$ with Generating Functions?

62 Views Asked by At

So here is the original problem

For the inter-hostel six-a-side football tournament, a team of 6 players is to be chosen from 11 players consisting of 5 forwards, 4 defenders and 2 goalkeepers. The team must include at least 2 forwards, at least 2 defenders and at least 1 goalkeeper. Find the number of different ways in which the team can be chosen.

Which I think can be written as $$ a+b+c=6; \quad 2\le a \le 5,\quad 2\le b \le 4\quad 1\le c \le 2 $$

I know how to solve the problem with combinations where we choose [(3,2,1), (2,3,1), (2,2,2)] which is of the form (#of forwards, #defenders, #goalkeepers), this gives answer as 260.

While solving the same problem with generating functions I arrived at following polynomial $$ x^2 (1+x+x^2+x^3) * x^2 (1+x+x^2) * x (1+x) $$ which is equivalent to $$ x^5 *\frac{(1-x^4)}{(1-x)} *\frac{(1-x^3)}{(1-x)} *\frac{(1-x^2)}{(1-x)}.$$

Now the problem is converted to finding $x^1$ in $ \frac{(1-x^4)}{(1-x)} *\frac{(1-x^3)}{(1-x)} *\frac{(1-x^2)}{(1-x)}$ and we can only get $x^1$ from $(1-x)^{-3}$ to which there are only 3 ways which is a wrong answer.

What is the correct method?

1

There are 1 best solutions below

3
On

Your $3$ solutions for $(a,b,c)$ are correct if players in the same position are indistinguishable. Accounting for distinguishable players yields $$\binom{5}{3}\binom{4}{2}\binom{2}{1}=10\cdot6\cdot2=120$$ solutions for $(a,b,c)=(3,2,1)$, $$\binom{5}{2}\binom{4}{3}\binom{2}{1}=10\cdot4\cdot2=80$$ solutions for $(a,b,c)=(2,3,1)$, and $$\binom{5}{2}\binom{4}{2}\binom{2}{2}=10\cdot6\cdot1=60$$ solutions for $(a,b,c)=(2,2,2)$, so $120+80+60=260$ solutions altogether.

Your generating function also yields the correct count of $3$ if players in the same position are indistinguishable.