0

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?

RobPratt
  • 45,619
dshrikant
  • 43

1 Answers1

1

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.

RobPratt
  • 45,619
  • Considering players are distinguishable, can we solve the same with generating functions? – dshrikant Dec 23 '20 at 17:19
  • You could use $(1+f y)^5 (1+d y)^4 (1+g y)^2$ and extract the coefficient of $y^6$: $$10 d^4 f^2 + 10 d^4 f g + d^4 g^2 + 40 d^3 f^3 + 80 d^3 f^2 g + 20 d^3 f g^2 + 30 d^2 f^4 + 120 d^2 f^3 g + 60 d^2 f^2 g^2 + 4 d f^5 + 40 d f^4 g + 40 d f^3 g^2 + 2 f^5 g + 5 f^4 g^2.$$ From that, you would keep only $80 d^3 f^2 g + 120 d^2 f^3 g + 60 d^2 f^2 g^2$. – RobPratt Dec 23 '20 at 17:28
  • 1
    The $y$ counts players, and the $f$, $d$,and $g$ count forwards, defenders, and goalies, respectively. For each forward, select that forward ($f y$) or not ($1$). Because there are five forwards and each decision is independent, this yields $(1+fy)^5$. Similar explanation for defenders and goalies. – RobPratt Dec 23 '20 at 18:00