1
$\begingroup$

N boys and M girls are learning acting skills from a theatre in Mumbai. To perform a play on ‘Ramayana’ they need to form a group of P actors containing not less than 4 boys and not less than 1 girl. The theatre requires you to write a program that tells them the number of ways the group can be formed.

  • 0
    **Hint**: I think you can reduce this problem by assuming $4$ of the $P$ slots are filled by boys, and $1$ of the slots are filled by girls. Then you have only $P-5$ slots to be filled by $N-4$ boys and $M-1$ girls. ATM, I'm forgetting how you to count that.2012-02-18
  • 0
    @Jeff: Unfortunately, without substantial adjustment, this approach won't work. In general it overcounts the number of choices. The idea would work for the related problem of choosing $P$ balls from $M$ green and $N$ red, with the restrictions of the problem, where balls of the same colour are *indistinguishable*.2012-02-18
  • 0
    The title should give some indication of the actual question.2012-02-18

1 Answers 1

6

Assume that $M \ge 1$, $N\ge 4$, and $P\ge 5$. In how many ways can we choose $P$ people, with no sex restrictions? We are choosing $P$ people from $M+N$. The number of choices is $$\tbinom{M+N}{P}.$$ However, choosing $0$, $1$, $2$, or $3$ boys is forbidden.

In how many ways can we choose $0$ boys, and therefore $P$ girls? The answer is $\binom{M}{P}$. For reasons that will be apparent soon, we write that as $\binom{N}{0}\binom{M}{P}$.

There are $\binom{N}{1}\binom{M}{P-1}$ ways to choose $1$ boy and $P-1\,$ girls.

There are $\binom{N}{2}\binom{M}{P-2}$ ways to choose $2$ boys and $P-2\,$ girls.

There are $\binom{N}{3}\binom{M}{P-3}$ ways to choose $3$ boys and $P-3\,$ girls.

We need to deal with a small technical complication. Suppose, for example, that we are choosing $0$ boys and therefore $P$ girls, but the number $M$ of available girls is less than $P$. The answer above remains correct if we use the common convention that $\binom{m}{n}=0$ if $m

Finally, at least $1$ girl must be chosen. So the $\binom{N}{P}\binom{M}{0}$ all-boy choices are forbidden.

The total number of forbidden choices is therefore $$\tbinom{N}{0}\tbinom{M}{P}+\tbinom{N}{1}\tbinom{M}{P-1}+\tbinom{N}{2}\tbinom{M}{P-2} +\tbinom{N}{3}\tbinom{M}{P-3}+\tbinom{N}{P}\tbinom{M}{0}.$$ Finally, subtract the above number from the total number $\binom{M+N}{P}$ of choices with no sex restrictions.

  • 0
    Is that answer the same as $\binom{(M-1)+(N-4)}{P-5}$?2012-02-18
  • 0
    @Jeff: For (for instance) $M=3$, $N=8$, $P=5$ one has $\binom{(M-1)+(N-4)}{P-5}=\binom60=1$ whereas $\binom{M+N}P-\sum_{i=0}^3\binom Ni\binom M{P-i}-\binom NP =462-0-0-28-168-56=210$, so frankly: no!2012-02-18