0
$\begingroup$

Possible Duplicate:
Combinatorics-N boys and M girls are learning acting skills from a theatre in Mumbai.

N boys and M girls are learning acting skills from a theatre. To perform a play 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.

Note: Composition should be unique and not the order in which the composition is made of.

I have tried a lot but can't get over some of my confusions. How can i solve this ?

  • 0
    @steve: I am aware what $P$ is. My point is that if you want to solve the problem with specific numbers, it is not enough to specify how many boys and how many girls there are, you **also** need to specify what $P$ is. Otherwise, your answer needs to have $P$s all over the place. That's why your attempted answer is nonsense: without a specific $P$, or without leaving $P$ indicated, whatever it is you think you are counting has nothing whatsoever to do with the problem at hand.2012-02-23

2 Answers 2

1

If $N\lt 4$, $M\lt 1$, or $P\lt 5$, then you are sunk: there is no way to accomplish the task.

So assume $N\geq 4$, $M\geq 1$, and $P\geq 5$.

How can a particular casting fail to satisfy the conditions? If it is made up entirely of boys (only possible if $M\geq P$), or it contains either no boys, exactly one boy, exactly two boys, or exact three boys (only possible if $M\geq P$, $M\geq P-1$, $M\geq P-2$, or $M\geq P-3$, respectively).

  1. In how many ways can your cast have no girls? You have $\binom{N}{P}$ ways of selecting $P$ boys.

  2. In how many ways can your cast have no boys? You have $\binom{M}{P}$ ways of doing it.

  3. In how many ways can your cast have exactly one boy? There are $\binom{N}{1}$ ways of choosing the boy, and $\binom{M}{P-1}$ ways of choosing the girls.

Continue this way. Then figure out how many total casts you can make without regard of how many boys and girls there are. The number you are looking for will be the total minus the sum of the "bad casts" we are counting above.

  • 0
    @steve: Okay, I've considered it. Now what? Seriously: you need **three** pieces of information to make this a problem with no variables: the value of $N$ (how many boys), the value of $M$ (how many girls), and the value of $P$ (how many people are in the play). The fact that you keep ignoring $P$ is, no doubt, a big part of why you aren't understanding how to do the problem. And I've given you all the information you need to consider any specific case, like $6$ boys, $2$ girls, and $5$ players. Just go through the cases.2012-02-23
1

You can think about the problem in either of two ways. One is the way that you seem to have in mind in your comment: add up the possibilities for every possible boy-girl split, from $4$ boys and $P-4$ girls to $P-1$ boys and $1$ girl. (I’m assuming that $N\ge 4$, $M\ge 1$, and $P\ge 5$, so that there is at least one possible combination.) If you do this, you have to evaluate

$\sum_{n=4}^{P-1}\binom{N}n\binom{M}{P-n}\;:\tag{1}$

the number of ways of picking $n$ boys out of $N$ is $\binom{N}n$, and the number of ways of picking $P-n$ girls out of $M$ is $\binom{M}{P-n}$, so the number of ways of forming a combination with $n$ boys and $P-n$ girls is $\binom{N}n\binom{M}{P-n}$, and you need to sum these over all possible values of $n$.

If you’re writing a computer program to solve the problem, this is entirely feasible, but it would be rather painful to do by hand if $P$ were very large.

The other possibility is to count the unacceptable combinations and subtract that number from the total. In other words, if there are $u$ unacceptable combinations, calculate $\binom{N+M}P-u\;.\tag{2}$ The advantage to this is that if $P$ is at all large, there are fewer ways to form unacceptable combinations than to form acceptable ones:

  • you could have $P$ boys and no girls, or
  • $P$ girls and no boys, or
  • $P-1$ girls and $1$ boy, or
  • $P-2$ girls and $2$ boys, or
  • $P-3$ girls and $3$ boys.

That’s a mere five boy-girl splits to worry about, and instead of the $P-4$ terms of the sum in $(1)$, you’ll have only five terms (and the one subtraction in $(2)$). Thus, as soon a $P$ gets up to $10$ or so you’re better off using the second method.